Notes on the geometry layer of CLIM II

Regions and region-sets, primarily.  What pieces exist, how do they
fit together, how might they be implemented, and is the system
conceptually whole?

The presentation of regions in CLIM seems to be flawed.  Why not defer
region composition until /after/ the simple regions have been
introduced?  Additionally, bounding-rectangles can, and possibly
should, be introduced before region composition.  Part of the
description of bounding-rectangles relies on transformations, but
transformation application depends on simple regions.

** Object mutability and capture

Most region objects capture their mutable arguments, meaning that the
arguments must not be mutated while the geometry object is still in
scope.  There are no writers defined for any aspect of any simple
region object, meaning that there is no standard way to mutate such
objects.  Additionally, all standard simple region classes are
specified to produce immutable instances.

The exception to the general immutability here is that the three
standard REGION-SET classes are not specified to produce immutable
instances and, while there are no writers defined for the region
composition protcol, REGION-SET-REGIONS returns a list of regions that
may share structure with the internal implementation of the standard
REGION-SETs.

Conclusion: This is a specific nod to the possibility of a user
implementation of the various geometry protocols.

** The coordinate system

CLIM II specification, chapter 3, paragraph three states that the
coordinate system is an "abstract, continuous" system, and that the
system (not the coordinates, but the entire system) is converted to
"``real world''" coordinates only when doing things such as rendering
a geometric object to a display device.

Leaving aside the conversion of an entire coordinate system into a set
of coordinates, and the notion of a "real world" with coordinates,
section 3.1 defines a COORDINATE type which is required to be either T
or a subtype of REAL and grants explicit permission to use a "more
specific subtype of real", giving the example of SINGLE-FLOAT, "for
reasons of efficiency".  Amazingly enough, this gives permission to
use a coordinate type such as BIT or (INTEGER 0 0).

In any case, taking SINGLE-FLOAT as our coordinate type, we can
immediately point out that the precision of a SINGLE-FLOAT is
insufficient for a continuous coordinate space.  The same applies for
RATIONAL numbers, or any other convenient coordinate representation.

If we acknowledge the coordinate system as an /approximation/ of a
continuous system, however, we have the somewhat useful result that we
cannot determine the two points on a line immediately adjacent to a
given point, used in conjunction with dimensionality conservation when
defining the region composition operations.

** Predicates

The predicates used between regions are:

  - REGION-EQUAL: Do two regions contain exactly the same set of
    points?
  - REGION-CONTAINS-REGION-P: Are all of the points in the second
    region also contained in the first?
  - REGION-CONTAINS-POSITION-P: Is a particular point contained in a
    region?
  - REGION-INTERSECTS-REGION-P: Would the REGION-INTERSECTION of two
    regions contain any points at all?

A few notes here:

  - Two regions are REGION-EQUAL iif REGION-CONTAINS-REGION-P for both
    orderings of the regions.
  - REGION-CONTAINS-POSITION-P is REGION-CONTAINS-REGION-P with a
    "spread" point argument.
  - REGION-INTERSECTS-REGION-P is not a question of "do two regions
    contain any points in common" because of dimensionality
    conservation in region composition.  Two rectangles with a common
    border both contain the points along the line of the border, but
    do not intersect.

Robert Strandh has raised concerns that some of these functions might
be "very hard" to implement across the full range of region types,
including the various REGION-SET subtypes, with particular emphasis on
REGION-EQUAL and REGION-CONTAINS-REGION-P.

REGION-EQUAL can be defined as
#+begin_src lisp
  (and (region-contains-region-p region1 region2)
       (region-contains-region-p region2 region1))
#+end_src
.

REGION-CONTAINS-POSITION-P can reasonably be implemented for any
simple region.  For a STANDARD-REGION-UNION, there is
#+begin_src lisp
  (some (lambda (sub-region)
          (region-contains-position-p sub-region x y))
        (region-set-regions region))
