# The Region interface

A `Region.T` represents a set of integer lattice points.

    INTERFACE Region;

    IMPORT Rect, Point, Axis;

    TYPE
      T = RECORD r: Rect.T; p: P := NIL END;

      P <: REFANY;

If `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 of `rg`; this is equivalent to `rg.r`.

    PROCEDURE Add(READONLY rg: T; READONLY p: Point.T): T;

Return the translation of `rg` by `p`.

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 into `rg` by `n`.

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 of `rg` by `n` along the `hv` 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 of `rg` by `h` along the horizontal axis and by `v` 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 in `rg` and `rgP`.

    PROCEDURE JoinRect(READONLY r: Rect.T;
      READONLY rg: T): T;

Return the union of the points in `r` and `rg`.

    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 of `rg` and `rgP`.

    PROCEDURE MeetRect(READONLY r: Rect.T;
      READONLY rg: T): T;

Return the intersection of the points in `r` and `rg`.

    PROCEDURE Difference(READONLY rg, rgP: T): T;

Return the set of points in `rg` and not in `rgP`.

    PROCEDURE SymmetricDifference(READONLY rg, rgP: T): T;

Return the set of points in exactly one of `rg` and `rgP`.

    PROCEDURE MaxSubset(READONLY r: Rect.T;
      READONLY rg: T): Rect.T;

Return a large rectangular subset of `rg` containing `r`, or return `Empty` if `r` is not a subset of `rg`.

    PROCEDURE Flip(READONLY rg: T; hor, ver: BOOLEAN): T;

Return the region which flips `rg` about the horizontal and vertical axes, depending on whether `hor` and `ver` are `TRUE`.

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 whether `rg` and `rgP` 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 whether `p` is in `rg`.

    PROCEDURE SubsetRect(READONLY r: Rect.T;
      READONLY rg: T): BOOLEAN;

Return whether `r` is contained in `rg`.

    PROCEDURE Subset(READONLY rg, rgP: T): BOOLEAN;

Return whether `rg` is contained in `rgP`.

    PROCEDURE OverlapRect(READONLY r: Rect.T;
      READONLY rg: T): BOOLEAN;

Return whether `r` and `rg` have any point in common.

    PROCEDURE Overlap(READONLY rg, rgP: T): BOOLEAN;

Return whether `rg` and `rgP` have any point in common.

    END Region.