Contributed by Michel Dagenais (dagenais@vlsi.polymtl.ca), 1994.
A RealRect.T
is a set of points lying in a rectangle with its sides
parallel to the coordinate axes. The directions of the screen are
named after the compass points, with north at the top. A rectangle
rect
contains a point pt
if
pt.h is in [rect.west .. rect.east - 1] AND pt.v is in [rect.north .. rect.south - 1]We impose the restriction that if a rectangle contains no points, then it must be equal as a record to
RealRect.Empty
.
INTERFACE--- Initialization ---RealRect ; IMPORT Axis, RealInterval, RealPoint; TYPE T = RECORD west, east, north, south: REAL END; TYPE Edge = {W, E, N, S}; TYPE Vertex = {NW, NE, SW, SE}; CONST Empty = T {0.0, 0.0, 0.0, 0.0}; (* An empty rectangle *) CONST Full = T {FIRST(REAL), LAST(REAL), FIRST(REAL), LAST(REAL)}; (* The biggest possible rectangle *)
PROCEDURE FromEdges(w, e, n, s: REAL): T;
Ifw >= e
orn >= s
returnEmpty
, else returnT{w,e,n,s}
.
PROCEDURE FromAbsEdges(h1, h2, v1, v2: REAL): T;
Return
FromEdges(MIN(h1,h2), MAX(h1,h2), MIN(v1,v2), MAX(v1,v2))
PROCEDURE FromPoint(READONLY p: RealPoint.T): T;
Return the rectangle whose only element is p
.
PROCEDURE FromCorners(READONLY p, q: RealPoint.T): T;
Return FromAbsEdges(p.h,q.h,p.v,q.v)
.
PROCEDURE FromCorner( READONLY p: RealPoint.T; hor, ver: REAL): T;
Return FromEdges(p.h, p.h+hor, p.v, p.v+ver)
.
PROCEDURE FromSize(hor, ver: REAL): T;
Return FromCorner(Point.Origin,hor,ver)
.
PROCEDURE Center(READONLY r: T; READONLY p: RealPoint.T): T;
Ifr
is empty then returnEmpty
else return a rectangles
such thatCongruent(r, s)
andMiddle(s)=p
.
PROCEDURE FromIntervals (READONLY hor, ver: RealInterval.T): T;
Return FromEdges(hor.lo,hor.hi,ver.lo,ver.hi)
.
PROCEDURE FromAxes (axis: Axis.T; READONLY n, m: RealInterval.T): T;
If axis=Hor then FromIntervals(n,m), else FromIntervals(m,n)
--- Selection ---
PROCEDURE NorthWest(READONLY r: T): RealPoint.T;
Return Point.T{r.west,r.north}
.
PROCEDURE NorthEast(READONLY r: T): RealPoint.T;
Return Point.T{r.east,r.north}
.
PROCEDURE SouthWest(READONLY r: T): RealPoint.T;
Return Point.T{r.west,r.south}
.
PROCEDURE SouthEast(READONLY r: T): RealPoint.T;
Return Point.T{r.east,r.south}
.
PROCEDURE GetVertex (v: Vertex; READONLY r: T): RealPoint.T;
the point corresponding to the vertex v of r; origin if r is empty
PROCEDURE HorSize(READONLY r: T): REAL;
Return r.east - r.west
.
PROCEDURE VerSize(READONLY r: T): REAL;
Return r.south - r.north
.
PROCEDURE Size (a: Axis.T; READONLY r: T): REAL;
HorSize(r) if a=Hor; VerSize(r) if a=Ver
PROCEDURE DiagSizeSquare (READONLY r: T): REAL;
HorSize(r)**2+VerSize(r)**2
PROCEDURE Middle(READONLY r: T): RealPoint.T;
Return Point.T{r.west+r.east DIV 2, r.north+r.south DIV 2}
.
PROCEDURE PickEdge (READONLY r: T; READONLY p: RealPoint.T): Edge;
Return the edge of r closest to p (one of them if not unique)
PROCEDURE PickVertex (READONLY r: T; READONLY p: RealPoint.T): Vertex;
Return the vertex of r closest to p (one of them if not unique)
PROCEDURE Project(READONLY r: T; READONLY p: RealPoint.T): RealPoint.T;
Return the element ofr
that is closest top
. This is a checked runtime error ifr
is empty.
--- Transformation ---
PROCEDURE Add(READONLY r: T; READONLY p: RealPoint.T): T;
Return
FromEdges(r.west+p.h, r.east+p.h, r.north+p.v,r.south+p.v)
PROCEDURE Sub(READONLY r: T; READONLY p: RealPoint.T): T;
Return Add(r, Point.Minus(p))
.
PROCEDURE Move (READONLY r: T; READONLY p: RealPoint.T): T;
increment r.e and r.w by p.h; increment r.n and r.s by p.v
PROCEDURE MoveH (READONLY r: T; h: REAL): T;
increment r.e and r.w by h
PROCEDURE MoveV (READONLY r: T; v: REAL): T;
increment r.n and r.s by v
PROCEDURE MoveHV (READONLY r: T; h, v: REAL): T;
increment r.e and r.w by h, r.n and r.s by v
PROCEDURE Scale (READONLY r: T; num, den: REAL): T;
scale a rectangle by a fraction
PROCEDURE Change (READONLY r: T; dw,de,dn,ds: REAL): T;
Ifr
is empty returnEmpty
, else return the rectangleFromEdges(r.west+dw, r.east+de, r.north+dn, r.south+ds)
.
PROCEDURE Inset(READONLY r: T; n: REAL): T;
Return Change(r, n, -n, n, -n)
.
PROCEDURE Transpose(READONLY r: T; ax := Axis.T.Ver): T;
Ifr
is empty or ifax = Axis.Hor
, then returnr
, else returnT{r.north, r.south, r.west, r.east}
.
PROCEDURE MoveEdge (READONLY r: T; e: Edge; dn: REAL): T;
If r is empty return empty, else move the edge e of r by dn in the positive direction of the axis perpendicular to it
PROCEDURE MoveVertex (READONLY r: T; v: Vertex; READONLY dp: RealPoint.T): T ;
If r is empty return empty, else move the vertex v of r by dp in the northwest-southeast direction
PROCEDURE Stretch (READONLY r: T; axis: Axis.T; lo, hi: REAL): T;
If r is empty return empty, else change the interval of r determined by axis.
PROCEDURE Join(READONLY r, s: T): T;
Return the smallest rectangle containing bothr
ands
.
PROCEDURE Meet(READONLY r, s: T): T;
Return the largest rectangle contained in bothr
ands
.
PROCEDURE Extend (READONLY r: T; READONLY p: RealPoint.T): T;
Returns Join(r,FromPoint(p))
PROCEDURE Chop (hv: Axis.T; READONLY r: T; n: REAL; VAR (*out*) s, t: T) ;
Chop a rectangle in two. If hv=Ver, s and t become the top and bottom parts of r resp. If hv=Hor, s and t become the left and right parts of r resp.
TYPE Partition = ARRAY [0..4] OF T; PROCEDURE Factor( READONLY r, s: T; VAR (*out*) f: Partition; dh, dv: REAL) ;
Partitionr
into5
piecesf[0]..f[4]
wheref[2] = Meet(r,s)
, and the other rectangles inf
partition the set differencer-s
.
The order of
f
is such that if i<j
then f[i]
translated by
any positive multiple of (dh,dv)
doesn't intersect f[j]
. (Only
the signs of dh
and dv
affect the order, not their magnitude.)
PROCEDURE Mod(READONLY p: RealPoint.T; READONLY r: T): RealPoint.T;
Return the element ofr
whose distance fromp
in each axis is a multiple of the size ofr
in that axis. This is a checked runtime error ifr
is empty.
--- Test ---
PROCEDURE Equal (READONLY r, s: T): BOOLEAN;
Rectangle equality; all empty rectangles are equal
PROCEDURE IsEmpty(READONLY r: T): BOOLEAN;
Return whether r
is empty.
PROCEDURE Member(READONLY p: RealPoint.T; READONLY r: T): BOOLEAN;
Return whether p is in r.
PROCEDURE Overlap(READONLY r, s: T): BOOLEAN;
Return whetherr
ands
have any element in common.
PROCEDURE Subset(READONLY r, s: T): BOOLEAN;
Return whetherr
is contained ins
.
PROCEDURE Congruent(READONLY r, s: T): BOOLEAN;
Return whetherr
ands
are congruent, that is, whether they have the same height and width.
--- Coordinate Transformation ---
PROCEDURE GlobToLoc (READONLY r: T; READONLY p: RealPoint.T): RealPoint.T;
Transform p (in global coordinates) to the local coordinate system of r. Return Point.Sub(p,NorthWest(r))
PROCEDURE LocToGlob (READONLY r: T; READONLY p: RealPoint.T): RealPoint.T;
Transform p (in the local coordinate system of r) to global coordinates. Returns Point.Add(p,NorthWest(r))
--- Standard type operations ---
PROCEDURE New (READONLY value: T): REF T;
Allocates and initializes a new heap value
PROCEDURE NewArray (size: CARDINAL; READONLY value := Empty): REF ARRAY OF T;
Allocates a new array from the heap and initializes all its elements with the given value
PROCEDURE UntracedNew (READONLY value: T): UNTRACED REF T;
Allocates and initializes a new untraced value
PROCEDURE UntracedNewArray (size: CARDINAL; READONLY value := Empty): UNTRACED REF ARRAY OF T;
Allocates a new untraced array from the heap and initializes all its elements with the given value
PROCEDURE Compare (READONLY a, b: T): INTEGER;
== RETURN (-1 if Lt (a, b), 0 if Eq (a, b), +1 o. w.)
PROCEDURE Lt (READONLY a, b: T): BOOLEAN;
== RETURN lexicographic comparison of a, b by <w, e, n, s>
PROCEDURE Eq (READONLY a, b: T): BOOLEAN;
== RETURN (a = b)
PROCEDURE Hash (READONLY a: T): INTEGER;
== RETURN a suitable hash value
END RealRect.