#+end_src
, or a formulation using MAP-OVER-REGION-SET-REGIONS could be used.
For a STANDARD-REGION-INTERSECTION, the use of EVERY instead of SOME
in the example above is sufficient.  For a STANDARD-REGION-DIFFERENCE
with two regions,
#+begin_src lisp
  (and (region-contains-position-p (first sub-regions) x y)
       (not (region-contains-position-p (second sub-regions) x y)))
#+end_src
, with suitable extension for whatever semantic is decided on for a
STANDARD-REGION-DIFFERENCE with more than two regions (assuming that
such a semantic is defined).

REGION-INTERSECTS-REGION-P can be implemented as
#+begin_src lisp
  (eq +nowhere+ (region-intersection region1 region2))
#+end_src
, by a trivial interpretation of its specification.

This leaves REGION-CONTAINS-REGION-P as the "hard" case.  [ FIXME:
Solve the hard case. ]

We begin with the unbounded regions, which are the easy cases:

  - REGION-CONTAINS-REGION-P for a super-region or sub-region that is
NOWHERE is never true.
  - REGION-CONTAINS-REGION-P for a super-region that is EVERYWHERE is
only false if the sub-region is NOWHERE.
  - REGION-CONTAINS-REGION-P for a sub-region that is EVERYWHERE is
only true if the super-region is EVERYWHERE.

REGION-CONTAINS-REGION-P is never true if the dimensionality of the
sub-region is greater than the dimensionality of the super-region.
This means that a sub-region that is a PATH or a REGION-SET of PATHs
will never be contained in a super-region that is a POINT or a
REGION-SET of POINTs, and the same logic applies with AREAs as
sub-regions and POINTs or PATHs as super-regions.

REGION-CONTAINS-REGION-P for a sub-region that is comprised of POINTs
is trivially implemented by REGION-CONTAINS-POSITION-P.

[ Can we just use (region-difference sub-region super-region) to do
all this, and if the result is NOWHERE then the sub-region is
contained entirely within the super-region? ]

** Dimensionality conservation

When composing two regions, or creating a new "simple" region,
dimensionality is "conserved" in a manner which does not correspond
with set theory.  If an entity normally having dimensionality $m$ is
specified with parameters that would cause the entity to have
dimensionalty $n$ where $n<m$, then the empty region is produced
instead.

This means that any attempt to create a PATH with length zero (thus, a
point) will produce the empty region, and likewise an AREA with area
zero (thus, a point or a line).

Since dimensionality conservation applies to region composition, the
intersection of two PATHs is always the empty region (since it would
normally be a set of POINTs, and points have a lower dimensionality
than PATHs).

** Region composition

There are three region composition operators.  These are:

  - REGION-UNION: If passed two regions with differing dimensionality,
    returns the region with the highest dimensionality.  If passed two
    regions with the same dimensionality, returns a region which
    contains all of the points in both regions.  This region will be a
    simple region, a REGION-SET, or a STANDARD-REGION-UNION (which is
    a specific subclass of REGION-SET).
  - REGION-INTERSECTION: If passed two regions with differing
    dimensionality, returns the part of the lower-dimensional region
    that is contained within the higher-dimensional region.  If passed
    two regions with the same dimensionality, returns a region
    containing the parts [ FIXME: Figure out how to express this
    properly. ]
  - REGION-DIFFERENCE: [ FIXME: This one is even worse! ]

Note that the ability for two of these functions to return a
REGION-SET as well as a specific subclass of REGION-SET is to specify
a preferred subclass of REGION-SET when dealing with composing simple
regions, while still allowing arbitrary REGION-SET objects to be
returned "unscathed", as it were.  The reason for disallowing general
region sets from REGION-INTERSECTION is unknown (consider the
intersection of two unions of rectangles).

** Composite regions

A composite region may be described either by a simple region or by a
set of simple regions related by some operation (typically UNION,
although working with ELLIPSEs requires that there be support for
INTERSECTION and DIFFERENCE operations in REGION-SETs).

