realgeometry/src/RealRect.i3


 Copyright (C) 1989, Digital Equipment Corporation           
 All rights reserved.                                        
 See the file COPYRIGHT for a full description.              

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 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 *)
--- Initialization ---

PROCEDURE FromEdges(w, e, n, s: REAL): T;
If w >= e or n >= s return Empty, else return T{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;
If r is empty then return Empty else return a rectangle s such that Congruent(r, s) and Middle(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 of r that is closest to p. This is a checked runtime error if r 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;
If r is empty return Empty, else return the rectangle FromEdges(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;
If r is empty or if ax = Axis.Hor, then return r, else return T{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 both r and s.

PROCEDURE Meet(READONLY r, s: T): T;
Return the largest rectangle contained in both r and s.

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) ;
Partition r into 5 pieces f[0]..f[4] where f[2] = Meet(r,s), and the other rectangles in f partition the set difference r-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 of r whose distance from p in each axis is a multiple of the size of r in that axis. This is a checked runtime error if r 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 whether r and s have any element in common.

PROCEDURE Subset(READONLY r, s: T): BOOLEAN;
Return whether r is contained in s.

PROCEDURE Congruent(READONLY r, s: T): BOOLEAN;
Return whether r and s 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.

RealRect's implementation is in:


interface RealInterval is in:


interface RealPoint is in:


procedure RealRect.FromEdges is in:


procedure RealRect.FromAbsEdges is in:


procedure RealRect.FromPoint is in:


procedure RealRect.FromCorners is in:


procedure RealRect.FromCorner is in:


procedure RealRect.FromSize is in:


procedure RealRect.Center is in:


procedure RealRect.FromIntervals is in:


procedure RealRect.FromAxes is in:


procedure RealRect.NorthWest is in:


procedure RealRect.NorthEast is in:


procedure RealRect.SouthWest is in:


procedure RealRect.SouthEast is in:


procedure RealRect.GetVertex is in:


procedure RealRect.HorSize is in:


procedure RealRect.VerSize is in:


procedure RealRect.Size is in:


procedure RealRect.DiagSizeSquare is in:


procedure RealRect.Middle is in:


procedure RealRect.PickEdge is in:


procedure RealRect.PickVertex is in:


procedure RealRect.Project is in:


procedure RealRect.Add is in:


procedure RealRect.Sub is in:


procedure RealRect.Move is in:


procedure RealRect.MoveH is in:


procedure RealRect.MoveV is in:


procedure RealRect.MoveHV is in:


procedure RealRect.Scale is in:


procedure RealRect.Change is in:


procedure RealRect.Inset is in:


procedure RealRect.MoveEdge is in:


procedure RealRect.MoveVertex is in:


procedure RealRect.Stretch is in:


procedure RealRect.Join is in:


procedure RealRect.Meet is in:


procedure RealRect.Extend is in:


procedure RealRect.Chop is in:


procedure RealRect.Factor is in:


procedure RealRect.Mod is in:


procedure RealRect.Equal is in:


procedure RealRect.IsEmpty is in:


procedure RealRect.Member is in:


procedure RealRect.Overlap is in:


procedure RealRect.Subset is in:


procedure RealRect.GlobToLoc is in:


procedure RealRect.LocToGlob is in:


procedure RealRect.New is in:


procedure RealRect.NewArray is in:


procedure RealRect.UntracedNew is in:


procedure RealRect.UntracedNewArray is in:


procedure RealRect.Compare is in:


procedure RealRect.Lt is in:


procedure RealRect.Eq is in:


procedure RealRect.Hash is in: