> Combiner: PUBLIC PROC[ currentw, inputw: RVHU.VertexHandle, inputState: CSI.State, stateCombiner: CSI.StateCombiner ] RETURNS [combinedw: RVHU.VertexHandle]={ <> intersectionPolygonv, intersectionPolygonw: RVHU.VertexHandle; [combinedw, intersectionPolygonv, intersectionPolygonw] _ CombineGeometry[currentw, inputw, TRUE]; IF intersectionPolygonv#NIL THEN { CombineState[intersectionPolygonv, intersectionPolygonw, inputState, stateCombiner]; ClearIntersectPolygonFields[intersectionPolygonv, intersectionPolygonw]; <<-- ClearIntersectPolygonFields not executed when intersectionPolygonv = NIL, i.e. we assume no intersectionPolygonEdge fields set in this case>> }; }; <<>> CombineGeometry: PUBLIC PROC[ currentw, inputw: RVHU.VertexHandle, setIntersectionPolygonEdges: BOOL _ TRUE] RETURNS [combinedw, intersectionPolygonv, intersectionPolygonw: RVHU.VertexHandle]={ <> <> <> currentv, inputv, combinedv, dummyv, dummyw: RVHU.VertexHandle; currentoutlinecom, inputfigurecom: RVHU.Point; status: RVHU.PointSectorRelation; outsideCurrentStatus: OutsideCurrentTrilean; intsideCurrentStatus: InsideCurrentTrilean; <> IF inputw = NIL THEN RETURN[currentw, NIL, NIL]; IF currentw = NIL THEN RETURN[inputw, NIL, NIL]; IF NOT RVHU.ThreeOrMoreVertices[currentw] OR NOT RVHU.ThreeOrMoreVertices[inputw] THEN ERROR; <> IF currentw.visited # inputw.visited THEN SetFigureVisitedValues[inputw, currentw.visited]; <> currentv _ RVHU.PreviousOutlineVertex[currentw]; inputv _ RVHU.PreviousOutlineVertex[inputw]; <> currentoutlinecom _ RVHU.CenterOfMass[ currentv, currentw, TRUE]; inputfigurecom _ RVHU.CenterOfMass[ inputv, inputw, FALSE]; [status, currentv, currentw] _ RVHU.FindSubtendForPoint[ currentv, currentw, currentoutlinecom, inputv.coordinates, TRUE]; combinedv _ currentv; combinedw _ currentw; -- "Cache" where on the current outline the input activity is taking place, in case the next input activity happens to occur at the same locale. I.e., if [ combinedv, combinedw] is not subsequently reassigned, we will return currentw as it has just been assigned. SELECT status FROM SUBTENDINTERIOR, RIGHTRAYINTERIOR, LEFTRAYINTERIOR => { [outsideCurrentStatus, currentv, currentw, inputv, inputw] _ InputvOutsideCurrentOutline[ currentoutlinecom, currentv, currentw, inputv, inputw]; SELECT outsideCurrentStatus FROM INTERSECTSOUTLINE => [ combinedv, combinedw, intersectionPolygonv, intersectionPolygonw ] _ InputIntersectsCurrent[ EXTERIORTOINTERIOR, currentv, currentw, inputv, inputw, TRUE]; EXTERNAL => { [ combinedv, combinedw ] _ InputExternalToCurrent[ currentv, currentw, inputv, inputw, currentoutlinecom, inputfigurecom]; intersectionPolygonv _ intersectionPolygonw _ NIL; }; ENCLOSES => { v, w, firstv: RVHU.VertexHandle; vTow, wTov: RVHU.AdjacencyHandle; outline: BOOL _ TRUE; inputPolygonState: CSI.State; <> [ vTow, wTov ] _ RVHU.FindAdjacency[ inputv, inputw ]; inputPolygonState _ vTow.leftState; <<>> <> v _ firstv _ currentv; w _ currentw; [ vTow, wTov ] _ RVHU.FindAdjacency[ v, w ]; vTow.intersectionPolygonEdge _ TRUE; wTov.leftRegionExterior _ FALSE; wTov.leftState _ inputPolygonState; WHILE w # firstv DO [v, w] _ RVHU.StepVertex[v,w, outline]; [ vTow, wTov ] _ RVHU.FindAdjacency[ v, w ]; vTow.intersectionPolygonEdge _ TRUE; wTov.leftRegionExterior _ FALSE; wTov.leftState _ inputPolygonState; ENDLOOP; <> PolygonEnclosesPolygon[currentoutlinecom, currentv, currentw, inputv, inputw ]; combinedv _ inputv; combinedw _ inputw; intersectionPolygonv _ currentv; intersectionPolygonw _ currentw; }; ENDCASE => ERROR }; SECTORINTERIOR, RIGHTSPOKEINTERIOR, LEFTSPOKEINTERIOR => { [intsideCurrentStatus, currentv, currentw, inputv, inputw] _ InputvInsideCurrentOutline[ currentoutlinecom, currentv, currentw, inputv, inputw]; SELECT intsideCurrentStatus FROM INTERSECTSOUTLINE => [ combinedv, combinedw, intersectionPolygonv, intersectionPolygonw ] _ InputIntersectsCurrent[INTERIORTOEXTERIOR, currentv, currentw, inputv, inputw, TRUE]; INSINGLEPOLYGON => { v, w, firstv: RVHU.VertexHandle; vTow, wTov: RVHU.AdjacencyHandle; outline: BOOL _ TRUE; currentPolygonState: CSI.State; <> [ vTow, wTov ] _ RVHU.FindAdjacency[ currentv, currentw ]; currentPolygonState _ vTow.leftState; RVHU.SetPolygonState[inputv, inputw, currentPolygonState]; <> v _ firstv _ inputv; w _ inputw; [ vTow, wTov ] _ RVHU.FindAdjacency[ v, w ]; vTow.intersectionPolygonEdge _ TRUE; wTov.leftRegionExterior _ FALSE; wTov.leftState _ currentPolygonState; WHILE w # firstv DO [v, w] _ RVHU.StepVertex[v,w, outline]; [ vTow, wTov ] _ RVHU.FindAdjacency[ v, w ]; vTow.intersectionPolygonEdge _ TRUE; wTov.leftRegionExterior _ FALSE; wTov.leftState _ currentPolygonState; ENDLOOP; <<>> <> PolygonEnclosesPolygon[inputfigurecom, inputv, inputw, currentv, currentw]; intersectionPolygonv _ inputv; intersectionPolygonw _ inputw; -- leave combinedv _ currentv, combinedw _ currentw }; INMULTIPLEPOLYGONS => [dummyv, dummyw, intersectionPolygonv, intersectionPolygonw] _ InputIntersectsCurrent[ INTERIORTOINTERIOR, currentv, currentw, inputv, inputw, TRUE]; -- Don't change settting of [combinedv, combinedw] _ [currentv, currentw] in this case, since current outline didn't change ENDCASE => ERROR }; ENDCASE => ERROR; -- EQUALCOM, EQUALRIGHTVERTEX, EQUALLEFTVERTEX, POLYGONEDGEINTERIOR not currently handled 9/19 RETURN [combinedw, intersectionPolygonv, intersectionPolygonw] }; CombineState: PUBLIC PROC[intersectionPolygonv, intersectionPolygonw: RVHU.VertexHandle, inputState: CSI.State, stateCombiner: CSI.StateCombiner] = { <<[intersectionPolygonv, intersectionPolygonw] 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. inputState is the state of the input polygon. stateCombiner is the rule for state combination.>> <> <> polygonState: CSI.State; v: RVHU.VertexHandle _ intersectionPolygonv; w: RVHU.VertexHandle _ intersectionPolygonw; firstv: RVHU.VertexHandle _ v; vTow, wTov: RVHU.AdjacencyHandle; outline: BOOL _ FALSE; stateRope: Rope.ROPE; [ vTow, wTov ] _ RVHU.FindAdjacency[ v, w ]; polygonState _ stateCombiner[ vTow.leftState, inputState ]; <> stateRope _ CSI.RopeFromState[ polygonState ]; out.PutF["\nCombineState entered with argument [#%g , #%g ], state %g \n", IO.int[v.index], IO.int[w.index], IO.rope[stateRope]]; <<>> <> vTow.leftState _ polygonState; vTow.leftRegionVisited _ TRUE; WHILE w # firstv DO [v, w] _ RVHU.StepVertex[v,w, outline]; [ vTow, wTov ] _ RVHU.FindAdjacency[ v, w ]; vTow.leftState _ polygonState; vTow.leftRegionVisited _ TRUE; ENDLOOP; <> [v, w] _ RVHU.StepVertex[v,w, outline]; WHILE w # firstv DO [v, w] _ RVHU.StepVertex[v,w, outline]; [ vTow, wTov ] _ RVHU.FindAdjacency[ v, w ]; IF NOT vTow.intersectionPolygonEdge THEN IF NOT wTov.leftRegionVisited THEN CombineState[w, v, inputState, stateCombiner ]; ENDLOOP; }; <<>> <> <<>> InputvOutsideCurrentOutline: PUBLIC PROC[ currentfigurecom: RVHU.Point, v1, w1, v2, w2: RVHU.VertexHandle ] RETURNS [outsideCurrentStatus: OutsideCurrentTrilean, v3, w3, v4, w4: RVHU.VertexHandle] = { <<[v1,w1] is a counterclockwise oriented edge on the outline of the current figure, [v2,w2] is a counterclockwise oriented edge of the input figure, such that v2 lies in the wedge of the sector of the current outline defined by [v1,w1], but not in the sector itself (it follows that we don't have to do the loop below for the initial v2). We trace the current outline to follow the input polygon, until an intersection of the input polygon with the current outline is found, or we determine that there is no intersection (i.e. we've gone all the way around the input polygon without finding one). As we trace, we simultaneously collect information to be able to decide whether the input polygon is external to or encloses the outline of the current figure, in case there is no intersection. If an intersection is found, then [v3,w3] is the edge of the current figure, and [v4,w4] the edge of the input figure, which have been found to intersect. If there is no intersection, then [v3,w3] is an edge of the current figure, and [v4,w4] an edge of the input figure, such that v4 is in the wedge defined by [v3,w3].>> external: BOOL _ FALSE; v1first: RVHU.VertexHandle _ v1; v2first: RVHU.VertexHandle _ v2; done: BOOL _ FALSE; pointSectorRelation: RVHU.PointSectorRelation; outcome: RVHU.DirectedEdgeIntersectionStatus; value: RVHU.DirectedEdgeIntersectionStatusValue; intPoint: RVHU.Point; pointSectorRelation _ RVHU.PointSectorTest[ v1.coordinates, w1.coordinates, currentfigurecom, w2.coordinates ]; WHILE NOT done DO SELECT pointSectorRelation FROM RIGHTRAYINTERIOR, LEFTRAYINTERIOR, SUBTENDINTERIOR => NULL; ENDCASE => { [ outcome, intPoint] _ RVHU.IntersectDirectedEdges[ v1.coordinates, w1.coordinates, v2.coordinates, w2.coordinates ]; value _ outcome.first; SELECT value FROM PROPERINTERSECT => RETURN[ INTERSECTSOUTLINE, v1, w1, v2, w2]; DISJOINT => NULL; ENDCASE => ERROR; -- only cases handled 9/19 WHILE pointSectorRelation = RIGHTOFSUBTEND OR pointSectorRelation = LEFTOFSUBTEND DO [v1, w1] _ RVHU.StepVertex[ v1, w1, TRUE ]; -- step current outline to catch up with input polygon edge [ outcome, intPoint] _ RVHU.IntersectDirectedEdges[ v1.coordinates, w1.coordinates, v2.coordinates, w2.coordinates ]; -- check for intersection with input polygon edge as we pass over each current structure edge value _ outcome.first; SELECT value FROM PROPERINTERSECT => RETURN[ INTERSECTSOUTLINE, v1, w1, v2, w2]; DISJOINT => NULL; ENDCASE => ERROR; -- only cases handled 9/19 pointSectorRelation _ RVHU.PointSectorTest[ v1.coordinates, w1.coordinates, currentfigurecom, w2.coordinates ]; ENDLOOP; }; IF RVHU.PointLineTest[ v2.coordinates, w2.coordinates, v1first.coordinates] = RIGHTOFLINE THEN external _ TRUE; -- if current figure is external to input figure, then any vertex of the current figure (we arbitrarily picked v1first) must lie 'external' to at least one edge of the input figure. This test will eventually uncover such an input edge if one exists. [v2,w2] _ RVHU.StepVertex[ v2, w2, TRUE ]; -- move to next edge of input polygon IF v2 = v2first THEN done _ TRUE ELSE pointSectorRelation _ RVHU.PointSectorTest[ v1.coordinates, w1.coordinates, currentfigurecom, w2.coordinates ]; -- check if have walked completely around input polygon ENDLOOP; IF external THEN RETURN[ EXTERNAL, v1, w1, v2, w2 ] ELSE RETURN [ ENCLOSES, v1, w1, v2, w2 ]; }; InputvInsideCurrentOutline: PUBLIC PROC[ currentfigurecom: RVHU.Point, v1, w1, v2, w2: RVHU.VertexHandle ] RETURNS [intsideCurrentStatus: InsideCurrentTrilean, v3, w3, v4, w4: RVHU.VertexHandle ] = { <> <> <> v1first: RVHU.VertexHandle _ v1; w1first: RVHU.VertexHandle _ w1; v2first: RVHU.VertexHandle _ v2; polygoncom: RVHU.Point; status: RVHU.PointSectorRelation; pointSectorRelation: RVHU.PointSectorRelation; v5, w5, temp: RVHU.VertexHandle; done: BOOL _ FALSE; outcome: RVHU.DirectedEdgeIntersectionStatus; value: RVHU.DirectedEdgeIntersectionStatusValue; intPoint: RVHU.Point; pointSectorRelation _ RVHU.PointSectorTest[ v1.coordinates, w1.coordinates, currentfigurecom, w2.coordinates ]; WHILE NOT done DO SELECT pointSectorRelation FROM RIGHTSPOKEINTERIOR, LEFTSPOKEINTERIOR, SECTORINTERIOR => NULL; RIGHTRAYINTERIOR, LEFTRAYINTERIOR, SUBTENDINTERIOR, RIGHTOFSUBTEND, LEFTOFSUBTEND => { [ outcome, intPoint] _ RVHU.IntersectDirectedEdges[ v1.coordinates, w1.coordinates, v2.coordinates, w2.coordinates ]; value _ outcome.first; SELECT value FROM PROPERINTERSECT => RETURN[ INTERSECTSOUTLINE, v1, w1, v2, w2]; DISJOINT => NULL; ENDCASE => ERROR; -- only cases handled 9/19 WHILE pointSectorRelation = RIGHTOFSUBTEND OR pointSectorRelation = LEFTOFSUBTEND DO [v1, w1] _ RVHU.StepVertex[ v1, w1, TRUE ]; -- step current outline to catch up with input polygon edge [ outcome, intPoint] _ RVHU.IntersectDirectedEdges[ v1.coordinates, w1.coordinates, v2.coordinates, w2.coordinates ]; -- check for intersection with input polygon edge as we pass over each current structure edge value _ outcome.first; SELECT value FROM PROPERINTERSECT => RETURN[ INTERSECTSOUTLINE, v1, w1, v2, w2]; DISJOINT => NULL; ENDCASE => ERROR; -- only cases handled 9/19 pointSectorRelation _ RVHU.PointSectorTest[ v1.coordinates, w1.coordinates, currentfigurecom, w2.coordinates ]; ENDLOOP; }; ENDCASE => ERROR; -- other cases not handled 9/19 [v2,w2] _ RVHU.StepVertex[ v2, w2, TRUE ]; IF v2 = v2first THEN done _ TRUE ELSE pointSectorRelation _ RVHU.PointSectorTest[ v1.coordinates, w1.coordinates, currentfigurecom, w2.coordinates ]; ENDLOOP; <> v1 _ v1first; -- reinitialize our position on the current figure w1 _ w1first; polygoncom _ RVHU.CenterOfMass[ v1, w1, FALSE]; -- find com of internal polygon. [status, v5, w5] _ RVHU.FindSubtendForPoint[ v1, w1, polygoncom, v2.coordinates, FALSE ]; -- [v5,w5] defines a particular sector of this polygon WHILE status = RIGHTRAYINTERIOR OR status = LEFTRAYINTERIOR OR status = SUBTENDINTERIOR DO -- flip flop polygons until you find the one that contains v2 temp _ v5; v5 _ w5; w5 _ temp; -- flip v5 and w5 to move to next polygon polygoncom _ RVHU.CenterOfMass[ v5, w5, FALSE]; [status, v5, w5] _ RVHU.FindSubtendForPoint[ v5, w5, polygoncom, v2.coordinates, FALSE ]; ENDLOOP; SELECT status FROM RIGHTSPOKEINTERIOR, LEFTSPOKEINTERIOR, SECTORINTERIOR => NULL; ENDCASE => ERROR; -- other cases not handled 9/19 <> <> done _ FALSE; pointSectorRelation _ RVHU.PointSectorTest[ v5.coordinates, w5.coordinates, currentfigurecom, w2.coordinates ]; WHILE NOT done DO SELECT pointSectorRelation FROM EQUALCOM, RIGHTSPOKEINTERIOR, LEFTSPOKEINTERIOR, SECTORINTERIOR => NULL; RIGHTRAYINTERIOR, LEFTRAYINTERIOR, SUBTENDINTERIOR, RIGHTOFSUBTEND, LEFTOFSUBTEND => { <> [ outcome, intPoint] _ RVHU.IntersectDirectedEdges[ v5.coordinates, w5.coordinates, v2.coordinates, w2.coordinates ]; value _ outcome.first; SELECT value FROM PROPERINTERSECT => RETURN[ INMULTIPLEPOLYGONS, v5, w5, v2, w2]; DISJOINT => NULL; ENDCASE => ERROR; WHILE pointSectorRelation = RIGHTOFSUBTEND OR pointSectorRelation = LEFTOFSUBTEND DO [v5, w5] _ RVHU.StepVertex[ v5, w5, FALSE ]; [ outcome, intPoint] _ RVHU.IntersectDirectedEdges[ v5.coordinates, w5.coordinates, v2.coordinates, w2.coordinates ]; value _ outcome.first; SELECT value FROM PROPERINTERSECT => RETURN[ INMULTIPLEPOLYGONS, v5, w5, v2, w2]; DISJOINT => NULL; ENDCASE => ERROR; pointSectorRelation _ RVHU.PointSectorTest[ v5.coordinates, w5.coordinates, currentfigurecom, w2.coordinates ]; ENDLOOP; }; ENDCASE => ERROR; -- other cases not handled 9/19 [v2, w2] _ RVHU.StepVertex[ v2, w2, TRUE ]; IF v2 = v2first THEN done _ TRUE ELSE pointSectorRelation _ RVHU.PointSectorTest[ v5.coordinates, w5.coordinates, currentfigurecom, w2.coordinates ]; ENDLOOP; RETURN [INSINGLEPOLYGON, v5, w5, v2, w2]; -- As a result of the last RVHU.StepVertex of the just-finished loop, v2 is now in the sector determined by [v5,w5]. }; InputIntersectsCurrent: PUBLIC PROC[ lensTransitionType: LensTransitionType, currentv, currentw, inputv, inputw: RVHU.VertexHandle, setIntersectionPolygonEdges: BOOL _ TRUE] RETURNS [voutline, woutline: RVHU.VertexHandle _ NIL, intersectionPolygonv, intersectionPolygonw: RVHU.VertexHandle] = { <<[currentv, currentw] is an edge of the current figure, and [inputv, inputw] is an edge of the input figure, which intersect and thus constitute a lens transition pont. lensTransitionType specifies the type of transition which is occurring at their intersection. [voutline,woutline] is a counterclockwise oriented edge on the outline of the combined figure, unless all lenses are internal to the current outline (i.e. all lens transitions are INTERIORTOINTERIOR), in which case voutline _ woutline _ NIL;>> pj1, pj, qi1, qi: RVHU.VertexHandle; v, firstv, temp : RVHU.VertexHandle; returnedToFirstv: BOOL _ FALSE; lensInExterior, nextLensInExterior: BOOL; qi1Tov, vToqi1: RVHU.AdjacencyHandle; <> IF lensTransitionType = EXTERIORTOINTERIOR THEN { pj1 _ currentv; pj _ currentw; qi1 _ inputv; qi _ inputw; lensInExterior _ TRUE } ELSE IF lensTransitionType = INTERIORTOEXTERIOR THEN { pj1 _ inputv; pj _ inputw; qi1 _ currentv; qi _ currentw; lensInExterior _ FALSE } ELSE { -- lensTransitionType = INTERIORTOINTERIOR pj1 _ inputv; pj _ inputw; qi1 _ currentv; qi _ currentw; lensInExterior _ FALSE }; <> v _ firstv _ InsertIntersectionPoint[pj1, pj, qi1, qi]; <> WHILE NOT returnedToFirstv DO <> IF lensInExterior THEN { -- lensTransitionType = EXTERIORTOINTERIOR lensTransitionType _ EXTERIORTOINTERIOR; -- set it <> [voutline, woutline] _ GrowToConvexOutline[ qi1, v, pj ]; <<>> <> temp _ pj; pj _ qi; qi _ temp; nextLensInExterior _ FALSE; } ELSE { [ qi1Tov, vToqi1 ] _ RVHU.FindAdjacency[ qi1, v ]; -- compute nextLensInExterior nextLensInExterior _ vToqi1.leftRegionExterior; IF nextLensInExterior THEN { -- lensTransitionType = INTERIORTOEXTERIOR lensTransitionType _ INTERIORTOEXTERIOR; <> [voutline, woutline] _ GrowToConvexOutline[ qi1, v, pj]; <<>> <> temp _ pj; pj _ qi; qi _ temp; } ELSE { -- lensTransitionType = INTERIORTOINTERIOR lensTransitionType _ INTERIORTOINTERIOR; <> qi _ qi1; }; }; <> lensInExterior _ nextLensInExterior; [returnedToFirstv, v, pj1, pj, qi1, qi ] _ LensDecomposition[ firstv, v, pj, qi, lensInExterior, setIntersectionPolygonEdges]; ENDLOOP; <> RETURN[ voutline, woutline, pj1, pj]; }; InputExternalToCurrent: PUBLIC PROC[ currentv, currentw, inputv, inputw: RVHU.VertexHandle, currentoutlinecom, inputfigurecom: RVHU.Point] RETURNS [combinedv, combinedw: RVHU.VertexHandle] = { <<[currentv, currentw] is a counterclockwise oriented edge on the (convex) outline of the current figure. [inputv, inputw] is a counterclockwise oriented edge on the input polygon. [currentv, currentw] defines a sector of the current figure in (the closure of) which inputv lies. [combinedv, combinedw] is a counterclockwise oriented edge on the (convex) outline of the combined figure. >> <> previousInv, previousCurv: RVHU.VertexHandle; forwardCurw: RVHU.VertexHandle; pointLineRelation: RVHU.PointLineRelation; status: RVHU.PointSectorRelation; [status, inputv, inputw] _ RVHU.FindSubtendForPoint[ inputv, inputw, inputfigurecom, currentoutlinecom, TRUE]; [status, currentv, currentw] _ RVHU.FindSubtendForPoint[ currentv, currentw, currentoutlinecom, inputv.coordinates, TRUE]; previousCurv _ RVHU.NewPrevOutlineVertex[currentv, currentw]; JoinVerticesOnOutline[previousCurv, currentv, inputv, inputw, FALSE]; -- triangle not yet formed, so call with setLRE = FALSE out.PutF["\nInputExternalToCurrent has joined vertices #%g and #%g\n", IO.int[currentv.index], IO.int[inputv.index]]; previousInv _ RVHU.PreviousVertex[inputv, inputw, FALSE]; -- can't do PreviousOutlineVertex because of new edge from currentv to inputv forwardCurw _ RVHU.NextOutlineVertex[currentv, currentw]; -- NextOutlineVertex will still work because edge from inputv to currentw not yet added JoinVerticesOnOutline[previousInv, inputv, currentw, forwardCurw]; -- now triangle formed, so set LRE fields of its inward-facing edges. out.PutF["\nInputExternalToCurrent has joined vertices #%g and #%g\n", IO.int[inputv.index], IO.int[currentw.index]]; pointLineRelation _ RVHU.PointLineTest[previousInv.coordinates, inputv.coordinates, currentw.coordinates]; IF pointLineRelation = RIGHTOFLINE THEN [combinedv, combinedw] _ GrowToConvexOutline[ previousInv, inputv, currentw] ELSE { pointLineRelation _ RVHU.PointLineTest[inputv.coordinates, currentw.coordinates, forwardCurw.coordinates]; IF pointLineRelation = RIGHTOFLINE THEN [combinedv, combinedw] _ GrowToConvexOutline[ inputv, currentw, forwardCurw] }; pointLineRelation _ RVHU.PointLineTest[previousCurv.coordinates, currentv.coordinates, inputv.coordinates]; IF pointLineRelation = RIGHTOFLINE THEN [combinedv, combinedw] _ GrowToConvexOutline[ previousCurv, currentv, inputv] ELSE { pointLineRelation _ RVHU.PointLineTest[currentv.coordinates, inputv.coordinates, inputw.coordinates]; IF pointLineRelation = RIGHTOFLINE THEN [combinedv, combinedw] _ GrowToConvexOutline[ currentv, inputv, inputw] }; RETURN [combinedv, combinedw] }; PolygonEnclosesPolygon: PUBLIC PROC[ innercom: RVHU.Point, innerv, innerw, outerv, outerw: RVHU.VertexHandle] = { <<[innerv, innerw] is a counterclockwise oriented edge on the inner polygon. [outerv, outerw] is a counterclockwise oriented edge on the outer polygon.>> <> status: RVHU.PointSectorRelation; returnedToFirstv: BOOL _ FALSE; nextInner, prevInner, thisInner: RVHU.VertexHandle; vending, pj1ending, pjending, qi1ending, qiending: RVHU.VertexHandle; pointLineRelation: RVHU.PointLineRelation; [status, innerv, innerw] _ RVHU.FindSubtendForPoint[ innerv, innerw, innercom, outerv.coordinates, FALSE]; out.PutF["\nEnter PolygonEnclosesPolygon\n"]; <> nextInner _ innerw; thisInner _ innerv; prevInner _ RVHU.NewPrevOutlineVertex[thisInner, nextInner]; pointLineRelation _ RVHU.PointLineTest[outerv.coordinates, thisInner.coordinates, prevInner.coordinates]; WHILE pointLineRelation = LEFTOFLINE DO nextInner _ thisInner; thisInner _ prevInner; prevInner _ RVHU.NewPrevOutlineVertex[thisInner, nextInner]; pointLineRelation _ RVHU.PointLineTest[outerv.coordinates, thisInner.coordinates, prevInner.coordinates]; ENDLOOP; <<>> <> JoinVerticesInLens[thisInner, nextInner, outerv, outerw]; pointLineRelation _ RVHU.PointLineTest[outerv.coordinates, thisInner.coordinates, nextInner.coordinates]; WHILE pointLineRelation = RIGHTOFLINE DO prevInner _ thisInner; [thisInner, nextInner] _ RVHU.StepVertex[thisInner, nextInner, TRUE]; -- outline step, since inner figure could be current figure JoinVerticesInLens[thisInner, nextInner, outerv, outerw]; pointLineRelation _ RVHU.PointLineTest[outerv.coordinates, thisInner.coordinates, nextInner.coordinates]; ENDLOOP; <> [returnedToFirstv, vending, pj1ending, pjending, qi1ending, qiending ] _ LensDecomposition[ outerv, outerv, thisInner, outerw, TRUE, FALSE]; -- lensInExterior = TRUE is the right thing, to get outline stepping of the inner figure. setIntersectionPolygonEdges = FALSE, since we assume already done by caller, and presence of cone makes it tricky in any case. IF NOT returnedToFirstv THEN ERROR; RETURN }; <> <<>> LensDecomposition: PUBLIC PROC[ firstv, v, pj, qi: RVHU.VertexHandle, lensInExterior: BOOL, setIntersectionPolygonEdges: BOOL _ TRUE] RETURNS [ returnedToFirstv: BOOL, vending, pj1ending, pjending, qi1ending, qiending: RVHU.VertexHandle] = { <> <> <> <> <<11/27/85 - Shouldn't the rule be just to outline step the inner polygon, and polygon step the outer polygon?>> pj1, qi1, qip1, pjp1, intersection: RVHU.VertexHandle; pj1Topj, pjTopj1, qi1Toqi, qiToqi1: RVHU.AdjacencyHandle; pj1Toint, intTopj1: RVHU.AdjacencyHandle; ReachedNextIntersection: BOOL _ FALSE; polygonStepping: BOOL _ FALSE; outcome: RVHU.DirectedEdgeIntersectionStatus; value: RVHU.DirectedEdgeIntersectionStatusValue; intPoint: RVHU.Point; pointLineRelation: RVHU.PointLineRelation; lensState: CSI.State; <> pj1 _ qi1 _ v; returnedToFirstv _ FALSE; [qi1Toqi, qiToqi1] _ RVHU.FindAdjacency[ qi1, qi ]; lensState _ qi1Toqi.leftState; -- state of lens is (internal) state of outer polygon qip1 _ RVHU.NextVertex[qi1, qi, polygonStepping]; -- qip1 will be used for avoiding calls to RVHU.NextVertex and RVHU.StepVertex following insertion of new edges (would go off and follow wrong polygon) pjp1 _ RVHU.NextVertex[pj1, pj, lensInExterior]; -- same as for qip1 <<>> <> WHILE (NOT ReachedNextIntersection) AND (NOT returnedToFirstv) DO <> pointLineRelation _ RVHU.PointLineTest[pj1.coordinates, pj.coordinates, qip1.coordinates]; WHILE pointLineRelation # LEFTOFLINE AND qip1 # pj DO -- ( qip1 # pj ) needed for last lens when we are going to be returnedToFirstv IF pointLineRelation = ONLINE THEN ERROR; -- not yet handled qi1 _ qi; [qi, qip1] _ RVHU.StepVertex[ qi, qip1, polygonStepping]; pointLineRelation _ RVHU.PointLineTest[pj1.coordinates, pj.coordinates, qip1.coordinates]; ENDLOOP; <> IF pj = firstv AND qip1 = firstv THEN returnedToFirstv _ TRUE ELSE { <<-- the test for returnedToFirstv must be pj = firstv AND qip1 = firstv, because pj = firstv, NOT returnedToFirstv, ReachedNextIntersection, could occur by pj reaching ahead through the next lens to happen to coincide with firstv (- qip1 could reach ahead in the same way?; don't know, not necessary to know 1/30/85). >> [ outcome, intPoint] _ RVHU.IntersectDirectedEdges[ pj1.coordinates, pj.coordinates, qi.coordinates, qip1.coordinates ]; value _ outcome.first; SELECT value FROM PROPERINTERSECT => ReachedNextIntersection _ TRUE; DISJOINT => NULL; ENDCASE => ERROR; }; <> IF (NOT ReachedNextIntersection) AND (NOT returnedToFirstv) THEN { JoinVerticesInLens[ pj, pjp1, qi, qip1 ]; <> [pj1Topj, pjTopj1] _ RVHU.FindAdjacency[ pj1, pj ]; <> pjTopj1.leftRegionExterior _ FALSE; pjTopj1.leftState _ lensState; IF setIntersectionPolygonEdges THEN { pj1Topj.intersectionPolygonEdge _ TRUE; -- note that here we set a field of pj1Topj, whereas in previous two assignments we set fields of pjTopj1. out.PutF["\nLensDecomposition marks edge [ #%g , #%g ] on intersection polygon\n", IO.int[pj1.index], IO.int[pj.index]]; -- verbosity }; pj1 _ pj; [pj, pjp1] _ RVHU.StepVertex[ pj, pjp1, lensInExterior ]; <> pointLineRelation _ RVHU.PointLineTest[pj1.coordinates, pj.coordinates, qi.coordinates]; IF pointLineRelation = LEFTOFLINE THEN { qi1 _ qi; [qi, qip1] _ RVHU.StepVertex[ qi, qip1, polygonStepping]; JoinVerticesInLens[ pj1, pj, qi, qip1 ]; -- Note use of pj1 and pj instead of pj and pjp1, since we want an edge to the same vertex of inner polygon, but we've done a StepVertex <> }; }; ENDLOOP; IF ReachedNextIntersection THEN { intersection _ InsertIntersectionPoint[pj1, pj, qi, qip1]; <> [pj1Toint, intTopj1] _ RVHU.FindAdjacency[ pj1, intersection ]; intTopj1.leftRegionExterior _ FALSE; intTopj1.leftState _ lensState; IF setIntersectionPolygonEdges THEN { pj1Toint.intersectionPolygonEdge _ TRUE; out.PutF["\nLensDecomposition marks edge [ #%g , #%g ] on intersection polygon\n", IO.int[pj1.index], IO.int[intersection.index]]; -- verbosity }; RETURN [returnedToFirstv, intersection, pj1, pj, qi, qip1]; } ELSE { -- returnedToFirstv <> [pj1Topj, pjTopj1] _ RVHU.FindAdjacency[ pj1, pj ]; -- pj = firstv pjTopj1.leftRegionExterior _ FALSE; pjTopj1.leftState _ lensState; IF setIntersectionPolygonEdges THEN { pj1Topj.intersectionPolygonEdge _ TRUE; out.PutF["\nLensDecomposition marks edge [ #%g , #%g ] on intersection polygon\n", IO.int[pj1.index], IO.int[pj.index]]; -- verbosity }; RETURN [returnedToFirstv, firstv, pj1, pj, qi, qip1]; -- note that pj = qip1 = firstv }; }; GrowToConvexOutline: PUBLIC PROC[w2, v, w1: RVHU.VertexHandle, outline: BOOL _ TRUE] RETURNS [v3,w3: RVHU.VertexHandle] = { <> <> ok: BOOL _ FALSE; prew1, forw1, prew2, forw2: RVHU.VertexHandle; -- in the counterclockwise order on the outline (with respect to interior of figure), we have (prew2, w2, forw2, prew1, w1, forw1) pointLineRelation: RVHU.PointLineRelation; prew2 _ RVHU.PreviousVertex[w2, v, outline]; forw2 _ v; prew1 _ v; forw1 _ RVHU.NextVertex[v, w1, outline]; <> WHILE NOT ok DO ok _ TRUE; <> pointLineRelation _ RVHU.PointLineTest[w1.coordinates, w2.coordinates, prew2.coordinates]; IF pointLineRelation = ONLINE THEN ERROR; -- not yet handled WHILE pointLineRelation = LEFTOFLINE DO ok _ FALSE; IF NOT RVHU.ConvexPolygonOnOutline[ prew2, w2, prew1, w1, outline] THEN { JoinVerticesOnOutline[prew2, w2, w1, forw1]; prew1 _ w2; -- take account of presence of new edge joining w1 and w2 out.PutF["\nGrowToConvexOutline has joined vertices #%g and #%g\n", IO.int[w2.index], IO.int[w1.index]]; }; forw2 _ w2; w2 _ prew2; prew2 _ RVHU.PreviousVertex[w2, forw2, outline]; pointLineRelation _ RVHU.PointLineTest[w1.coordinates, w2.coordinates, prew2.coordinates]; IF pointLineRelation = ONLINE THEN ERROR; -- not yet handled ENDLOOP; <> pointLineRelation _ RVHU.PointLineTest[forw1.coordinates, w1.coordinates, w2.coordinates]; IF pointLineRelation = ONLINE THEN ERROR; -- not yet handled WHILE pointLineRelation = LEFTOFLINE DO ok _ FALSE; IF NOT RVHU.ConvexPolygonOnOutline[ w2, forw2, w1, forw1, outline] THEN { JoinVerticesOnOutline[ prew2, w2, w1, forw1]; forw2 _ w1; -- take account of presence of new edge joining w1 and w2 out.PutF["\nGrowToConvexOutline has joined vertices #%g and #%g\n", IO.int[w2.index], IO.int[w1.index]]; }; prew1 _ w1; [w1, forw1] _ RVHU.StepVertex[w1, forw1, outline]; pointLineRelation _ RVHU.PointLineTest[forw1.coordinates, w1.coordinates, w2.coordinates]; IF pointLineRelation = ONLINE THEN ERROR; -- not yet handled ENDLOOP; ENDLOOP; JoinVerticesOnOutline[prew2, w2, w1, forw1]; -- no need to update forw2 or prew1 since this is the last edge that will be added out.PutF["\nGrowToConvexOutline has joined vertices #%g and #%g\n", IO.int[w2.index], IO.int[w1.index]]; RETURN [w2, w1] }; <> InsertIntersectionPoint: PUBLIC PROC[ pj1, pj, qi, qip1: RVHU.VertexHandle] RETURNS [ vh: RVHU.VertexHandle] = { << Split the intersecting edges [pj1, pj] and [qi, qip1] which terminate a lens. Assumes that Counterclockwise[pj1, pj, qip1], i.e. [pj1, pj] and [qi, qip1] are at the end of a lens in which [pj1, pj] was on the inner polygon and [qi, qip1] was on the outer.>> <> ah: RVHU.AdjacencyHandle; ahlsave: RVHU.AdjacencyHandleList; outcome: RVHU.DirectedEdgeIntersectionStatus; intPoint: RVHU.Point; pj1Topj, pjTopj1, qiToqip1, qip1Toqi: RVHU.AdjacencyHandle; <<>> <> [outcome, intPoint] _ RVHU.IntersectDirectedEdges[ pj1.coordinates, pj.coordinates, qi.coordinates, qip1.coordinates ]; IF outcome.first # PROPERINTERSECT THEN ERROR; <> vh _ NEW[ RVHU.Vertex _ [coordinates: intPoint, index: RVHU.vertexIndex, adjacentVertices: NIL, visited: pj.visited] ]; RVHU.vertexIndex _ RVHU.vertexIndex + 1; <> [pj1Topj, pjTopj1] _ RVHU.FindAdjacency[ pj1, pj]; [qiToqip1, qip1Toqi] _ RVHU.FindAdjacency[ qi, qip1]; <> pj1Topj.vertex _ vh; pjTopj1.vertex _ vh; qiToqip1.vertex _ vh; qip1Toqi.vertex _ vh; <> ah _ NEW[ RVHU.Adjacency _ [vertex: pj, leftState: pj1Topj.leftState, leftRegionVisited : pj1Topj.leftRegionVisited, leftRegionExterior: pj1Topj.leftRegionExterior, intersectionPolygonEdge: pj1Topj.intersectionPolygonEdge] ]; vh.adjacentVertices _ CONS[ ah, vh.adjacentVertices ]; ahlsave _ vh.adjacentVertices; -- save pointer to last list cell for making circular list <> ah _ NEW[ RVHU.Adjacency _ [vertex: qip1, leftState: qiToqip1.leftState, leftRegionVisited : qiToqip1.leftRegionVisited, leftRegionExterior : qiToqip1.leftRegionExterior, intersectionPolygonEdge : qiToqip1.intersectionPolygonEdge] ]; vh.adjacentVertices _ CONS[ ah, vh.adjacentVertices ]; <> ah _ NEW[ RVHU.Adjacency _ [vertex: pj1, leftState: pjTopj1.leftState, leftRegionVisited : pjTopj1.leftRegionVisited, leftRegionExterior : pjTopj1.leftRegionExterior, intersectionPolygonEdge : pjTopj1.intersectionPolygonEdge] ]; vh.adjacentVertices _ CONS[ ah, vh.adjacentVertices ]; <> ah _ NEW[ RVHU.Adjacency _ [vertex: qi, leftState: qip1Toqi.leftState, leftRegionVisited : qip1Toqi.leftRegionVisited, leftRegionExterior : qip1Toqi.leftRegionExterior, intersectionPolygonEdge : qip1Toqi.intersectionPolygonEdge] ]; vh.adjacentVertices _ CONS[ ah, vh.adjacentVertices ]; ahlsave.rest _ vh.adjacentVertices; -- make list of adjacencies circular out.PutF["\nInsertIntersectionPoint has inserted vertex #%g.\n", IO.int[vh.index]]; RETURN [vh]; }; JoinVerticesOnOutline: PUBLIC PROC[ prew2, w2, w1, forw1: RVHU.VertexHandle, setLRE: BOOL _ TRUE] = { << [prew2, w2] and [w1, forw1] are counterclockwise-oriented edges (with respect to the interior of the figure) on an outline. It is assumed that edges between w2 and w1 will lie external to the current outline, and that an edge from w1 to w2 will extend this outline in such a way that the exterior of the new outline will lie to the left of this edge. Edges between w2 and w1 are created, in such a fashion that prew2 follows w1 in the clockwise ordering of adjacent vertices of w2, and forw1 precedes w2 in the clockwise ordering of adjacent vertices of w1. We first set up the edge from w1 to w2 which has leftRegionExterior = TRUE. Then we set up the edge from w2 to w1, which typically creates a polygon (hence the default setLRE _ TRUE), and (unless setLRE _ FALSE) we go around this polygon setting leftRegionExterior = FALSE and leftState= NIL.>> ahl, ahltrail, ahltemp: RVHU.AdjacencyHandleList; w2Toprew2, prew2Tow2, w1Toforw1, forw1Tow1, ah: RVHU.AdjacencyHandle; <<>> <> [prew2Tow2, w2Toprew2] _ RVHU.FindAdjacency[ prew2, w2]; [w1Toforw1, forw1Tow1] _ RVHU.FindAdjacency[ w1, forw1]; <> ah _ NEW[ RVHU.Adjacency _ [vertex: w2, leftState: NIL, -- we are in the exterior of the outline, so there is no state leftRegionVisited : prew2Tow2.leftRegionVisited, leftRegionExterior : TRUE, intersectionPolygonEdge : FALSE ] ]; <> ahl _ w1.adjacentVertices; ahltrail _ ahl; ahl _ ahl.rest; WHILE ahltrail.first.vertex # forw1 DO ahltrail _ ahl; ahl _ ahl.rest; ENDLOOP; ahltemp _ CONS[ah, ahl]; ahltrail.rest _ ahltemp; <> ah _ NEW[ RVHU.Adjacency _ [vertex: w1, leftState: NIL, -- we are in the exterior of the outline, so there is no state leftRegionVisited : prew2Tow2.leftRegionVisited, leftRegionExterior : FALSE, intersectionPolygonEdge : FALSE ] ]; <> ahl _ w2.adjacentVertices; ahltrail _ ahl; ahl _ ahl.rest; WHILE ahl.first.vertex # prew2 DO ahltrail _ ahl; ahl _ ahl.rest; ENDLOOP; ahltemp _ CONS[ah, ahl]; ahltrail.rest _ ahltemp; <> IF setLRE THEN RVHU.SetPolygonState[w2, w1, NIL, TRUE]; }; JoinVerticesInLens: PUBLIC PROC[ pj1, pj, qi1, qi: RVHU.VertexHandle] = { << [pj1,pj] is a counterclockwise-oriented edge on the inner polygon. [qi1,qi] is a counterclockwise-oriented edge on the outer polygon. Edges between pj1 and qi1 are created, in such a fashion that qi1 follows pj in the clockwise ordering of adjacent vertices of pj1, and qi follows pj1 in the clockwise ordering of adjacent vertices of qi1. leftField values (leftState, leftRegionVisited) are inherited from edge [qi1,qi], i.e. the inward facing edge of the outer polygon.>> ahl, ahltrail, ahltemp: RVHU.AdjacencyHandleList; qi1Toqi, qiToqi1, ah: RVHU.AdjacencyHandle; <<>> <> [qi1Toqi, qiToqi1] _ RVHU.FindAdjacency[ qi1, qi]; <> ah _ NEW[ RVHU.Adjacency _ [vertex: qi1, leftState: qi1Toqi.leftState, leftRegionVisited : qi1Toqi.leftRegionVisited, leftRegionExterior : FALSE, intersectionPolygonEdge : FALSE ] ]; <> ahl _ pj1.adjacentVertices; ahltrail _ ahl; ahl _ ahl.rest; WHILE ahltrail.first.vertex # pj DO ahltrail _ ahl; ahl _ ahl.rest; ENDLOOP; ahltemp _ CONS[ah, ahl]; ahltrail.rest _ ahltemp; <> ah _ NEW[ RVHU.Adjacency _ [vertex: pj1, leftState: qi1Toqi.leftState, leftRegionVisited : qi1Toqi.leftRegionVisited, leftRegionExterior : FALSE, intersectionPolygonEdge : FALSE ] ]; <> ahl _ qi1.adjacentVertices; ahltrail _ ahl; ahl _ ahl.rest; WHILE ahl.first.vertex # qi DO ahltrail _ ahl; ahl _ ahl.rest; ENDLOOP; ahltemp _ CONS[ah, ahl]; ahltrail.rest _ ahltemp; out.PutF["\nJoinVerticesInLens has joined vertices #%g and #%g\n", IO.int[pj1.index], IO.int[qi1.index]]; }; <> SetFigureVisitedValues: PUBLIC PROC[v: RVHU.VertexHandle, visitedValue: BOOLEAN] = { <> IF v = NIL THEN RETURN; -- no vertices IF v.adjacentVertices = NIL THEN { v.visited _ visitedValue; RETURN }; -- one vertex SetFigureVisitedValuesSubr[v, visitedValue ]; -- two or more vertices RETURN; }; SetFigureVisitedValuesSubr: PROC[v: RVHU.VertexHandle, visitedValue: BOOLEAN] = { <> vAdjList: RVHU.AdjacencyHandleList _ v.adjacentVertices; nextAdjacency: RVHU.AdjacencyHandle; lastVertex, nextVertex: RVHU.VertexHandle; done: BOOL _ FALSE; v.visited _ visitedValue; -- record that have visited this vertex <> lastVertex _ vAdjList.first.vertex; vAdjList _ vAdjList.rest; -- shift past marker vertex (i.e. first iteration of loop begins after it) done _ FALSE; WHILE NOT done DO nextAdjacency _ vAdjList.first; nextVertex _ nextAdjacency.vertex; IF nextVertex = lastVertex THEN done _ TRUE; -- test for last vertex to be processed IF (nextVertex.visited # visitedValue) THEN SetFigureVisitedValuesSubr[ nextVertex, visitedValue]; -- Recursive call for w vAdjList _ vAdjList.rest; ENDLOOP; RETURN; }; ClearIntersectPolygonFields: PUBLIC PROC[v, w: RVHU.VertexHandle] = { <<[intersectionPolygonv, intersectionPolygonw] is a (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. The leftRegionVisited and intersectionPolygonEdge fields of all edges of all polygons interior to the intersection polygon are cleared. The algorithm uses Depth First Search.>> vTow, wTov: RVHU.AdjacencyHandle; firstv: RVHU.VertexHandle _ v; outline: BOOL _ FALSE; <> out.PutF["\nClearIntersectPolygonFields entered with argument [#%g , #%g ] \n", IO.int[v.index], IO.int[w.index] ]; <<>> <> [ vTow, wTov ] _ RVHU.FindAdjacency[ v, w ]; vTow.leftRegionVisited _ FALSE; vTow.intersectionPolygonEdge _ FALSE; WHILE w # firstv DO [v, w] _ RVHU.StepVertex[v,w, outline]; [ vTow, wTov ] _ RVHU.FindAdjacency[ v, w ]; vTow.leftRegionVisited _ FALSE; vTow.intersectionPolygonEdge _ FALSE; ENDLOOP; <> [v, w] _ RVHU.StepVertex[v,w, outline]; [ vTow, wTov ] _ RVHU.FindAdjacency[ v, w ]; IF wTov.leftRegionVisited THEN ClearIntersectPolygonFields[w, v]; WHILE w # firstv DO [v, w] _ RVHU.StepVertex[v,w, outline]; [ vTow, wTov ] _ RVHU.FindAdjacency[ v, w ]; IF wTov.leftRegionVisited THEN ClearIntersectPolygonFields[w, v]; ENDLOOP; }; END. <<>>