<*PRAGMA LL*>A
Region.T
represents a set of integer lattice points.
INTERFACEIfRegion ; IMPORT Rect, Point, Axis; TYPE T = RECORD r: Rect.T; p: P := NIL END; P <: REFANY;
rg
is a region, then rg.r
is the smallest rectangle
containing all points in rg
, and rg.p
is the private
representation of the region as a sorted array of disjoint
rectangles.
CONST Empty = T{Rect.Empty, NIL}; Full = T{Rect.Full, NIL}; PROCEDURE FromRect(READONLY r: Rect.T): T;
Return the region containing the same points as r
.
PROCEDURE FromRects(READONLY ra: ARRAY OF Rect.T): T;
Return the region containing all points in any rectangle of ra
.
PROCEDURE ToRects(READONLY rg: T): REF ARRAY OF Rect.T;
Returns a list of disjoint rectangles that partition rg
.
The call
ToRects(Empty)
produces an array of length zero.
PROCEDURE FromPoint(READONLY p: Point.T): T;
Return the region containing exactly the point p
.
PROCEDURE BoundingBox(READONLY rg: T): Rect.T;
Return the smallest rectangle containing all the points ofrg
; this is equivalent torg.r
.
PROCEDURE Add(READONLY rg: T; READONLY p: Point.T): T;
Return the translation ofrg
byp
.
That is,
Add(rg, p)
contains pt
if and only if rg
contains
Point.Sub(pt, p)
.
PROCEDURE Sub(READONLY rg: T; READONLY p: Point.T): T;
Return Add(rg, Point.Minus(p))
.
PROCEDURE AddHV(READONLY rg: T; dh, dv: INTEGER): T;
Return Add(rg, Point.T{dh,dv})
.
PROCEDURE Inset(READONLY rg: T; n: INTEGER): T;
Return the region inset intorg
byn
.
That is, if
n
is non-negative, Inset(rg, n)
contains a point
pt
if all points within distance n
of pt
are contained in rg
.
If n
is non-positive, Inset(rg, n)
contains a point pt
if some
point within distance -n
of pt
is in rg
. For the purposes
of this definition, points p
and q
are ``within distance n
''
if both ABS(p.h-q.h)
and ABS(p.v-q.v)
are at most n
. (If n
is zero, both definitions give Inset(rg, n) = rg
.)
PROCEDURE PlaceAxis(READONLY rg: T; n: INTEGER; hv: Axis.T): T;
Return the retraction ofrg
byn
along thehv
axis.
That is, let
rect
equal Rect.FromSize(1, ABS(n))
if hv
is Axis.T.Ver
or rect.FromSize(1, ABS(n))
if hv
is Axis.T.Hor
. If n
is
non-negative, then PlaceAxis(rg, n, hv)
contains a point pt
if
the rectangle Rect.Add(pt, rect)
is contained in rg
. If n
is negative, then PlaceAxis(rg, n, hv)
contains a point pt
if
Rect.Add(pt, rect)
contains some point in rg
.
PROCEDURE Place(READONLY rg: T; h, v: INTEGER): T;
Return the retraction ofrg
byh
along the horizontal axis and byv
along the vertical axis.
More precisely,
Place(rg, h, v)
is defined by the expression
PlaceAxis(PlaceAxis(rg, h, Axis.Hor), v, Axis.Ver) .
PROCEDURE Join(READONLY rg, rgP: T): T;
Return the union of the points inrg
andrgP
.
PROCEDURE JoinRect(READONLY r: Rect.T; READONLY rg: T): T;
Return the union of the points inr
andrg
.
PROCEDURE JoinRegions(READONLY rg: REF ARRAY OF T): T;
Return the union of all the regions in rg
.
PROCEDURE Meet(READONLY rg, rgP: T): T;
Return the intersection ofrg
andrgP
.
PROCEDURE MeetRect(READONLY r: Rect.T; READONLY rg: T): T;
Return the intersection of the points inr
andrg
.
PROCEDURE Difference(READONLY rg, rgP: T): T;
Return the set of points inrg
and not inrgP
.
PROCEDURE SymmetricDifference(READONLY rg, rgP: T): T;
Return the set of points in exactly one ofrg
andrgP
.
PROCEDURE MaxSubset(READONLY r: Rect.T; READONLY rg: T): Rect.T;
Return a large rectangular subset ofrg
containingr
, or returnEmpty
ifr
is not a subset ofrg
.
PROCEDURE Flip(READONLY rg: T; hor, ver: BOOLEAN): T;
Return the region which flipsrg
about the horizontal and vertical axes, depending on whetherhor
andver
areTRUE
.
More precisely, let
H = -1
if hor
is TRUE
, and +1
otherwise,
and similarly for V
. Then a point (h,v)
is in the flipped region
iff (H*h, V*v)
is in rg
.
PROCEDURE Equal(READONLY rg, rgP: T): BOOLEAN;
Return whetherrg
andrgP
contain the same points.
PROCEDURE IsEmpty(READONLY rg: T): BOOLEAN;
Return whether rg
is empty.
PROCEDURE IsRect(READONLY rg: T): BOOLEAN;
Return whether rg
is a rectangle, that is, whether
it contains all the points in its bounding box.
PROCEDURE Member(READONLY p: Point.T; READONLY rg: T): BOOLEAN;
Return whetherp
is inrg
.
PROCEDURE SubsetRect(READONLY r: Rect.T; READONLY rg: T): BOOLEAN;
Return whetherr
is contained inrg
.
PROCEDURE Subset(READONLY rg, rgP: T): BOOLEAN;
Return whetherrg
is contained inrgP
.
PROCEDURE OverlapRect(READONLY r: Rect.T; READONLY rg: T): BOOLEAN;
Return whetherr
andrg
have any point in common.
PROCEDURE Overlap(READONLY rg, rgP: T): BOOLEAN;
Return whetherrg
andrgP
have any point in common.
END Region.