All of the regions in a REGION-SET will have the same dimensionality,
due to dimensionality conservation during composition.

** Composition of unbounded regions

REGION-SET is a subclass of BOUNDING-RECTANGLE, implying that
composite regions are bounded regions.  This means that DIFFERENCE
from +EVERYWHERE+ of any bounded region cannot be supported, as the
result would be unbounded.  CLIM II specification, section 3.1.2,
paragraph three states that an implementation must signal an error (of
unspecified type) when such a composition is attempted.

The following table shows the effects of unbounded regions in
composition, where "any" is any region whatsoever, "bounded" is any
bounded region, and "error" means that the implementation is obliged
to signal an error should such a composition be attempted.

| Operation    | Region-1   | Region-2   | Result     |
|--------------+------------+------------+------------|
| UNION        | EVERYWHERE | any        | EVERYWHERE |
|              | any        | EVERYWHERE | EVERYWHERE |
| INTERSECTION | EVERYWHERE | any        | Region-2   |
|              | any        | EVERYWHERE | Region-1   |
| DIFFERENCE   | EVERYWHERE | EVERYWHERE | NOWHERE    |
|              | EVERYWHERE | NOWHERE    | EVERYWHERE |
|              | EVERYWHERE | bounded    | error      |
|              | NOWHERE    | any        | NOWHERE    |

Note, however, that REGION-INTERSECTION of EVERYWHERE with a
STANDARD-REGION-UNION or a STANDARD-REGION-DIFFERENCE is required to
return a STANDARD-REGION-INTERSECTION, presumably with EVERYWHERE as
one of the regions in the intersection.  As the other two composition
operations allow the return of any REGION-SET class, it could be
argued that this is a bug in the specification of REGION-INTERSECTION.

** Multi-region compositions

Each composition only deals with two regions at a time, but these
regions may themselves be composite regions.  It is clear that the
UNION and INTERSECTION operators both commutative and associative,
while the DIFFERENCE operator is neither.  The question thus arises,
can composite regions have a "normal form", and what could/should it
be?

We begin by enumerating cases.

The UNION of R1 with UNION(R2,R3) produces UNION(R1,R2,R3).

The INTERSECTION of R1 with INTERSECTION(R2,R3) produces
INTERSECTION(R1,R2,R3).

The UNION of R1 with INTERSECTION(R2,R3) produces either
UNION(R1,INTERSECTION(R2,R3)) or
INTERSECTION(UNION(R1,R2),UNION(R1,R3)).

The INTERSECTION of R1 with UNION(R2,R3) produces either
INTERSECTION(R1,UNION(R2,R3)) or
UNION(INTERSECTION(R1,R2),INTERSECTION(R1,R3)).

The UNION of R1 with DIFFERENCE(R2,R3) produces
UNION(R1,DIFFERENCE(R2,R3)) or
DIFFERENCE(UNION(R1,R2),DIFFERENCE(R3,R1)).

The INTERSECTION of R1 with DIFFERENCE(R2,R3) produces
INTERSECTION(R1,DIFFERENCE(R2,R3)) or
DIFFERENCE(INTERSECTION(R1,R2),R3).

This becomes more interesting when one realizes that some of the
"inner" UNION or INTERSECTION operations may result in a simple region
instead of a composite, thus simplifying the structure of the overall
region.

DIFFERENCE, unlike UNION or INTERSECTION, is neither associative nor
commutative.

The DIFFERENCE of R2 from R1 produces DIFFERENCE(R1,R2) or
DIFFERENCE(R1,INTERSECTION(R1,R2)).

The DIFFERENCE of DIFFERENCE(R2,R3) from R1 produces
DIFFERENCE(R1,DIFFERENCE(R2,R3)) or [ FIXME: Finish this? ]

There is a cross-product effect with UNION and INTERSECTION:

[ FIXME: Figure this out, too. ]

** Compositions that result in non-simple regions

