> Combiner: PUBLIC PROC[currentEnd, inputEnd: Vertex, inputClientData: REF, clientDataCombiner: ClientDataCombiner, verbosity: Verbosity _ NIL] RETURNS [combinedEnd: Vertex]={ <> 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]={ <> <> <> 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; <> 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; <> IF currentEnd.visited # inputEnd.visited THEN EG.SetFigureVisitedValues[inputEnd, currentEnd.visited]; <> currentStart _ CEG.SpecialPreviousOutlineVertex[currentEnd]; firstInputVertex _ inputStart _ CEG.SpecialPreviousOutlineVertex[inputEnd]; [ startToEnd, endToStart ] _ EG.FindAdjacency[ inputStart, inputEnd ]; inputClientData _ CEG.GetEdgeClientData[startToEnd]; <> 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; <> }; Encloses => { <<>> <> CEG.SetPolygonIPEdges[currentStart, currentEnd, TRUE]; CEG.SetOutwardOutlineEdgeFields[currentStart, currentEnd, FALSE, FALSE, inputClientData]; <> 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; <> [startToEnd, endToStart] _ EG.FindAdjacency[internalStart, internalEnd]; currentInternalClientData _ CEG.GetEdgeClientData[startToEnd]; CEG.SetPolygonClientData[inputStart, inputEnd, currentInternalClientData]; <> CEG.SetPolygonIPEdges[inputStart, inputEnd, TRUE]; CEG.SetOutwardOutlineEdgeFields[inputStart, inputEnd, FALSE, FALSE, currentInternalClientData]; <<>> <> 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; <> 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.>> <> <> 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]; <<>> <> CEG.SetPolygonClientData[start, end, combinedClientData, TRUE]; <> 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; }; <<>> <> <<>> 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 <> [startToEnd, endToStart] _ EG.FindAdjacency[outerStart, outerEnd]; outerClientData _ CEG.GetEdgeClientData[startToEnd]; <> [pointSectorStatus, innerStart, innerEnd] _ CEG.FindSubtendForPoint[ innerStart, innerEnd, innerCOM, outerStart.coordinates, FALSE]; <> 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; <<>> <> 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; <> [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; }; <> <<>> 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 <> 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; <> IF EG.CountAdjacencies[inputStart] > 1 THEN { tempVertex _ EG.SplitVertex[inputStart, inputEnd]; EG.MergeVertices[currentVertex, tempVertex]; }; <> EG.DeleteVertex[inputStart]; <> [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]; <> EG.MergeVertices[currentVertex, inputStart]; <> 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 { <> <> [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]]; }; }; <> 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]; <<>> <> DO -- WHILE NOT EndOfLens <> 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 => { <> 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] ]; <> UpdateInnerEdgeFields[]; <> 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 <> 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; <> IF EG.CountAdjacencies[inputStart] > 1 THEN { tempVertex _ EG.SplitVertex[inputStart, inputEnd]; EG.MergeVertices[currentVertex, tempVertex]; }; <> EG.DeleteVertex[inputStart]; <> [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; <> EG.MergeVertices[currentVertex, inputStart]; }; <> <<>> SimpleCleaner: PUBLIC PROC [currentEnd: Vertex, clientDataEqual: ClientDataEqual, verbosity: Verbosity _ NIL] ~ { <> visitedValue: BOOL; SimpleCleanerSubr: PROC[v: Vertex, visitedValue: BOOL, clientDataEqual: ClientDataEqual, verbosity: Verbosity _ NIL] = { adjacencies: LIST OF Vertex; nextVertex, prevV: Vertex; vToNext, NextTov: EG.Adjacency; <> v.visited _ visitedValue; -- record that we've visited this vertex <> 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. <<>>