ConvexCombiner.mesa
Last Edited by: Arnon, November 26, 1985 10:49:05 am PST
Combiner for Convex EuclideanGraphs.
DIRECTORY
IO,
EuclideanGraphs,
ConvexEuclideanGraphs;
ConvexCombiner: CEDAR DEFINITIONS
Combines two ConvexEuclideanGraphs with client data at edges only (not vertices).
= BEGIN OPEN EG: EuclideanGraphs, CEG: ConvexEuclideanGraphs;
Combiner Data Structures
Vertex: TYPE = EG.Vertex; -- A single (outline) vertex is sufficient representation for a combiner database, since ConvexEuclideanGraphs are assumed to be connected, so a single vertex is sufficient entree into the graph.
Point: TYPE = EG.Point;
Verbosity: TYPE = CEG.Verbosity;
Client Data Procedure Types
ClientDataCombiner: TYPE = PROC[currentClientdata, inputClientdata: REF] RETURNS [resultClientData: REF]; -- note well the order of input parameters.
IF currentregiondata=NIL THEN RETURN[ inputregiondata ];
IF inputregiondata=NIL THEN RETURN[ currentregiondata ]; -- all DataCombiner's should contain these lines: our convention is that NIL data combined with any data returns that data.
ClientDataEqual: TYPE = PROC [clientData1, clientData2: REF] RETURNS [BOOL];
IF data1=NIL OR data2=NIL THEN RETURN[data1 = NIL AND data2 = NIL]; -- all DataEqual's should contain this test
IsAProc: TYPE = CEG.IsAProc;
Main procedures
Combiner: PROC[currentEnd, inputEnd: Vertex, inputClientData: REF, clientDataCombiner: ClientDataCombiner, verbosity: Verbosity ← NIL] RETURNS [combinedEnd: Vertex];
currentEnd is a vertex on the (convex) outline of the current figure. inputEnd is a vertex on the input polygon. combinedEnd is a vertex on the (convex) outline of the combined figure.
CombineGeometry: PROC[currentEnd, inputEnd: Vertex, setIntersectionPolygonEdges: BOOL ← TRUE, verbosity: Verbosity ← NIL] RETURNS [combinedEnd, intersectionPolyStart, intersectionPolyEnd: Vertex];
currentEnd is a vertex on the (convex) outline of the current figure. inputEnd is a vertex on the input polygon. combinedEnd is a vertex on the (convex) outline of the combined figure. [intersectionPolyStart, intersectionPolyEnd] is a (directed) edge in the new (i.e. combined) geometry which is contained in the intersection polygon (of current figure and input polygon), and such that the interior of the intersection polygon lies to its left. If the intersection polygon is empty, then both intersectionPolyStart and intersectionPolyEnd are set to NIL.
If setIntersectionPolygonEdges, then CombineGeometry sets the intersectionPolygonEdge fields of all (directed) edges in the new (i.e. combined) geometry which are contained in the intersection polygon (of current figure and input polygon), and such that the interior of the intersection polygon lies to their left. Although this functionality is provided as an essential preprocessing step for CombineClientData, note that it is a purely geometrical operation. It can be undone with ClearIntersectionPolygonEdges.
CombineClientData: PROC[ intersectionPolyStart, intersectionPolyEnd: Vertex, inputClientData: REF, clientDataCombiner: ClientDataCombiner, verbosity: Verbosity ← NIL];
[intersectionPolyStart, intersectionPolyEnd] is a counterclockwise oriented (directed) edge in the current (i.e. combined) geometry which is contained in the intersection polygon (of current figure and input polygon), and such that the interior of the intersection polygon lies to its left. inputClientData is the state of the input polygon. clientDataCombiner is the rule for state combination.
The leftState fields of the edges of all polygons interior to the intersection polygon are set to the result of state combining inputClientData with the states those polygons had in the current figure. The algorithm uses Depth First Search.
CombineClientData assumes that the intersectionPolygonEdge fields of all (directed) edges in the new (i.e. combined) geometry which are contained in the intersection polygon (of current figure and input polygon), and such that the interior of the intersection polygon lies to their left, are set. It doesn't clear them.
Combiner cases
InputIntersectsCurrent: PROC [inputStart, inputEnd, currentVertex: Vertex, verbosity: Verbosity ← NIL] RETURNS [outlineStart, outlineEnd: Vertex ← NIL, intersectionPolyStart, intersectionPolyEnd: Vertex];
Starting from the first intersection point currentVertex, iterates overlap handling and lens decompositions until we return to first intersection point.
Assumes that there is at least one lens (case of complete overlap of input polygon and current outline handled by main loop of CombineGeometry), so that intersectionPolyStart and intersectionPolyEnd get set.
If any lenses in exterior, then [outlineStart, outlineEnd] is an edge on the new outline formed; otherwise outlineStart = outlineEnd = NIL.
InputExternalToCurrent: PROC[ currentStart, currentEnd, inputStart, inputEnd: Vertex, currentOutlineCOM, inputCOM: Point, verbosity: Verbosity ← NIL] RETURNS [outlineStart, outlineEnd: Vertex];
[currentStart, currentEnd] is a counterclockwise oriented edge on the (convex) outline of the current figure. [inputStart, inputEnd] is a counterclockwise oriented edge on the input polygon. [currentStart, currentEnd] defines a sector of the current figure in (the closure of) which inputStart lies. [outlineStart, outlineEnd] is a counterclockwise oriented edge on the outline which results from joining currentStart and currentEnd to inputStart with edges.
Advance [inputStart, inputEnd] until it defines sector (in closure of which) currentOutlineCOM lies (this is to insure that inputStart is not on the "backside" of the input polygon with respect to the current outline). Then advance [currentStart, currentEnd] until it defines a sector of the current figure in (the closure of) which inputStart lies.
Assert inputStart and currentEnd are mutually visible; join with an edge pair. While inputEnd to right of line [currentEnd, inputStart]: [currentEnd, inputStart].exterior ← FALSE, advance [inputStart, inputEnd], join currentEnd and inputStart.
PolygonEnclosesPolygon: PROC[ innerCOM: Point, innerStart, innerEnd, outerStart, outerEnd: Vertex, verbosity: Verbosity ← NIL];
[innerStart, innerEnd] is a counterclockwise oriented edge on the inner polygon. [outerStart, outerEnd] is a counterclockwise oriented edge on the outer polygon.
The algorithm is: pick a random vertex on outer polygon (we pick outerStart), pinwheel inner polygon until wedge for that vertex is found. Back up along inner polygon until last vertex "visible" from outerStart is found; then add a "cone" of edges from outerStart to vertices of inner polygon until a convex outline is obtained. This leaves a "lens-like region" (i.e. a region which is a lens by some suitably general definition of lens) to be decomposed into convex polygons; we do so by applying the existing lens decomposition procedure.
Convex decomposers and overlap handlers
HandleVertexContact: PROC [firstIntersection, inputStart, inputEnd, currentVertex: Vertex, verbosity: Verbosity ← NIL] RETURNS [returnedToFirstIntersection: BOOL, nextLensInExterior: BOOL ← FALSE, currentCommonVertex, nextCurrentVertex, nextInputVertex: Vertex ← NIL];
Moves forward until start of next lens found or returnedToFirstIntersection (if latter, then must occur by means of overlap).
[inputStart, inputEnd] is outgoing edge of input polygon. It is assumed that inputStart and currentVertex have same coordinates and have not yet been merged.
If end of overlap chain is firstIntersection, then returnedToFirstIntersection ← TRUE and other return parms defaulted. If not, then returnedToFirstIntersection ← FALSE, nextLensInExterior set appropriately, currentCommonVertex is start of next lens, and nextCurrentVertex and nextInputVertex are next vertices that start off the lens (which is on inner edge and which on outer depends on nextLensInExterior).
LensDecomposition: PROC[firstIntersection, lensStart, innerEnd, outerEnd: Vertex, lensInExterior: BOOL, setIntersectionPolygonEdges: BOOL ← TRUE, verbosity: Verbosity ← NIL] RETURNS [returnedToFirstIntersection: BOOL, innerPrevious, innerCommon, outerPrevious, outerCommon: Vertex];
Each of the lenses that two polygons give rise to is external to one of them and internal to the other (in fact, a lens of two polynomials p1 and p2 can be defined as a connected component of p1 - p2 or p2 - p1). The polygon for which the lens is external is said to be the inner polygon of the lens; the other is the outer polygon of the lens.
firstIntersection is the intersection point which started the first lens. [lensStart, innerEnd] is an edge of the polygon which is coming from outer and going inner. [lensStart, outerEnd] is an edge of the polygon which is coming from inner and going outer. lensInExterior specifies whether the forthcoming lens is in the exterior of the current figure, i.e. whether the input polygon is outer or not.
returnedToFirstIntersection tells us whether we have come back to the first lens. innerCommon and outerCommon have same coordinates, namely the point which terminates the lens. They are distinct vertices, however, unless returnedToFirstIntersection, in which case innerCommon = outerCommon.
BoundaryContactOnly: PROC[inputStart, inputEnd, currentVertex: Vertex, verbosity: Verbosity ← NIL];
Similar to HandleVertexContact. Handles contact which may be as little as a single vertex, or a string of edges. [inputStart, inputEnd] is outgoing edge of input polygon. It is assumed that inputStart and currentVertex have same coordinates and have not yet been merged.
While overlap do: set LRE fields FALSE and states to inputClientData, of outward-facing edges of current outline.
Structure Cleaner
SimpleCleaner: PROC [currentEnd: Vertex, clientDataEqual: ClientDataEqual, verbosity: Verbosity ← NIL];
END.