All discontiguous regions are represented by REGION-SETs, and can only
be produced by composing simple regions.  Contiguous regions will tend
to be prepresented by simple regions, but there are several
exceptions.

  - The UNION of two contiguous PATH regions may not be representable
    as a single PATH (either a LINE, a POLYLINE, or an
    ELLIPTICAL-ARC).
  - Non-rectangular regions produced by composing axis-aligned
    RECTANGLEs are (as specified) required to be represented as
    REGION-SETs of axis-aligned RECTANGLEs.  [ FIXME: Possibly as
    UNIONs? ]
  - Any region which has a section of the arc of an ELLIPSE as part of
    its boundary must either be an ELLIPSE or a REGION-SET that
    involves an ELLIPSE at some level.

All other cases are either discontiguous regions or may be represented
as POLYGONs.  [ FIXME: Can they really?  DIFFERENCE an interior chunk
out of a POLYGON.  I suppose this could be covered by the polygon
having an edge leading inward, carving out the missing chunk, and then
traversing outward along the same edge...  But this means that the
odd-even winding rule and a selection of a suitable point at infinity
could show that some of the supposedly-interior points along the
doubled edge only intersect an even number of edge segments. ]

** Bounded simple regions

[ FIXME: Go over this section and render the wording of the various
composition cases and results consistent. ]

*** Dimensionality zero

The only bounded simple region of dimensionality zero is the POINT.

The composition operations for distinct points P1 and P2 are:

  - The UNION of P1 with P1 is P1.
  - The UNION of P1 with P2 is UNION(P1,P2).
  - The INTERSECTION of P1 and P1 is P1.
  - The INTERSECTION of P1 and P2 is NOWHERE.
  - The DIFFERENCE of P1 from P1 is NOWHERE.
  - The DIFFERENCE of P2 from P1 is P1.

*** Dimensionality one

Simple regions of dimensionality one are PATHs.  These are
ELLIPTICAL-ARCs, POLYLINEs, and LINEs.  LINEs are a special case of
POLYLINEs with only one segment, thus we may consider POLYLINEs to be
the UNION of the LINEs representing each of their segments, and need
consider them no further.

The simple cases for composition operations for an ELLIPTICAL-ARC A1
and a LINE L1 are:

  - The UNION of A1 with L1 is UNION(A1,L1).
  - The INTERSECTION of A1 and L1 is NOWHERE.
  - The DIFFERENCE of L1 from A1 is A1.
  - The DIFFERENCE of A1 from L1 is L1.

This is because a LINE and an ELLIPTICAL-ARC cannot overlap at
anything other than points, which are eliminated due to dimensionality
conservation.

The remaining cases are more involved.  We begin with the cases for
distinct LINEs L1 and L2.

For two distinct LINEs L1 and L2, there are five possibilities:

  1. Both endpoints of L1 are present in L2.
  2. Both endpoints of L2 are present in L1, and neither is an
     endpoint of L1.
  3. Both endpoints of L2 are present in L1, and one is an endpoint of
     L1.
  4. One endpoint of L1 is present in L2 and one endpoint of L2 is
     present in L1.
  5. The lines do not overlap (they may intersect, but dimensionality
     conservation treats this as yielding NOWHERE).

For UNION, the results are as follows:

  - In case 1, the UNION of L1 with L2 is L2.
  - In case 2, the UNION of L1 with L2 is L1.
  - In case 3, the UNION of L1 with L2 is L1.
  - In case 4, the UNION of L1 with L2 is a new LINE with the
    endpoints from L1 and L2 that are not present in the other.
  - In case 5, the UNION of L1 with L2 is a STANDARD-REGION-UNION with
    L1 and L2 as the REGION-SET-REGIONS.

For INTERSECTION, the results are as follows:

  - In case 1, the INTERSECTION of L1 and L2 is L1.
  - In case 2, the INTERSECTION of L1 and L2 is L2.
  - In case 3, the INTERSECTION of L1 and L2 is L2.
  - In case 4, the INTERSECTION of L1 and L2 is a new LINE with the
    endpoints from L1 and L2 that are present in the other.
  - In case 5, the INTERSECTION of L1 and L2 is NOWHERE.

