ConvexCombinerImpl.mesa
Last Edited by: Arnon, June 20, 1985 4:44:33 pm PDT
DIRECTORY
IO,
Rope,
RatNums,
EuclideanGraphs,
ConvexEuclideanGraphs,
ConvexCombiner;
ConvexCombinerImpl: CEDAR PROGRAM
IMPORTS IO, RatNums, EuclideanGraphs, ConvexEuclideanGraphs
EXPORTS ConvexCombiner
= BEGIN OPEN RN: RatNums, EG: EuclideanGraphs, CEG: ConvexEuclideanGraphs, ConvexCombiner;
Main procedures
Combiner: PUBLIC 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.
intersectionPolyStart, intersectionPolyEnd: Vertex;
[combinedEnd, intersectionPolyStart, intersectionPolyEnd] ← CombineGeometry[currentEnd, inputEnd, TRUE, verbosity];
IF intersectionPolyStart#NIL THEN {
CombineClientData[intersectionPolyStart, intersectionPolyEnd, inputClientData, clientDataCombiner, verbosity];
CEG.ClearGraphIPEdges[intersectionPolyStart, intersectionPolyEnd];
}; -- assume no intersectionPolygonEdge fields set if intersectionPolyStart = NIL.
};
CombineGeometry: PUBLIC 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 intersectionPolyStart ← intersectionPolyEnd ← NIL.
Either currentEnd or inputEnd may be NIL, in which case the other is returned. If non-NIL, it is assumed that each structure has at least three vertices.
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, 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 ClearGraphIPEdges.
currentStart, inputStart, combinedStart: Vertex;
currentOutlineCOM, inputCOM: Point;
pointSectorStatus: CEG.PointSectorRelation;
polygonCompareStatus: CEG.ConvexPolygonCompareStatus;
firstInputVertex: Vertex;
done: BOOL ← FALSE;
currentPrevious, currentCommon, currentNext, inputPrevious, inputCommon, inputNext: Vertex;
inputClientData: REF;
startToEnd, endToStart: EG.Adjacency;
outlineStart, outlineEnd, newOutlineStart, newOutlineEnd: Vertex;
Check for empty arguments, valid inputs.
IF inputEnd = NIL THEN RETURN[currentEnd, NIL, NIL];
IF currentEnd = NIL THEN RETURN[inputEnd, NIL, NIL];
IF NOT CEG.ThreeOrMoreVertices[currentEnd] OR NOT CEG.ThreeOrMoreVertices[inputEnd] THEN ERROR;
Insure that current figure and input polygon have same setting of vertex visited flag. Adjacency flag fields (leftRegionVisited, intersectionPolygonEdge) assumed to be cleared (set to FALSE) in both current figure and input polygon.
IF currentEnd.visited # inputEnd.visited THEN EG.SetFigureVisitedValues[inputEnd, currentEnd.visited];
Find preceding vertices on outline so that [currentStart, currentEnd] is a counterclockwise oriented edge on the (convex) outline of the current figure, and [inputStart, inputEnd] is a counterclockwise oriented edge on the input polygon. Get client data for input polygon
currentStart ← CEG.SpecialPreviousOutlineVertex[currentEnd];
firstInputVertex ← inputStart ← CEG.SpecialPreviousOutlineVertex[inputEnd];
[ startToEnd, endToStart ] ← EG.FindAdjacency[ inputStart, inputEnd ];
inputClientData ← CEG.GetEdgeClientData[startToEnd];
Centers of mass of both figures, and locate wedge of current figure outline that contains vertex inputStart of the input polygon.
currentOutlineCOM ← CEG.CenterOfMass[ currentStart, currentEnd, TRUE];
inputCOM ← CEG.CenterOfMass[ inputStart, inputEnd, FALSE];
[pointSectorStatus, currentStart, currentEnd] ← CEG.FindSubtendForPoint[ currentStart, currentEnd, currentOutlineCOM, inputStart.coordinates, TRUE];
"Cache" where on the current outline the input activity is taking place. If combinedEnd is not subsequently reassigned, we will return this value.
outlineStart ← currentStart; outlineEnd ← combinedEnd ← currentEnd;
WHILE NOT done DO
SELECT pointSectorStatus FROM
SUBTENDINTERIOR, RIGHTRAYINTERIOR, LEFTRAYINTERIOR => {
pointLineRelation: EG.PointLineRelation;
[polygonCompareStatus, currentPrevious, currentCommon, currentNext, inputPrevious, inputCommon, inputNext] ← CEG.ConvexPolygonCompare[
innerCOM: currentOutlineCOM,
innerStart: currentStart,
innerEnd: currentEnd,
innerOutline: TRUE,
outerStart: inputStart,
outerEnd: inputEnd,
checkExternal: TRUE
];
SELECT polygonCompareStatus FROM
Intersection => {
pointLineRelation ← EG.PointLineTest[currentCommon.coordinates, currentPrevious.coordinates, inputNext.coordinates];
SELECT pointLineRelation FROM
ONLINE, LEFTOFLINE => {
outlineStart ← currentCommon; outlineEnd ← currentNext;
BoundaryContactOnly[inputCommon, inputNext, currentCommon, verbosity];
[combinedStart, combinedEnd] ← CEG.ConvexifyOutline[outlineStart, outlineEnd, verbosity];
RETURN[combinedEnd, NIL, NIL];
};
RIGHTOFLINE => {
[outlineStart, outlineEnd, intersectionPolyStart, intersectionPolyEnd] ← InputIntersectsCurrent[inputCommon, inputNext, currentCommon, verbosity];
[combinedStart, combinedEnd] ← CEG.ConvexifyOutline[outlineStart, outlineEnd, verbosity];
RETURN[combinedEnd, intersectionPolyStart, intersectionPolyEnd];
};
ENDCASE;
The validity of this EG.PointLineTest branching follows from the facts that inputPrevious = inputStart is outside the current outline, and input polygon is convex.
};
Encloses => {
Set intersectionPolygonEdge fields of "inward-facing" edges, and clear leftRegionExterior and set clientData fields, of "outward-facing" edges, on outline of current figure
CEG.SetPolygonIPEdges[currentStart, currentEnd, TRUE];
CEG.SetOutwardOutlineEdgeFields[currentStart, currentEnd, FALSE, FALSE, inputClientData];
Decompose the annulus formed by input polygon - current outline
PolygonEnclosesPolygon[currentOutlineCOM, currentStart, currentEnd, inputStart, inputEnd, verbosity]; -- should pass in data field values???
RETURN [inputEnd, currentStart, currentEnd];
};
External => {
[outlineStart, outlineEnd] ← InputExternalToCurrent[currentStart, currentEnd, inputStart, inputEnd, currentOutlineCOM, inputCOM, verbosity];
[combinedStart, combinedEnd] ← CEG.ConvexifyOutline[outlineStart, outlineEnd, verbosity];
RETURN [combinedEnd, NIL, NIL];
};
ENDCASE;
};
SECTORINTERIOR, RIGHTSPOKEINTERIOR, LEFTSPOKEINTERIOR, EQUALCOM => {
inputStartStatus: CEG.PointSectorRelation;
internalStart, internalEnd: Vertex;
found: BOOL;
1. Search for containing internal polygon.
[inputStartStatus, internalStart, internalEnd] ← CEG.FindInternalPolygonForPoint[currentStart, currentEnd, inputStart.coordinates];
2. If on boundary of containing internal polygon, call InputIntersectsCurrent.
SELECT inputStartStatus FROM
EQUALRIGHTVERTEX => {
currentCommon ← internalStart;
[newOutlineStart, newOutlineEnd, intersectionPolyStart, intersectionPolyEnd] ← InputIntersectsCurrent[inputStart, inputEnd, currentCommon, verbosity];
IF newOutlineStart#NIL THEN { outlineStart ← newOutlineStart; outlineEnd ← newOutlineEnd };
[combinedStart, combinedEnd] ← CEG.ConvexifyOutline[outlineStart, outlineEnd, verbosity];
RETURN [combinedEnd, intersectionPolyStart, intersectionPolyEnd];
};
EQUALLEFTVERTEX => {
currentCommon ← internalEnd;
[newOutlineStart, newOutlineEnd, intersectionPolyStart, intersectionPolyEnd] ← InputIntersectsCurrent[inputStart, inputEnd, currentCommon, verbosity];
IF newOutlineStart#NIL THEN { outlineStart ← newOutlineStart; outlineEnd ← newOutlineEnd };
[combinedStart, combinedEnd] ← CEG.ConvexifyOutline[outlineStart, outlineEnd, verbosity];
RETURN [combinedEnd, intersectionPolyStart, intersectionPolyEnd];
};
POLYGONEDGEINTERIOR => {
currentCommon ← CEG.InsertVertexInEdges[internalStart, internalEnd, inputStart.coordinates];
[newOutlineStart, newOutlineEnd, intersectionPolyStart, intersectionPolyEnd] ← InputIntersectsCurrent[inputStart, inputEnd, currentCommon, verbosity];
IF newOutlineStart#NIL THEN { outlineStart ← newOutlineStart; outlineEnd ← newOutlineEnd };
[combinedStart, combinedEnd] ← CEG.ConvexifyOutline[outlineStart, outlineEnd, verbosity];
RETURN [combinedEnd, intersectionPolyStart, intersectionPolyEnd];
};
ENDCASE;
3. If in interior of containing internal polygon, find a vertex internalStart of internal polygon which lies in exterior of input polygon. Set inputStart, inputEnd to edge defining wedge containing internalStart.
[found, inputStart, inputEnd, internalStart, internalEnd] ← CEG.VertexExternalToPolygon[inputCOM, inputStart, inputEnd, internalStart, internalEnd];
IF NOT found THEN ERROR;
4. Compare containing internal and input polygons.
[polygonCompareStatus, inputPrevious, inputCommon, inputNext, currentPrevious, currentCommon, currentNext] ← CEG.ConvexPolygonCompare[
innerCOM: inputCOM,
innerStart: inputStart,
innerEnd: inputEnd,
innerOutline: FALSE,
outerStart: internalStart,
outerEnd: internalEnd,
checkExternal: FALSE
];
SELECT polygonCompareStatus FROM
Intersection => {
[newOutlineStart, newOutlineEnd, intersectionPolyStart, intersectionPolyEnd] ← InputIntersectsCurrent[inputCommon, inputNext, currentCommon, verbosity];
IF newOutlineStart#NIL THEN { outlineStart ← newOutlineStart; outlineEnd ← newOutlineEnd };
[combinedStart, combinedEnd] ← CEG.ConvexifyOutline[outlineStart, outlineEnd, verbosity];
RETURN [combinedEnd, intersectionPolyStart, intersectionPolyEnd];
};
Encloses => {
currentInternalClientData: REF;
Set clientData of input polygon to state of internal polygon of current figure that encloses it. This is the right thing to do since CombineClientData assumes that interior of the intersection polygon has current state, and will combine that with input polygon state. Hence CombineGeometry has side effects with respect to state (this is not the only example of that by any means).
[startToEnd, endToStart] ← EG.FindAdjacency[internalStart, internalEnd];
currentInternalClientData ← CEG.GetEdgeClientData[startToEnd];
CEG.SetPolygonClientData[inputStart, inputEnd, currentInternalClientData];
Set intersectionPolygonEdge fields of "inward-facing" edges, and clear leftRegionExterior and set clientData fields, of "outward-facing" edges, on input polygon
CEG.SetPolygonIPEdges[inputStart, inputEnd, TRUE];
CEG.SetOutwardOutlineEdgeFields[inputStart, inputEnd, FALSE, FALSE, currentInternalClientData];
Decompose annulus formed by current internal polygon - input polygon.
PolygonEnclosesPolygon[inputCOM, inputStart, inputEnd, internalStart, internalEnd, verbosity];
RETURN [combinedEnd, inputStart, inputEnd]; -- leave combinedEnd ← currentEnd, its initial assignment
};
ENDCASE => ERROR;
};
POLYGONEDGEINTERIOR, EQUALRIGHTVERTEX, EQUALLEFTVERTEX => {
[inputStart, inputEnd] ← CEG.StepVertex[ inputStart, inputEnd, TRUE ]; -- move to next edge of input polygon, looking for first one that goes off the outline of current figure.
IF inputStart = firstInputVertex THEN
done ← TRUE
ELSE
[pointSectorStatus, currentStart, currentEnd] ← CEG.FindSubtendForPoint[ currentStart, currentEnd, currentOutlineCOM, inputStart.coordinates, TRUE];
};
ENDCASE => ERROR;
ENDLOOP;
If we arrive here, then input polygon is identical with outline of current figure. Set all edges of current figure outline to be intersection polygon edges.
CEG.SetPolygonIPEdges[currentStart, currentEnd, TRUE];
RETURN [currentEnd, currentStart, currentEnd];
};
CombineClientData: PUBLIC PROC[intersectionPolyStart, intersectionPolyEnd: Vertex, inputClientData: REF, clientDataCombiner: ClientDataCombiner, verbosity: Verbosity ← NIL] = {
[intersectionPolyStart, intersectionPolyEnd] is an edge in the current (i.e. combined) geometry which is contained in the intersection polygon (of current figure and input polygon). inputClientData is the clientData of the input polygon. clientDataCombiner is the rule for clientData combination.
CombineClientData assumes that the intersectionPolygonEdge fields of all (directed) intersection polygon edges are set. It doesn't clear them.
The clientData fields of the edges of all polygons internal to the intersection polygon are set to the result of clientData combining inputClientData with the clientData's those polygons had in the current figure. The algorithm is Depth First Search.
currentClientData, combinedClientData: REF;
start: Vertex ← intersectionPolyStart;
end: Vertex ← intersectionPolyEnd;
firstIntersection: Vertex ← start;
startToEnd, endToStart: EG.Adjacency;
outline: BOOL ← FALSE;
IF verbosity#NIL THEN {
verbosity.out.PutF["\nCombineClientData entered with argument [#%g , #%g ]\n", IO.int[start.index], IO.int[end.index] ];
};
[startToEnd, endToStart] ← EG.FindAdjacency[start, end];
currentClientData ← CEG.GetEdgeClientData[startToEnd];
combinedClientData ← clientDataCombiner[currentClientData, inputClientData];
Set clientData and leftRegionVisited fields of edges of this polygon
CEG.SetPolygonClientData[start, end, combinedClientData, TRUE];
Go around edges again; check each to see if an unprocessed polygon lies across it, if so, recursive call on the flipped edge. Don't need to consider first edge since on outermost call, [start, end] is on intersection polygon, and on recursive calls, endToStart.leftRegionVisited will have been set true by the caller.
WHILE end # firstIntersection DO
[start, end] ← CEG.StepVertex[start, end, outline];
[ startToEnd, endToStart ] ← EG.FindAdjacency[ start, end ];
IF NOT CEG.GetEdgeIPEdge[startToEnd] THEN
IF NOT endToStart.visited THEN
CombineClientData[end, start, inputClientData, clientDataCombiner, verbosity];
ENDLOOP;
};
Combiner cases
InputIntersectsCurrent: PUBLIC PROC [inputStart, inputEnd, currentVertex: Vertex, verbosity: Verbosity ← NIL] RETURNS [outlineStart, outlineEnd: Vertex ← NIL, intersectionPolyStart, intersectionPolyEnd: Vertex] ~ {
firstIntersection: Vertex ← currentVertex;
returnedToFirstIntersection: BOOL ← FALSE;
previousCurrentVertex, nextCurrentVertex: Vertex;
lensInExterior: BOOL;
WHILE NOT returnedToFirstIntersection DO
[returnedToFirstIntersection, lensInExterior, currentVertex, nextCurrentVertex, inputEnd] ← HandleVertexContact[firstIntersection, inputStart, inputEnd, currentVertex, verbosity];
IF NOT returnedToFirstIntersection THEN
IF lensInExterior THEN {
outlineStart ← currentVertex; outlineEnd ← inputEnd;
[returnedToFirstIntersection, previousCurrentVertex, currentVertex, inputStart, inputEnd] ← LensDecomposition[ firstIntersection, currentVertex, nextCurrentVertex, inputEnd, lensInExterior, TRUE, verbosity];
}
ELSE
[returnedToFirstIntersection, inputStart, inputEnd, previousCurrentVertex, currentVertex] ← LensDecomposition[ firstIntersection, currentVertex, inputEnd, nextCurrentVertex, lensInExterior, TRUE, verbosity];
IF NOT returnedToFirstIntersection THEN
[inputStart, inputEnd] ← CEG.StepVertex[inputStart, inputEnd, FALSE];
ENDLOOP;
intersectionPolyEnd ← CEG.IPVertexToEdge[firstIntersection];
RETURN[outlineStart, outlineEnd, firstIntersection, intersectionPolyEnd];
};
InputExternalToCurrent: PUBLIC PROC[ currentStart, currentEnd, inputStart, inputEnd: Vertex, currentOutlineCOM, inputCOM: Point, verbosity: Verbosity ← NIL] RETURNS [outlineStart, outlineEnd: Vertex] = {
status: CEG.PointSectorRelation;
pointLineRelation: EG.PointLineRelation;
edge1, edge2: EG.Adjacency;
[status, inputStart, inputEnd] ← CEG.FindSubtendForPoint[inputStart, inputEnd, inputCOM, currentOutlineCOM, TRUE];
[status, currentStart, currentEnd] ← CEG.FindSubtendForPoint[ currentStart, currentEnd, currentOutlineCOM, inputStart.coordinates, TRUE];
CEG.JoinVertices[inputStart, currentEnd, NIL, NIL, FALSE, FALSE, TRUE, TRUE, FALSE, FALSE]; -- Edges [currentEnd, inputStart] are both exterior.
IF verbosity#NIL THEN verbosity.out.PutF["\nInputExternalToCurrent joins vertices #%g and #%g\n", IO.int[currentEnd.index], IO.int[inputStart.index]];
pointLineRelation ← EG.PointLineTest[currentEnd.coordinates, inputStart.coordinates, inputEnd.coordinates];
WHILE pointLineRelation = RIGHTOFLINE DO
[edge1, edge2] ← EG.FindAdjacency[currentEnd, inputStart];
CEG.SetEdgeExterior[edge2, FALSE]; -- [inputStart, currentEnd] has become internal
[edge1, edge2] ← EG.FindAdjacency[inputStart, inputEnd];
CEG.SetEdgeExterior[edge2, FALSE]; -- [inputEnd, inputStart] has become internal
[inputStart, inputEnd] ← CEG.StepVertex[inputStart, inputEnd, FALSE];
CEG.JoinVertices[currentEnd, inputStart, NIL, NIL, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE]; -- [inputStart, currentEnd] is an exterior edge
IF verbosity#NIL THEN verbosity.out.PutF["\nInputExternalToCurrent joins vertices #%g and #%g\n", IO.int[currentEnd.index], IO.int[inputStart.index]];
pointLineRelation ← EG.PointLineTest[currentEnd.coordinates, inputStart.coordinates, inputEnd.coordinates];
ENDLOOP;
RETURN [currentStart, currentEnd]
};
PolygonEnclosesPolygon: PUBLIC PROC[ innerCOM: Point, innerStart, innerEnd, outerStart, outerEnd: Vertex, verbosity: Verbosity ← NIL] = {
pointSectorStatus: CEG.PointSectorRelation;
nextInner, prevInner, thisInner: Vertex;
pointLineRelation: EG.PointLineRelation;
outerClientData: REF;
startToEnd, endToStart: EG.Adjacency;
returnedToFirstIntersection: BOOL ← FALSE;
innerPrevious, innerCommon, outerPrevious, outerCommon: Vertex; -- dummies
Get outer client data
[startToEnd, endToStart] ← EG.FindAdjacency[outerStart, outerEnd];
outerClientData ← CEG.GetEdgeClientData[startToEnd];
Get wedge of inner polygon for outerStart
[pointSectorStatus, innerStart, innerEnd] ← CEG.FindSubtendForPoint[ innerStart, innerEnd, innerCOM, outerStart.coordinates, FALSE];
Back up along inner polygon
nextInner ← innerEnd;
thisInner ← innerStart;
prevInner ← CEG.PreviousOutlineVertex[thisInner, nextInner];
pointLineRelation ← EG.PointLineTest[outerStart.coordinates, thisInner.coordinates, prevInner.coordinates];
WHILE pointLineRelation = LEFTOFLINE DO
nextInner ← thisInner;
thisInner ← prevInner;
prevInner ← CEG.PreviousOutlineVertex[thisInner, nextInner];
pointLineRelation ← EG.PointLineTest[outerStart.coordinates, thisInner.coordinates, prevInner.coordinates];
ENDLOOP;
Go forward along inner polygon, adding cone of edges. It is assumed that clientData and leftRegionExterior fields of previously external (outward-facing) edges of internal polygon have already been updated by caller.
CEG.JoinVertices[thisInner, outerStart, outerClientData, outerClientData];
IF verbosity#NIL THEN verbosity.out.PutF["\nPolygonEnclosesPolygon joins vertices #%g and #%g\n", IO.int[thisInner.index], IO.int[outerStart.index]];
pointLineRelation ← EG.PointLineTest[outerStart.coordinates, thisInner.coordinates, nextInner.coordinates];
WHILE pointLineRelation = RIGHTOFLINE DO
prevInner ← thisInner;
[thisInner, nextInner] ← CEG.StepVertex[thisInner, nextInner, TRUE]; -- outline step, since inner figure could be current figure
CEG.JoinVertices[thisInner, outerStart, outerClientData, outerClientData];
IF verbosity#NIL THEN verbosity.out.PutF["\nPolygonEnclosesPolygon joins vertices #%g and #%g\n", IO.int[thisInner.index], IO.int[outerStart.index]];
pointLineRelation ← EG.PointLineTest[outerStart.coordinates, thisInner.coordinates, nextInner.coordinates];
ENDLOOP;
Lens decomposition to finish
[returnedToFirstIntersection, innerPrevious, innerCommon, outerPrevious, outerCommon] ← LensDecomposition[outerStart, outerStart, thisInner, outerEnd, TRUE, FALSE, verbosity]; -- lensInExterior = TRUE is the right thing, so that we don't set states of "intersection polygon edges". setIntersectionPolygonEdges = FALSE, since we assume already done by caller, and presence of cone makes it tricky in any case.
IF NOT returnedToFirstIntersection THEN ERROR;
};
Convex decomposers and overlap handlers
HandleVertexContact: PUBLIC PROC [firstIntersection, inputStart, inputEnd, currentVertex: Vertex, verbosity: Verbosity ← NIL] RETURNS [returnedToFirstIntersection: BOOL, nextLensInExterior: BOOL ← FALSE, currentCommonVertex, nextCurrentVertex, nextInputVertex: Vertex ← NIL] ~ {
overlap: BOOL;
overlappedCurrentVertex: Vertex;
distStartCurrent, distStartInput: RN.RatNum;
newVertex, tempVertex: Vertex;
thisToNext, nextToThis: EG.Adjacency;
XOR: PROC[a, b: BOOLEAN] RETURNS[BOOLEAN] = {
IF (a AND b) THEN RETURN[FALSE];
IF (a OR b) THEN RETURN[TRUE];
RETURN[FALSE];
};
returnedToFirstIntersection ← FALSE;
nextInputVertex ← inputEnd;
[overlap, overlappedCurrentVertex] ← EG.TestEdgeOverlap[currentVertex, inputEnd];
WHILE overlap AND NOT returnedToFirstIntersection DO
Find out which of overlappedCurrentVertex, inputEnd closer to inputStart, create new vertex if appropriate.
distStartInput ← EG.DistanceSquare[inputStart.coordinates, inputEnd.coordinates];
distStartCurrent ← EG.DistanceSquare[currentVertex.coordinates, overlappedCurrentVertex.coordinates];
SELECT RN.RatNumCompare[distStartInput, distStartCurrent] FROM
ratGreater => {
newVertex ← CEG.InsertVertexInEdges[inputStart, inputEnd, overlappedCurrentVertex.coordinates];
nextInputVertex ← inputEnd;
inputEnd ← newVertex;
nextCurrentVertex ← overlappedCurrentVertex;
};
ratEqual => {
nextInputVertex ← CEG.NextPolygonVertex[inputStart, inputEnd]; -- meaningless if returnedToFirstIntersection; that's ok.
nextCurrentVertex ← overlappedCurrentVertex;
};
ratLess => {
newVertex ← CEG.InsertVertexInEdges[currentVertex, overlappedCurrentVertex, inputEnd.coordinates];
nextCurrentVertex ← newVertex;
nextInputVertex ← CEG.NextPolygonVertex[inputStart, inputEnd];
};
ENDCASE;
Split off all adjacencies of inputStart other than edges [inputStart, inputEnd].
IF EG.CountAdjacencies[inputStart] > 1 THEN {
tempVertex ← EG.SplitVertex[inputStart, inputEnd];
EG.MergeVertices[currentVertex, tempVertex];
};
Delete edges [inputStart, inputEnd] from input polygon, leaving the identical edge of current figure in place.
EG.DeleteVertex[inputStart];
The current figure edge left in place is on intersection polygon
[thisToNext, nextToThis] ← EG.FindAdjacency[currentVertex, nextCurrentVertex];
CEG.SetEdgeIPEdge[thisToNext, TRUE];
IF verbosity#NIL THEN verbosity.out.PutF["\nHandleVertexContact marks edge [ #%g , #%g ] on intersection polygon\n", IO.int[currentVertex.index], IO.int[nextCurrentVertex.index]];
inputStart ← inputEnd; inputEnd ← nextInputVertex; -- move to next input polygon edge
currentVertex ← nextCurrentVertex; -- now inputStart and currentVertex are next pair of common coordinate, unmerged vertices of input polygon and current figure
returnedToFirstIntersection ← inputStart = firstIntersection;
IF XOR[returnedToFirstIntersection, currentVertex = firstIntersection] THEN ERROR; -- consistency check
[overlap, overlappedCurrentVertex] ← EG.TestEdgeOverlap[currentVertex, inputEnd]; -- meaningless if returnedToFirstIntersection; that's ok.
ENDLOOP;
IF returnedToFirstIntersection THEN RETURN[TRUE];
Merge the common vertices (preparation for LensDecomposition).
EG.MergeVertices[currentVertex, inputStart];
Determine nextLensInExterior and nextCurrentVertex. Algorithm: currentVertex begins the next lens, i.e. is common to both input polygon and current figure; the next outgoing edge [currentVertex, inputEnd] of the input polygon does not overlap an edge of the current figure. In the (at this point partially constructed) internal polygon containing the edge [currentVertex, inputEnd], we find the current figure vertex x which precedes currentVertex, and if [x, currentVertex].leftRegionExterior, then lensInExterior and nextCurrentVertex = x. If NOT [x, currentVertex].leftRegionExterior, then not lensInExterior, and where y is the current figure vertex following currentVertex in the (at this point partially constructed) internal polygon containing the edge [inputEnd, currentVertex], nextCurrentVertex = y.
nextCurrentVertex ← CEG.PreviousPolygonVertex[currentVertex, nextInputVertex];
[thisToNext, nextToThis] ← EG.FindAdjacency[currentVertex, nextCurrentVertex];
nextLensInExterior ← CEG.GetEdgeExterior[nextToThis];
IF NOT nextLensInExterior THEN
nextCurrentVertex ← CEG.NextPolygonVertex[nextInputVertex, currentVertex];
RETURN[FALSE, nextLensInExterior, currentVertex, nextCurrentVertex, nextInputVertex];
};
LensDecomposition: PUBLIC PROC[firstIntersection, lensStart, innerEnd, outerEnd: Vertex, lensInExterior: BOOL, setIntersectionPolygonEdges: BOOL ← TRUE, verbosity: Verbosity ← NIL] RETURNS [returnedToFirstIntersection: BOOL, innerPrevious, innerCommon, outerPrevious, outerCommon: Vertex] = {
polygonStepping: BOOL = FALSE;
outlineStepping: BOOL = TRUE;
innerStart, outerStart, outerNext, innerNext: Vertex;
innerStartToInnerEnd, innerEndToInnerStart, outerStartToOuterEnd, outerEndToOuterStart: EG.Adjacency;
intersection: Point;
pointDirectedEdgeRelation: EG.PointDirectedEdgeRelation;
pointLineRelation: EG.PointLineRelation;
edgeCompareStatus: EG.BiasedEdgeCompareStatus;
lensClientData: REF;
UpdateInnerEdgeFields: PROC ~ INLINE {
Update leftRegionExterior and state for [innerEnd, innerStart], and record that [innerStart, innerEnd] is an edge of the intersection polygon of the input polygon and the outline of the current figure. If NOT lensInExterior, i.e. input polygon is inner, then need to also set state of (directed edge) [innerStart, innerEnd] to lens state, since it's a new edge in current structure which cuts through an existing region, hence should get the state of that region.
These updates are done for an inner edge only after we know we are ready to move past it. This is important, because if we updated too soon, we might e.g. assign a new state to a region that at one point in time extended for the whole length of an inner edge, but the lens might in fact terminate by the outer polygon cutting across that edge, meaning that this region was being subdivided into two regions, the one of which ultimately outside the lens should not get the new state.
[innerStartToInnerEnd, innerEndToInnerStart] ← EG.FindAdjacency[innerStart, innerEnd];
CEG.SetEdgeExterior[innerEndToInnerStart, FALSE];
CEG.SetEdgeClientData[innerEndToInnerStart, lensClientData];
IF NOT lensInExterior THEN CEG.SetEdgeClientData[innerStartToInnerEnd, lensClientData];
IF setIntersectionPolygonEdges THEN {
CEG.SetEdgeIPEdge[innerStartToInnerEnd, TRUE];
IF verbosity#NIL THEN verbosity.out.PutF["\nLensDecomposition marks edge [ #%g , #%g ] on intersection polygon\n", IO.int[innerStart.index], IO.int[innerEnd.index]];
};
};
Initialize
innerStart ← outerStart ← lensStart;
[outerStartToOuterEnd, outerEndToOuterStart] ← EG.FindAdjacency[ outerStart, outerEnd ];
lensClientData ← CEG.GetEdgeClientData[outerStartToOuterEnd]; -- clientData for lens is clientData of outer polygon
outerNext ← CEG.NextVertex[outerStart, outerEnd, polygonStepping];
innerNext ← CEG.NextVertex[innerStart, innerEnd, outlineStepping];
Follow the lens, biting off convex polygons
DO -- WHILE NOT EndOfLens
Find last outer vertex "above" current inner edge.
pointDirectedEdgeRelation ← EG.PointDirectedEdgeTest[innerStart.coordinates, innerEnd.coordinates, outerNext.coordinates];
WHILE pointDirectedEdgeRelation = RIGHTOFEDGE DO
outerStart ← outerEnd; [outerEnd, outerNext] ← CEG.StepVertex[outerEnd, outerNext, polygonStepping];
pointDirectedEdgeRelation ← EG.PointDirectedEdgeTest[innerStart.coordinates, innerEnd.coordinates, outerNext.coordinates];
ENDLOOP;
edgeCompareStatus ← EG.BiasedEdgeCompare[outerEnd, outerNext, innerStart, innerEnd];
SELECT edgeCompareStatus FROM
OuterEndInInner => {
innerEnd ← CEG.InsertVertexInEdges[innerStart, innerEnd, outerNext.coordinates];
UpdateInnerEdgeFields[];
RETURN[FALSE, innerStart, innerEnd, outerEnd, outerNext];
};
OuterEndEqInnerEnd => {
UpdateInnerEdgeFields[];
IF innerEnd = outerNext THEN -- returnedToFirstIntersection
RETURN[TRUE, innerStart, innerEnd, outerEnd, outerNext]
ELSE
RETURN[FALSE, innerStart, innerEnd, outerEnd, outerNext];
};
ProperIntersection => {
intersection ← EG.IntersectLines[innerStart.coordinates, innerEnd.coordinates, outerEnd.coordinates, outerNext.coordinates];
innerEnd ← CEG.InsertVertexInEdges[innerStart, innerEnd, intersection];
outerNext ← CEG.InsertVertexInEdges[outerEnd, outerNext, intersection];
UpdateInnerEdgeFields[];
RETURN[FALSE, innerStart, innerEnd, outerEnd, outerNext]
};
InnerEndInOuter => {
outerNext ← CEG.InsertVertexInEdges[outerEnd, outerNext, innerEnd.coordinates];
UpdateInnerEdgeFields[];
RETURN[FALSE, innerStart, innerEnd, outerEnd, outerNext];
};
Disjoint => {
Create edges [innerEnd, outerEnd].
CEG.JoinVertices[innerEnd, outerEnd, lensClientData, lensClientData]; -- new edges get lens state, other fields default.
IF verbosity#NIL THEN verbosity.out.PutF["\nLensDecomposition joins vertices #%g and #%g in lens\n", IO.int[innerEnd.index], IO.int[outerEnd.index] ];
Update appropriate fields of edges [innerEnd, innerStart].
UpdateInnerEdgeFields[];
Corner check, i.e. check whether outerEnd is left of next inner edge (directed edge [innerEnd, innerNext]); if so, then we need edges [innerEnd, outerNext], so that the next polygon we bite out of the lens is convex.
pointLineRelation ← EG.PointLineTest[innerEnd.coordinates, innerNext.coordinates, outerEnd.coordinates];
IF pointLineRelation = LEFTOFLINE THEN {
outerStart ← outerEnd;
[outerEnd, outerNext] ← CEG.StepVertex[ outerEnd, outerNext, polygonStepping]; -- need to step outer polygon before doing next JoinVertices
CEG.JoinVertices[ innerEnd, outerEnd, lensClientData, lensClientData ];
IF verbosity#NIL THEN verbosity.out.PutF["\nLensDecomposition corner check joins vertices #%g and #%g in lens\n", IO.int[innerEnd.index], IO.int[outerEnd.index] ];
};
innerStart ← innerEnd;
[innerEnd, innerNext] ← CEG.StepVertex[innerEnd, innerNext, outlineStepping];
};
ENDCASE => ERROR -- OuterEndEqInnerStart, InnerStartInOuter cannot occur (proof by induction).;
ENDLOOP;
};
BoundaryContactOnly: PUBLIC PROC[inputStart, inputEnd, currentVertex: Vertex, verbosity: Verbosity ← NIL] = {
overlap: BOOL;
overlappedCurrentVertex, nextCurrentVertex: Vertex;
distStartCurrent, distStartInput: RN.RatNum;
newVertex, nextInputVertex, tempVertex: Vertex;
thisToNext, nextToThis: EG.Adjacency;
startToEnd, endToStart: EG.Adjacency;
inputClientData: REF;
[ startToEnd, endToStart ] ← EG.FindAdjacency[ inputStart, inputEnd ];
inputClientData ← CEG.GetEdgeClientData[startToEnd];
[overlap, overlappedCurrentVertex] ← EG.TestEdgeOverlap[currentVertex, inputEnd];
WHILE overlap DO
Find out which of overlappedCurrentVertex, inputEnd closer to inputStart, create new vertex if appropriate.
distStartInput ← EG.DistanceSquare[inputStart.coordinates, inputEnd.coordinates];
distStartCurrent ← EG.DistanceSquare[currentVertex.coordinates, overlappedCurrentVertex.coordinates];
SELECT RN.RatNumCompare[distStartInput, distStartCurrent] FROM
ratGreater => {
newVertex ← CEG.InsertVertexInEdges[inputStart, inputEnd, overlappedCurrentVertex.coordinates];
nextInputVertex ← inputEnd;
inputEnd ← newVertex;
nextCurrentVertex ← overlappedCurrentVertex;
};
ratEqual => {
nextInputVertex ← CEG.NextPolygonVertex[inputStart, inputEnd]; -- meaningless if returnedToFirstIntersection; that's ok.
nextCurrentVertex ← overlappedCurrentVertex;
};
ratLess => {
newVertex ← CEG.InsertVertexInEdges[currentVertex, overlappedCurrentVertex, inputEnd.coordinates];
nextCurrentVertex ← newVertex;
nextInputVertex ← CEG.NextPolygonVertex[inputStart, inputEnd];
};
ENDCASE;
Split off incoming input edge, attach to currentVertex.
IF EG.CountAdjacencies[inputStart] > 1 THEN {
tempVertex ← EG.SplitVertex[inputStart, inputEnd];
EG.MergeVertices[currentVertex, tempVertex];
};
Delete edges [inputStart, inputEnd] from input polygon, leaving the identical edge of current figure in place.
EG.DeleteVertex[inputStart];
Clear exterior field and set client data of current outline edge left in place
[thisToNext, nextToThis] ← EG.FindAdjacency[currentVertex, nextCurrentVertex];
CEG.SetEdgeExterior[thisToNext, FALSE];
CEG.SetEdgeClientData[thisToNext, inputClientData];
IF verbosity#NIL THEN verbosity.out.PutF["\nBoundaryContactOnly updates fields of edge [ #%g , #%g ]\n", IO.int[currentVertex.index], IO.int[nextCurrentVertex.index]];
inputStart ← inputEnd; inputEnd ← nextInputVertex; -- move to next input polygon edge
currentVertex ← nextCurrentVertex; -- now inputStart and currentVertex are next pair of common coordinate, unmerged vertices of input polygon and current figure
[overlap, overlappedCurrentVertex] ← EG.TestEdgeOverlap[currentVertex, inputEnd];
ENDLOOP;
Merge the last common vertices before input polygon veers into exterior of current outline.
EG.MergeVertices[currentVertex, inputStart];
};
Structure Cleaner
SimpleCleaner: PUBLIC PROC [currentEnd: Vertex, clientDataEqual: ClientDataEqual, verbosity: Verbosity ← NIL] ~ {
Depth First Search. Assumes we're called with three or more vertices. Never eliminates an edge pair one of whose elements is an exterior edge.
visitedValue: BOOL;
SimpleCleanerSubr: PROC[v: Vertex, visitedValue: BOOL, clientDataEqual: ClientDataEqual, verbosity: Verbosity ← NIL] = {
adjacencies: LIST OF Vertex;
nextVertex, prevV: Vertex;
vToNext, NextTov: EG.Adjacency;
Record that we've visited v
v.visited ← visitedValue; -- record that we've visited this vertex
Recursive calls for adjacencies of v
adjacencies ← EG.AdjacentVertices[v];
WHILE adjacencies#NIL DO
nextVertex ← adjacencies.first;
IF nextVertex.visited # visitedValue THEN
SimpleCleanerSubr[ nextVertex, visitedValue, clientDataEqual, verbosity]
ELSE {
IF EG.Adjacent[v, nextVertex] AND EG.CountAdjacencies[v] > 2 AND EG.CountAdjacencies[nextVertex] > 2 THEN { -- v and nextVertex may no longer be adjacent (because of deletes), and we don't want to create vertices with only one adjacency.
[vToNext, NextTov] ← EG.FindAdjacency[ v, nextVertex ];
IF NOT CEG.GetEdgeExterior[vToNext] AND NOT CEG.GetEdgeExterior[NextTov] -- don't delete outline edges
THEN IF clientDataEqual[CEG.GetEdgeClientData[vToNext], CEG.GetEdgeClientData[NextTov] ] THEN {
prevV ← CEG.PreviousPolygonVertex[v, nextVertex];
EG.DeleteEdge[v, nextVertex];
EG.DeleteEdge[nextVertex, v]; -- temporarily delete the edges
IF CEG.ConvexPolygon[prevV, v, FALSE] THEN {
IF verbosity#NIL THEN verbosity.out.PutF["\nSimpleCleaner deletes edges [ #%g , #%g ]\n", IO.int[v.index], IO.int[nextVertex.index]]
}
ELSE { -- restore the edges
CEG.AddEdge[v, nextVertex, CEG.GetEdgeExterior[vToNext], CEG.GetEdgeIPEdge[vToNext], CEG.GetEdgeClientData[vToNext], vToNext.visited];
CEG.AddEdge[nextVertex, v, CEG.GetEdgeExterior[NextTov], CEG.GetEdgeIPEdge[NextTov], CEG.GetEdgeClientData[NextTov], NextTov.visited];
};
};
};
};
adjacencies ← adjacencies.rest;
ENDLOOP;
};
IF currentEnd = NIL OR currentEnd.adjacentVertices = NIL THEN ERROR; -- no or one vertex;
visitedValue ← currentEnd.visited;
SimpleCleanerSubr[currentEnd, NOT visitedValue, clientDataEqual, verbosity]; -- toggle visitedValue
};
END.