For DIFFERENCE, the results are as follows:

  - In case 1, the DIFFERENCE of L2 from L1 is NOWHERE.
  - In case 2, the DIFFERENCE of L2 from L1 is a STANDARD-REGION-UNION
    with the two new, disjoint (non-overlapping) LINEs, each with one
    endpoint from L1 and one endpoint from L2.
  - In case 3, the DIFFERENCE of L2 from L1 is a new LINE with the
    endpoint from L1 that is not present in L2 and the endpoint from
    L2 that is not an endpoint in L1.
  - In case 4, the DIFFERENCE of L2 from L1 is a new LINE with the
    endpoint from L1 that is not present in L2 and the endpoint from
    L2 that is present in L2.
  - In case 5, the DIFFERENCE of L2 from L1 is L1.

And, finally, the cases for ELLIPTICAL-ARCs.

We begin by asserting that there must be a "normal form" for the
"radius vectors" (vectors that specify the bounding parallelogram of
the ellipse).  We do not at this point care what this normal form is,
only that it exist and be easy to compute given an aribitrary set of
radius vectors.  In the discussion below, whenever "radius vectors"
are referred to it is assumed that they are in normal form.

For two distinct ELLIPTICAL-ARCs A1 and A2, there are $n$
possibilities:

[ FIXME: Figure out the combinations for different combinations of
start and end angles.  These will undoubtably be similar to the LINE
cases above. ]

  1. The radius vectors and center point of A1 are not all equal to
     the radius vectors and center point of A2.
  2. A1 is a "full ellipse".
  3. A2 is a "full ellipse".

Note that the combination of equal radius vectors, center point, and
start and end angles implies that two ELLIPTICAL-ARCs represent the
same region.

For UNION, the results are as follows:

  - In case 1, the UNION of A1 with A2 is a STANDARD-REGION-UNION with
    A1 and A2 as REGION-SET-REGIONS.
  - In case 2, the UNION of A1 with A2 is A1.
  - In case 3, the UNION of A1 with A2 is A2.

For INTERSECTION, the results are as follows:

  - In case 1, the INTERSECTION of A1 and A2 is NOWHERE.
  - In case 2, the INTERSECTION of A1 and A2 is A2.
  - In case 3, the INTERSECTION of A1 and A2 is A1.

For DIFFERENCE, the results are as follows:

  - In case 1, the DIFFERENCE of A2 from A1 is A1.
  - In case 2, the DIFFERENCE of A2 from A1 is a new ELLIPTICAL-ARC
    with the same radius vectors and center point as A1, a start-angle
    of the end-angle of A2 and an end-angle of the start-angle of A2.
  - In case 3, the DIFFERENCE of A2 from A1 is NOWHERE.

*** Dimensionality two

Simple regions of dimensionality two are AREAs, and also are the area
where we run into trouble.  These are ELLIPSEs, POLYGONs, and
RECTANGLEs.

Any composition operation involving two POLYGONs will produce a result
that is either another POLYGON (if the resulting region is
contiguous), a UNION of two polygons (if the resulting region is
discontiguous), or NOWHERE.  Thus, we need only concern ourselves with
the cases involving ELLIPSEs.

Further, the troublesome cases for ELLIPSEs all occur when the part of
the perimiter described by an ELLIPTICAL-ARC is, in some definable
sense, "exposed".  In all other cases, the ELLIPSE may be treated as a
POLYGON (as it is either filled space, or the straight sides of the
"pie slice" area for the start and end angles).

In the troublesome cases for ELLIPSEs, we either /must/ use a
REGION-SET object or may "luck out" and be able to use a straight-up
ELLIPSE object (consider fully bisecting an ellipse through its center
point).  For all other cases, we end up with sets of POLYGONs at
worst.