<> <> <<>> DIRECTORY Rope, Convert, IO, Imager, ImagerPath, RealFns, List, RatNums, EuclideanGraphs, ConvexEuclideanGraphs; ConvexEuclideanGraphsImpl: CEDAR PROGRAM IMPORTS IO, Rope, Convert, ImagerPath, RealFns, List, RatNums, EuclideanGraphs EXPORTS ConvexEuclideanGraphs = BEGIN OPEN RN: RatNums, EG: EuclideanGraphs, ConvexEuclideanGraphs; <<>> <<************** Hull Computation **************>> ConvexHull: PUBLIC PROC [L: PointList] RETURNS [Hull: PointList] ~ { <> <> xtemp, ytemp: RN.RatNum; n: CARDINAL _ 1; I: CARDINAL; numLoops: CARDINAL; nRat: RN.RatNum; interiorP: Point; PointArray: TYPE = ARRAY [1..30] OF Point; pointArray: PointArray; tempPoint: Point; flip: BOOL; <> Compactify: PROC [j: CARDINAL] ~ { <> n _ n-1; FOR jC: CARDINAL IN [j..n] DO pointArray[jC] _ pointArray[jC+1]; ENDLOOP; }; MyMOD: PROC [K, N: CARDINAL] RETURNS [CARDINAL] ~ { IF K MOD N = 0 THEN RETURN[N] ELSE RETURN[K MOD N]; }; <<[in, out] _ ViewerIO.CreateViewerStreams[IO.PutFR["ConvexHull Log"]];>> <<>> <> n _ 0; WHILE L # NIL DO n _ n + 1; pointArray[n] _ [ L.first.x, L.first.y ]; <> L _ L.rest; ENDLOOP; <> I _ 1; WHILE I <= n-2 DO IF EG.PointLineTest[pointArray[I], pointArray[I+1], pointArray[I+2]]#ONLINE THEN EXIT; I _ I+1; ENDLOOP; IF EG.PointLineTest[pointArray[I], pointArray[I+1], pointArray[I+2]]=ONLINE THEN ERROR; -- noncollinear set of three points not found xtemp _ pointArray[I].x; ytemp _ pointArray[I].y; xtemp _ RN.RatNumAdd[xtemp, pointArray[I+1].x]; ytemp _ RN.RatNumAdd[ytemp, pointArray[I+1].y] ; xtemp _ RN.RatNumAdd[xtemp, pointArray[I+2].x]; ytemp _ RN.RatNumAdd[ytemp, pointArray[I+2].y]; nRat _ RN.RatNumFromSmallCards[1, 3, 1 ]; interiorP _ [x: RN.RatNumDivide[ xtemp , nRat ], y: RN.RatNumDivide[ ytemp , nRat ] ]; <> <> FOR I IN [1..n] DO pointArray[I] _ [x: RN.RatNumSubtract[ pointArray[I].x, interiorP.x], y: RN.RatNumSubtract[ pointArray[I].y , interiorP.y] ]; ENDLOOP; <> <<- what happens to points equal to interiorP, and multiple occurrences of points?>> FOR I DECREASING IN [1..n-1] DO FOR J:CARDINAL IN [1..I] DO SELECT RN.RatNumCompare[pointArray[J].y, RN.MakeRatNumZero[]] FROM ratGreater => SELECT RN.RatNumCompare[pointArray[J+1].y, RN.MakeRatNumZero[]] FROM ratGreater => flip _ RealFns.ArcTan[ RN.RatNumToREAL[pointArray[J].y], RN.RatNumToREAL[pointArray[J].x] ] > RealFns.ArcTan[ RN.RatNumToREAL[pointArray[J+1].y], RN.RatNumToREAL[pointArray[J+1].x] ]; ratLess => flip _ FALSE; ratEqual => SELECT RN.RatNumPositive[pointArray[J+1].x ] FROM TRUE => flip _ TRUE; -- J+1 on pos x -axis, hence less than J FALSE => flip _ FALSE; -- J+1 on neg x -axis, hence greater ENDCASE => ERROR; ENDCASE => ERROR; ratLess => SELECT RN.RatNumCompare[pointArray[J+1].y, RN.MakeRatNumZero[]] FROM ratGreater => flip _ TRUE; ratLess => flip _ RealFns.ArcTan[ RN.RatNumToREAL[pointArray[J].y], RN.RatNumToREAL[pointArray[J].x] ] > RealFns.ArcTan[ RN.RatNumToREAL[pointArray[J+1].y], RN.RatNumToREAL[pointArray[J+1].x] ]; ratEqual => flip _ TRUE; -- whether on positive or neg x-axis, J+1 less than J ENDCASE => ERROR; ratEqual => SELECT RN.RatNumCompare[pointArray[J].x, RN.MakeRatNumZero[] ] FROM ratGreater => flip _ FALSE; -- J on pos x -axis, hence less than J+1 ratLess => -- J on neg x-axis SELECT RN.RatNumCompare[pointArray[J+1].y, RN.MakeRatNumZero[]] FROM ratGreater => flip _ TRUE; ratLess => flip _ FALSE; ratEqual => SELECT RN.RatNumPositive[pointArray[J+1].x ] FROM TRUE => flip _ TRUE; -- J+1 on pos x -axis, hence less than J FALSE => flip _ FALSE; -- J+1 on neg x -axis, hence equal ENDCASE => ERROR; ENDCASE => ERROR; ratEqual => ERROR; -- J = interiorP; not yet handled ENDCASE => ERROR; ENDCASE => ERROR; <> IF flip THEN { tempPoint _ pointArray[J]; pointArray[J] _ pointArray[J+1]; pointArray[J+1] _ tempPoint; }; ENDLOOP; ENDLOOP; <> <> <> <> <> I _ 1; numLoops _ 2 * n; -- doesn't matter if we continue walking around longer than necessary (n may decrease in the course of this loop) FOR J:CARDINAL IN [1.. numLoops] DO WHILE EG.PointEqual[pointArray[MyMOD[I,n]], pointArray[MyMOD[I+1,n] ]] DO Compactify[MyMOD[I+1,n]]; -- check for and remove duplicate points ENDLOOP; WHILE EG.PointLineTest[pointArray[MyMOD[I,n]], pointArray[MyMOD[I+1,n]], pointArray[MyMOD[I+2,n]] ] = RIGHTOFLINE DO Compactify[MyMOD[I+1,n]]; I _ MyMOD[I-1,n]; ENDLOOP; I _ MyMOD[I+1,n]; ENDLOOP; <<>> <> Hull _ NIL; FOR I DECREASING IN [1..n] DO Hull _ CONS [ [x: RN.RatNumAdd[ pointArray[I].x, interiorP.x], y: RN.RatNumAdd[ pointArray[I].y, interiorP.y] ], Hull]; ENDLOOP; }; <<>> <<************** Graph Structure **************>> ThreeOrMoreVertices: PUBLIC PROC [w: EG.EuclideanGraph] RETURNS [BOOL] = { hasThreeVertices: BOOL; hasThreeVertices _ w # NIL; -- test for 0 vertices IF hasThreeVertices THEN hasThreeVertices _ w.adjacentVertices # NIL; -- test for 1 vertex only IF hasThreeVertices THEN hasThreeVertices _ w.adjacentVertices.first.vertex # w.adjacentVertices.rest.first.vertex; -- test for 2 vertices only RETURN[ hasThreeVertices ]; }; AddEdge: PUBLIC PROC [root, adjacentVertex: Vertex, exterior: BOOL _ FALSE, IPEdge: BOOL _ FALSE, clientData: REF _ NIL, visitedValue: BOOL _ FALSE] ~ { cEGEdgeData: CEGEdgeData _ NEW[CEGEdgeDataRec _ [exteriorEdge: exterior, intersectionPolygonEdge: IPEdge, clientData: clientData]]; EG.AddEdge[root, adjacentVertex, cEGEdgeData, visitedValue]; }; InsertVertexInEdges: PUBLIC PROC [v, w: Vertex, p: Point, vertexData: REF _ NIL] RETURNS [newVertex: Vertex] ~ { vTow, wTov: Adjacency; vTowData, wTovData: CEGEdgeData; z: Vertex _ EG.CreateVertex[p, vertexData, v.visited]; [vTow, wTov] _ EG.FindAdjacency[v, w]; vTowData _ NARROW[vTow.data]; wTovData _ NARROW[wTov.data]; AddEdge[z, w, vTowData.exteriorEdge, vTowData.intersectionPolygonEdge, vTowData.clientData, vTow.visited]; EG.DeleteEdge[v, w]; AddEdge[v, z, vTowData.exteriorEdge, vTowData.intersectionPolygonEdge, vTowData.clientData, vTow.visited]; AddEdge[z, v, wTovData.exteriorEdge, wTovData.intersectionPolygonEdge, wTovData.clientData, wTov.visited]; EG.DeleteEdge[w, v]; AddEdge[w, z, wTovData.exteriorEdge, wTovData.intersectionPolygonEdge, wTovData.clientData, wTov.visited]; RETURN[z]; }; JoinVertices: PUBLIC PROC [start, end: Vertex, startToEndData, endToStartData: REF _ NIL, startToEndIPEdge, endToStartIPEdge: BOOL _ FALSE, startToEndExterior, endToStartExterior: BOOL _ FALSE, startToEndVisited, endToStartVisited: BOOL _ FALSE] ~ { startToEndCEGData: CEGEdgeData _ NEW[CEGEdgeDataRec _ [exteriorEdge: startToEndExterior, intersectionPolygonEdge: startToEndIPEdge, clientData: startToEndData]]; endToStartCEGData: CEGEdgeData _ NEW[CEGEdgeDataRec _ [exteriorEdge: endToStartExterior, intersectionPolygonEdge: endToStartIPEdge, clientData: endToStartData]]; EG.AddEdge[start, end, startToEndCEGData, startToEndVisited]; EG.AddEdge[end, start, endToStartCEGData, endToStartVisited]; }; <<>> <<>> <<************** Graph Traversal **************>> StepVertex: PUBLIC PROC[ v1, w1: Vertex, outline: BOOL] RETURNS [ v2, w2: Vertex] = { RETURN [w1, NextVertex[ v1, w1, outline] ] }; NextVertex: PUBLIC PROC[ v, w: Vertex, outline: BOOL] RETURNS [ z: Vertex] = { IF outline THEN z _ NextOutlineVertex[v,w] ELSE z _ NextPolygonVertex[v,w]; RETURN [z] }; PreviousVertex: PUBLIC PROC[ v, w: Vertex, outline: BOOL] RETURNS [ z: Vertex] = { IF outline THEN z _ PreviousOutlineVertex[v,w] ELSE z _ PreviousPolygonVertex[v,w]; RETURN [z] }; NextOutlineVertex: PUBLIC PROC[ v, w: Vertex] RETURNS [ z: Vertex] = { A: AdjacencyList _ w.adjacentVertices; z _ A.first.vertex; A _ A.rest; WHILE A.first.vertex # v DO z _ A.first.vertex; A _ A.rest; ENDLOOP; RETURN [z] }; NextPolygonVertex: PUBLIC PROC[ v, w: Vertex] RETURNS [ Vertex] = { A: AdjacencyList _ w.adjacentVertices; WHILE A.first.vertex # v DO A _ A.rest ENDLOOP; RETURN [A.rest.first.vertex] }; SpecialPreviousOutlineVertex: PUBLIC PROC [w: Vertex] RETURNS [v:Vertex] ~ { <> ahl: AdjacencyList _ w.adjacentVertices; WHILE NOT GetEdgeExterior[ahl.first] DO ahl _ ahl.rest ENDLOOP; v _ ahl.first.vertex; }; PreviousOutlineVertex: PUBLIC PROC [v, w: Vertex] RETURNS [z: Vertex] ~ { <> A: AdjacencyList _ v.adjacentVertices; WHILE A.first.vertex # w DO A _ A.rest ENDLOOP; RETURN [A.rest.first.vertex] }; PreviousPolygonVertex: PUBLIC PROC [v, w: Vertex] RETURNS [z:Vertex] ~ { <<[v, w] is an edge on a polygon containing at least two vertices. Find the vertex z which precedes v in the counterclockwise ordering of vertices (we think of this counterclockwise ordering as being defined with respect to the INTERIOR of the polygon on which [v, w] lies).>> A: AdjacencyList _ v.adjacentVertices; z _ A.first.vertex; A _ A.rest; WHILE A.first.vertex # w DO z _ A.first.vertex; A _ A.rest; ENDLOOP; RETURN [z] }; <<>> <<************** Edge Fields **************>> GetEdgeClientData: PUBLIC PROC [startToEnd: Adjacency] RETURNS [data: REF ANY] = { cEGEdgeData: CEGEdgeData _ NARROW[startToEnd.data]; RETURN[cEGEdgeData.clientData]; }; <<>> SetEdgeClientData: PUBLIC PROC [startToEnd: Adjacency, data: REF ANY] = { cEGEdgeData: CEGEdgeData _ NARROW[startToEnd.data]; cEGEdgeData.clientData _ data; }; <<>> SetPolygonClientData: PUBLIC PROC [start, end: Vertex, data: REF, setVisited: BOOL _ FALSE] = { startToEnd, endToStart: Adjacency; firstStart: Vertex _ start; [ startToEnd, endToStart ] _ EG.FindAdjacency[ start, end ]; SetEdgeClientData[startToEnd, data]; IF setVisited THEN startToEnd.visited _ TRUE; WHILE end # firstStart DO [start, end] _ StepVertex[start, end, FALSE]; [ startToEnd, endToStart ] _ EG.FindAdjacency[ start, end ]; SetEdgeClientData[startToEnd, data]; IF setVisited THEN startToEnd.visited _ TRUE; ENDLOOP; }; <<>> GetEdgeExterior: PUBLIC PROC [startToEnd: Adjacency] RETURNS [value: BOOL] ~ { cEGEdgeData: CEGEdgeData _ NARROW[startToEnd.data]; RETURN[cEGEdgeData.exteriorEdge]; }; SetEdgeExterior: PUBLIC PROC [startToEnd: Adjacency, value: BOOL] ~ { cEGEdgeData: CEGEdgeData _ NARROW[startToEnd.data]; cEGEdgeData.exteriorEdge _ value; }; <<>> GetEdgeIPEdge: PUBLIC PROC [startToEnd: Adjacency] RETURNS [value: BOOL] ~ { cEGEdgeData: CEGEdgeData _ NARROW[startToEnd.data]; RETURN[cEGEdgeData.intersectionPolygonEdge]; }; <<>> SetEdgeIPEdge: PUBLIC PROC [startToEnd: Adjacency, value: BOOL] ~ { cEGEdgeData: CEGEdgeData _ NARROW[startToEnd.data]; cEGEdgeData.intersectionPolygonEdge _ value; }; <<>> SetPolygonIPEdges: PUBLIC PROC [start, end: Vertex, value: BOOL] ~ { startToEnd, endToStart: Adjacency; firstStart: Vertex _ start; [ startToEnd, endToStart ] _ EG.FindAdjacency[ start, end ]; SetEdgeIPEdge[startToEnd, value]; WHILE end # firstStart DO [start, end] _ StepVertex[start,end, FALSE]; -- polygon step [ startToEnd, endToStart ] _ EG.FindAdjacency[ start, end ]; SetEdgeIPEdge[startToEnd, value]; ENDLOOP; }; ClearGraphIPEdges: PUBLIC PROC[v, w: Vertex] = { startToEnd, endToStart: Adjacency; firstIntersection: Vertex _ v; outline: BOOL _ FALSE; <> [ startToEnd, endToStart ] _ EG.FindAdjacency[ v, w ]; startToEnd.visited _ FALSE; SetEdgeIPEdge[startToEnd, FALSE]; WHILE w # firstIntersection DO [v, w] _ StepVertex[v,w, outline]; [ startToEnd, endToStart ] _ EG.FindAdjacency[ v, w ]; startToEnd.visited _ FALSE; SetEdgeIPEdge[startToEnd, FALSE]; ENDLOOP; <> [v, w] _ StepVertex[v,w, outline]; [ startToEnd, endToStart ] _ EG.FindAdjacency[ v, w ]; IF endToStart.visited THEN ClearGraphIPEdges[w, v]; WHILE w # firstIntersection DO [v, w] _ StepVertex[v,w, outline]; [ startToEnd, endToStart ] _ EG.FindAdjacency[ v, w ]; IF endToStart.visited THEN ClearGraphIPEdges[w, v]; ENDLOOP; }; <<>> IPVertexToEdge: PUBLIC PROC [intersectionPolyVertex: Vertex] RETURNS [intersectionPolyNext: Vertex] ~ { adjacencies: AdjacencyList _ intersectionPolyVertex.adjacentVertices; WHILE NOT GetEdgeIPEdge[adjacencies.first] DO adjacencies _ adjacencies.rest; ENDLOOP; RETURN[adjacencies.first.vertex]; }; <<>> IPVertex: PUBLIC PROC [v: Vertex] RETURNS [BOOL] ~ { adjacencies: AdjacencyList _ v.adjacentVertices; adjHead: AdjacencyList _ v.adjacentVertices; IF adjacencies = NIL THEN RETURN[FALSE]; IF GetEdgeIPEdge[adjacencies.first] THEN RETURN[TRUE]; adjacencies _ adjacencies.rest; WHILE adjacencies # adjHead DO IF GetEdgeIPEdge[adjacencies.first] THEN RETURN[TRUE]; adjacencies_ adjacencies.rest; ENDLOOP; RETURN[FALSE]; }; <<>> ClearEdgeVisitedFields: PUBLIC PROC [v, w: Vertex] = { <<[v,w] is a counterclockwise oriented edge of a polygon contained in the outline of the current figure. Clear the visited fields of all edges of all polygons interior to a Vertex, assumed by this particular ClearEdgeVisitedFields to be an Vertex. Uses Depth First Search.>> vTow, wTov: Adjacency; firstv: Vertex _ v; outline: BOOL _ FALSE; <> [ vTow, wTov ] _ EG.FindAdjacency[ v, w ]; vTow.visited _ FALSE; WHILE w # firstv DO [v, w] _ StepVertex[v,w, outline]; [ vTow, wTov ] _ EG.FindAdjacency[ v, w ]; vTow.visited _ FALSE; ENDLOOP; <> [v, w] _ StepVertex[v, w, outline]; [ vTow, wTov ] _ EG.FindAdjacency[ v, w ]; IF wTov.visited THEN IF NOT GetEdgeExterior[wTov] THEN ClearEdgeVisitedFields[w, v ] ELSE wTov.visited _ FALSE; WHILE w # firstv DO [v, w] _ StepVertex[v,w, outline]; [ vTow, wTov ] _ EG.FindAdjacency[ v, w ]; IF wTov.visited THEN IF NOT GetEdgeExterior[wTov] THEN ClearEdgeVisitedFields[w, v] ELSE wTov.visited _ FALSE; ENDLOOP; }; ClearGraphEdgeFields: PUBLIC PROC [v: Vertex] ~ { <> Subr: PROC [v: Vertex, visitedValue: BOOL] ~ { vAdjList: AdjacencyList _ v.adjacentVertices; firstVertex, nextVertex: Vertex; vToNext, nextToV: Adjacency; <> firstVertex _ nextVertex _ vAdjList.first.vertex; [vToNext, nextToV] _ EG.FindAdjacency[v, nextVertex] ; vToNext.visited _ FALSE; SetEdgeIPEdge[vToNext, FALSE]; vAdjList _ vAdjList.rest; nextVertex _ vAdjList.first.vertex; WHILE nextVertex#firstVertex DO [vToNext, nextToV] _ EG.FindAdjacency[v, nextVertex] ; vToNext.visited _ FALSE; SetEdgeIPEdge[vToNext, FALSE]; vAdjList _ vAdjList.rest; nextVertex _ vAdjList.first.vertex; ENDLOOP; v.visited _ visitedValue; -- now we can say that we've been here. <> IF (nextVertex.visited # visitedValue) THEN Subr[nextVertex, visitedValue]; vAdjList _ vAdjList.rest; nextVertex _ vAdjList.first.vertex; WHILE nextVertex#firstVertex DO IF (nextVertex.visited # visitedValue) THEN Subr[nextVertex, visitedValue]; vAdjList _ vAdjList.rest; nextVertex _ vAdjList.first.vertex; ENDLOOP; }; IF v = NIL OR v.adjacentVertices = NIL THEN RETURN ELSE Subr[v, NOT v.visited]; }; SetOutwardOutlineEdgeFields: PUBLIC PROC [start, end: Vertex, exteriorEdgeValue, intersectionPolygonEdgeValue: BOOL, clientDataValue: REF _ NIL] ~ { cEGEdgeData: CEGEdgeData; startToEnd, endToStart: Adjacency; firstStart: Vertex _ start; [ startToEnd, endToStart ] _ EG.FindAdjacency[ start, end ]; cEGEdgeData _ NARROW[endToStart.data]; cEGEdgeData.exteriorEdge _ exteriorEdgeValue; cEGEdgeData.intersectionPolygonEdge _ intersectionPolygonEdgeValue; cEGEdgeData.clientData _ clientDataValue; WHILE end # firstStart DO [start, end] _ StepVertex[start,end, TRUE]; -- outline step [ startToEnd, endToStart ] _ EG.FindAdjacency[ start, end ]; cEGEdgeData _ NARROW[endToStart.data]; cEGEdgeData.exteriorEdge _ exteriorEdgeValue; cEGEdgeData.intersectionPolygonEdge _ intersectionPolygonEdgeValue; cEGEdgeData.clientData _ clientDataValue; ENDLOOP; }; SetPolygonFields: PUBLIC PROC [start, end: Vertex, exteriorEdgeValue, intersectionPolygonEdgeValue: BOOL _ FALSE, clientDataValue: REF _ NIL] ~ { cEGEdgeData: CEGEdgeData; startToEnd, endToStart: Adjacency; firstStart: Vertex _ start; [ startToEnd, endToStart ] _ EG.FindAdjacency[start, end]; cEGEdgeData _ NARROW[startToEnd.data]; cEGEdgeData.exteriorEdge _ exteriorEdgeValue; cEGEdgeData.intersectionPolygonEdge _ intersectionPolygonEdgeValue; cEGEdgeData.clientData _ clientDataValue; WHILE end # firstStart DO [start, end] _ StepVertex[start, end, FALSE]; -- polygon step [ startToEnd, endToStart ] _ EG.FindAdjacency[ start, end ]; cEGEdgeData _ NARROW[startToEnd.data]; cEGEdgeData.exteriorEdge _ exteriorEdgeValue; cEGEdgeData.intersectionPolygonEdge _ intersectionPolygonEdgeValue; cEGEdgeData.clientData _ clientDataValue; ENDLOOP; }; <<************** Convex (internal) polygon operations **************>> CenterOfMass: PUBLIC PROC[ v, w : Vertex, outline: BOOL ] RETURNS [Point] = { <<[v,w] is a counterclockwise oriented edge on the polygon>> vfirst: Vertex _ v; xt: RN.RatNum _ v.coordinates.x; yt: RN.RatNum _ v.coordinates.y; n: INTEGER _ 1; nRat: RN.RatNum; WHILE w # vfirst DO xt _ RN.RatNumAdd[ xt , w.coordinates.x ]; yt _ RN.RatNumAdd[ yt , w.coordinates.y ]; n _ n + 1; [v,w] _ StepVertex[ v, w, outline ]; ENDLOOP; nRat _ RN.RatNumFromSmallCards[1, n, 1 ]; RETURN[ [x: RN.RatNumDivide[ xt , nRat ], y: RN.RatNumDivide[ yt , nRat ] ] ]; }; CountPolygonVertices: PUBLIC PROC [start, end: Vertex, outline: BOOL _ FALSE] RETURNS [numVertices: CARDINAL] ~ { firstStart: Vertex _ start; numVertices _ 1; WHILE end # firstStart DO numVertices _ numVertices + 1; [start, end] _ StepVertex[start, end, outline]; ENDLOOP; }; AddVertexToPolygon: PUBLIC PROC [entryPrior, entryNext: Vertex, coordinates: Point, clientData: REF _ NIL] RETURNS [exitPrior, exitNext: Vertex] = { <> newVertex: Vertex _ EG.CreateVertex[coordinates, NIL, FALSE]; numVertices: CARDINAL; priorToNext, nextToPrior: Adjacency; edgeVisitedValue: BOOL; IF entryNext = NIL THEN RETURN[NIL, newVertex]; -- no vertices previously newVertex.visited _ entryNext.visited; IF entryPrior = NIL THEN { -- one vertex previously AddEdge[newVertex, entryNext, FALSE, FALSE, clientData, FALSE]; AddEdge[entryNext, newVertex, TRUE, FALSE, NIL, FALSE]; RETURN[newVertex, entryNext]; }; [priorToNext, nextToPrior] _ EG.FindAdjacency[entryPrior, entryNext]; edgeVisitedValue _ priorToNext.visited; numVertices _ CountPolygonVertices[entryPrior, entryNext]; -- do before SeparateVertices EG.SeparateVertices[entryPrior, entryNext]; AddEdge[entryPrior, newVertex, FALSE, FALSE, clientData, edgeVisitedValue]; AddEdge[newVertex, entryPrior, TRUE, FALSE, NIL, edgeVisitedValue]; AddEdge[newVertex, entryNext, FALSE, FALSE, clientData, edgeVisitedValue]; AddEdge[entryNext, newVertex, TRUE, FALSE, NIL, edgeVisitedValue]; IF numVertices = 2 THEN { AddEdge[entryNext, entryPrior, FALSE, FALSE, clientData, edgeVisitedValue]; AddEdge[entryPrior, entryNext, TRUE, FALSE, NIL, edgeVisitedValue]; }; RETURN[newVertex, entryNext]; }; PointSectorTest: PUBLIC PROC [rightvertex, leftvertex, centerOfMass, test: Point] RETURNS[PointSectorRelation _ EQUALCOM] = { <> pointEdgeRelation: EG.PointDirectedEdgeRelation _ EG.PointDirectedEdgeTest[ centerOfMass, rightvertex, test]; SELECT pointEdgeRelation FROM BEFORESTART => RETURN[ OUTSIDESUBTEND ]; EQUALSTART => RETURN[ EQUALCOM ]; BETWEENSTARTEND => RETURN[ RIGHTSPOKEINTERIOR ]; EQUALEND => RETURN[ EQUALRIGHTVERTEX ]; AFTEREND => RETURN[ RIGHTRAYINTERIOR ]; RIGHTOFEDGE => RETURN[ OUTSIDESUBTEND ]; LEFTOFEDGE => { pointEdgeRelation _ EG.PointDirectedEdgeTest[ centerOfMass, leftvertex, test]; SELECT pointEdgeRelation FROM BEFORESTART => RETURN[ OUTSIDESUBTEND ]; BETWEENSTARTEND => RETURN[ LEFTSPOKEINTERIOR ]; EQUALEND => RETURN[ EQUALLEFTVERTEX ]; AFTEREND => RETURN[ LEFTRAYINTERIOR ]; LEFTOFEDGE => RETURN[ OUTSIDESUBTEND ]; RIGHTOFEDGE => { pointLineRelation: EG.PointLineRelation _ EG.PointLineTest[ rightvertex, leftvertex, test]; SELECT pointLineRelation FROM ONLINE => RETURN[POLYGONEDGEINTERIOR]; LEFTOFLINE => RETURN[SECTORINTERIOR]; RIGHTOFLINE => RETURN[SUBTENDINTERIOR]; ENDCASE; }; ENDCASE => ERROR; -- EQUALSTART shouldn't occur }; ENDCASE; }; FindSubtendForPoint: PUBLIC PROC[v, w: Vertex, centerOfMass, test: Point, outline: BOOL ] RETURNS [status: PointSectorRelation, t, u: Vertex] = { <<[v,w] is a counterclockwise oriented edge on the polygon. [t, u] is a counterclockwise oriented edge on the polygon such that test lies in the closure of the subtend defined by [t, u] and the polygon's center of mass. If test = centerOfMass, then status = EQUALCOM and [t, u] _ [v, w].>> pointSectorRelation: PointSectorRelation _ PointSectorTest[ v.coordinates, w.coordinates, centerOfMass, test]; WHILE pointSectorRelation = OUTSIDESUBTEND DO [v, w] _ StepVertex [ v, w, outline]; pointSectorRelation _ PointSectorTest[ v.coordinates, w.coordinates, centerOfMass, test]; ENDLOOP; RETURN[ pointSectorRelation, v, w ]; }; VertexExternalToPolygon: PUBLIC PROC [firstCOM: Point, firstStart, firstEnd, secondStart, secondEnd: Vertex] RETURNS [found: BOOL, newFirstStart, newFirstEnd, newSecondStart, newSecondEnd: Vertex _ NIL] ~ { pointSectorStatus: PointSectorRelation; initSecondVertex: Vertex _ secondStart; done: BOOL _ FALSE; [pointSectorStatus, newFirstStart, newFirstEnd] _ FindSubtendForPoint[ firstStart, firstEnd, firstCOM, secondStart.coordinates, FALSE ]; -- [v5,w5] defines a particular sector of this polygon WHILE NOT done DO IF pointSectorStatus = RIGHTRAYINTERIOR OR pointSectorStatus = LEFTRAYINTERIOR OR pointSectorStatus = SUBTENDINTERIOR THEN RETURN[TRUE, newFirstStart, newFirstEnd, secondStart, secondEnd]; [secondStart, secondEnd] _ StepVertex[secondStart, secondEnd, FALSE]; IF secondStart = initSecondVertex THEN done _ TRUE ELSE [pointSectorStatus, newFirstStart, newFirstEnd] _ FindSubtendForPoint[newFirstStart, newFirstEnd, firstCOM, secondStart.coordinates, FALSE ]; ENDLOOP; RETURN[FALSE, newFirstStart, newFirstEnd, newSecondStart, newSecondEnd]; }; ConvexPolygon: PUBLIC PROC[ v, w : Vertex, outline: BOOL ] RETURNS [BOOL] = { <<[v,w] is a counterclockwise oriented edge on the polygon, must have at least 2 (3?) vertices.>> vfirst: Vertex _ v; z: Vertex _ NextVertex[v, w, outline]; IF z = v OR z = w THEN RETURN[TRUE]; SELECT EG.PointLineTest[v.coordinates, w.coordinates, z.coordinates] FROM -- check first angle RIGHTOFLINE => RETURN[FALSE]; LEFTOFLINE => NULL; ONLINE => NULL; -- 1/7/86 allow a 180deg angle ENDCASE; v _ w; [w, z] _ StepVertex[ w, z, outline ]; -- step past WHILE v # vfirst DO SELECT EG.PointLineTest[v.coordinates, w.coordinates, z.coordinates] FROM -- check first angle RIGHTOFLINE => RETURN[FALSE]; LEFTOFLINE => NULL; ONLINE => NULL; -- 1/7/86 allow a 180deg angle ENDCASE; v _ w; [w, z] _ StepVertex[ w, z, outline ]; ENDLOOP; RETURN[TRUE]; }; ConvexPolygonCompare: PUBLIC PROC[ innerCOM: Point, innerStart, innerEnd: Vertex, innerOutline: BOOL, outerStart, outerEnd: Vertex, checkExternal: BOOL _ TRUE] RETURNS [status: ConvexPolygonCompareStatus, innerPrevious, innerCommon, innerNext, outerPrevious, outerCommon, outerNext: Vertex _ NIL] = { external: BOOL _ FALSE; innerStartFirst: Vertex _ innerStart; outerStartFirst: Vertex _ outerStart; pointSectorRelation: PointSectorRelation; pointLineRelation: EG.PointLineRelation; edgeCompareStatus: EG.BiasedEdgeCompareStatus; intersection: Point; polygonStep: BOOL _ FALSE; done: BOOL _ FALSE; CheckEdgeContact: PROC ~ INLINE { <> pointLineRelation _ EG.PointLineTest[innerStart.coordinates, innerEnd.coordinates, outerStart.coordinates]; SELECT pointLineRelation FROM ONLINE => edgeCompareStatus _ Disjoint; -- we assume outerStart is disjoint from the edge. LEFTOFLINE => edgeCompareStatus _ Disjoint; -- <> RIGHTOFLINE => { edgeCompareStatus _ EG.BiasedEdgeCompare[outerStart, outerEnd, innerStart, innerEnd]; SELECT edgeCompareStatus FROM OuterEndEqInnerStart => { outerCommon _ outerEnd; outerEnd _ NextVertex[outerStart, outerCommon, polygonStep]; innerCommon _ innerStart; innerStart _ PreviousVertex[innerCommon, innerEnd, innerOutline]; }; OuterEndInInner => { outerCommon _ outerEnd; innerCommon _ InsertVertexInEdges[innerStart, innerEnd, outerEnd.coordinates]; outerEnd _ NextVertex[outerStart, outerCommon, polygonStep]; -- this statement needs to come after previous one }; OuterEndEqInnerEnd => { outerCommon _ outerEnd; outerEnd _ NextVertex[outerStart, outerCommon, polygonStep]; innerCommon _ innerEnd; innerEnd _ NextVertex[innerStart, innerCommon, innerOutline]; }; InnerStartInOuter => { innerCommon _ innerStart; outerCommon _ InsertVertexInEdges[outerStart, outerEnd, innerStart.coordinates]; innerStart _ PreviousVertex[innerCommon, innerEnd, innerOutline]; -- this statement needs to come after previous one }; ProperIntersection => { intersection _ EG.IntersectLines[innerStart.coordinates, innerEnd.coordinates, outerStart.coordinates, outerEnd.coordinates]; innerCommon _ InsertVertexInEdges[innerStart, innerEnd, intersection]; outerCommon _ InsertVertexInEdges[outerStart, outerEnd, intersection]; }; InnerEndInOuter => { innerCommon _ innerEnd; outerCommon _ InsertVertexInEdges[outerStart, outerEnd, innerEnd.coordinates]; innerEnd _ NextVertex[innerStart, innerCommon, innerOutline]; -- this statement needs to come after previous one }; Disjoint => NULL; -- this one falls through ENDCASE; }; ENDCASE; }; -- CheckEdgeContact pointSectorRelation _ PointSectorTest[ innerStart.coordinates, innerEnd.coordinates, innerCOM, outerEnd.coordinates ]; WHILE NOT done DO SELECT pointSectorRelation FROM RIGHTRAYINTERIOR, LEFTRAYINTERIOR, SUBTENDINTERIOR => NULL; ENDCASE => { -- outerEnd either inside (closed) inner polygon, or R or L of this sector CheckEdgeContact[]; SELECT edgeCompareStatus FROM Disjoint => NULL; ENDCASE => RETURN[Intersection, innerStart, innerCommon, innerEnd, outerStart, outerCommon, outerEnd]; WHILE pointSectorRelation = OUTSIDESUBTEND DO [innerStart, innerEnd] _ StepVertex[innerStart, innerEnd, innerOutline]; -- step inner polygon to catch up with outer polygon edge CheckEdgeContact[]; SELECT edgeCompareStatus FROM Disjoint => NULL; ENDCASE => RETURN[Intersection, innerStart, innerCommon, innerEnd, outerStart, outerCommon, outerEnd]; pointSectorRelation _ PointSectorTest[ innerStart.coordinates, innerEnd.coordinates, innerCOM, outerEnd.coordinates ]; ENDLOOP; }; <> IF checkExternal THEN IF EG.PointLineTest[ outerStart.coordinates, outerEnd.coordinates, innerStartFirst.coordinates] = RIGHTOFLINE THEN external _ TRUE; -- if inner polygon is external to outer polygon, then any vertex of the inner polygon (we arbitrarily picked innerStartFirst) must lie 'external' to at least one edge of the outer polygon. This test will eventually uncover such an outer edge if one exists. [outerStart, outerEnd] _ StepVertex[outerStart, outerEnd, polygonStep]; IF outerStart = outerStartFirst THEN done _ TRUE ELSE pointSectorRelation _ PointSectorTest[ innerStart.coordinates, innerEnd.coordinates, innerCOM, outerEnd.coordinates ]; ENDLOOP; IF external THEN RETURN[External, innerStart, innerCommon, innerEnd, outerStart, outerCommon, outerEnd] ELSE RETURN [Encloses, innerStart, innerCommon, innerEnd, outerStart, outerCommon, outerEnd]; }; <<************** Graph Searching **************>> FindInternalPolygonForPoint: PUBLIC PROC [v, w: Vertex, test: Point] RETURNS [pointSectorStatus: PointSectorRelation, y, z: Vertex] ~ { polygonCOM: Point; v5: Vertex _ v; w5: Vertex _ w; temp: Vertex; polygonCOM _ CenterOfMass[v5, w5, FALSE]; -- COM of current internal polygon. [pointSectorStatus, v5, w5] _ FindSubtendForPoint[ v5, w5, polygonCOM, test, FALSE]; WHILE pointSectorStatus = RIGHTRAYINTERIOR OR pointSectorStatus = LEFTRAYINTERIOR OR pointSectorStatus = SUBTENDINTERIOR DO -- flip flop polygons until you find the one that contains test temp _ v5; v5 _ w5; w5 _ temp; -- flip v5 and w5 to move to next polygon polygonCOM _ CenterOfMass[ v5, w5, FALSE]; [pointSectorStatus, v5, w5] _ FindSubtendForPoint[ v5, w5, polygonCOM, test, FALSE ]; ENDLOOP; RETURN[ pointSectorStatus, v5, w5]; }; SearchInternalPolygonsForPoint: PUBLIC PROC [v, w: Vertex, test: Point] RETURNS [found: BOOL, y, z: Vertex] ~ { polygonCOM: Point; pointSectorStatus: PointSectorRelation; v5: Vertex _ v; w5: Vertex _ w; temp: Vertex; v5Tow5, w5Tov5: Adjacency; [v5Tow5, w5Tov5] _ EG.FindAdjacency[v5, w5]; IF GetEdgeExterior[v5Tow5] THEN ERROR; polygonCOM _ CenterOfMass[ v5, w5, FALSE]; -- COM of current internal polygon. [pointSectorStatus, v5, w5] _ FindSubtendForPoint[ v5, w5, polygonCOM, test, FALSE ]; -- [v5,w5] defines a particular sector of this polygon WHILE pointSectorStatus = RIGHTRAYINTERIOR OR pointSectorStatus = LEFTRAYINTERIOR OR pointSectorStatus = SUBTENDINTERIOR DO -- flip flop polygons until you find the one that contains test temp _ v5; v5 _ w5; w5 _ temp; -- flip v5 and w5 to move to next polygon [ v5Tow5, w5Tov5] _ EG.FindAdjacency[ v5, w5]; IF GetEdgeExterior[v5Tow5] THEN RETURN[FALSE, v, w]; polygonCOM _ CenterOfMass[ v5, w5, FALSE]; [pointSectorStatus, v5, w5] _ FindSubtendForPoint[ v5, w5, polygonCOM, test, FALSE ]; ENDLOOP; RETURN[TRUE, v5, w5]; }; <<>> <<************** Graph Outline **************>> ConvexPolygonOnOutline: PUBLIC PROC[prew2, w2, prew1, w1: Vertex] RETURNS [BOOL] = { <> x, y, z: Vertex; SELECT EG.PointLineTest[w2.coordinates, prew2.coordinates, w1.coordinates] FROM RIGHTOFLINE => RETURN[FALSE]; LEFTOFLINE => NULL; ONLINE => NULL; -- 180deg angle ok ENDCASE; SELECT EG.PointLineTest[prew2.coordinates, w1.coordinates, prew1.coordinates] FROM RIGHTOFLINE => RETURN[FALSE]; LEFTOFLINE => NULL; ONLINE => NULL; ENDCASE; x _ w1; y _ prew1; z _ PreviousOutlineVertex[y, x]; WHILE x # w2 DO SELECT EG.PointLineTest[x.coordinates, y.coordinates, z.coordinates] FROM RIGHTOFLINE => RETURN[FALSE]; LEFTOFLINE => NULL; ONLINE => NULL; ENDCASE; x _ y; y _ z; z _ PreviousOutlineVertex[y, x]; ENDLOOP; RETURN[TRUE]; }; <<>> GrowToConvexOutline: PUBLIC PROC[w2, v, w1: Vertex, verbosity: Verbosity _ NIL] RETURNS [v3, w3: Vertex] = { <> <> <> ok: BOOL _ FALSE; prew1, forw1, prew2, forw2: Vertex; -- in the counterclockwise order on the outline (with respect to interior of figure), we have (prew2, w2, forw2, prew1, w1, forw1) pointLineRelation: EG.PointLineRelation; prew2 _ PreviousOutlineVertex[w2, v]; forw2 _ v; prew1 _ v; forw1 _ NextOutlineVertex[v, w1]; <> WHILE NOT ok DO ok _ TRUE; <> pointLineRelation _ EG.PointLineTest[w1.coordinates, w2.coordinates, prew2.coordinates]; WHILE pointLineRelation = LEFTOFLINE DO ok _ FALSE; IF NOT ConvexPolygonOnOutline[prew2, w2, prew1, w1] THEN { JoinVertices[w1, w2, NIL, NIL, FALSE, FALSE, TRUE, FALSE]; -- [w1, w2] is an exterior edge SetPolygonFields[w2, w1, FALSE, FALSE, NIL]; -- go around newly formed internal polygon setting leftRegionExterior = FALSE and leftClientData= NIL. prew1 _ w2; -- take account of presence of new edge joining w1 and w2 IF verbosity#NIL THEN verbosity.out.PutF["\nGrowToConvexOutline has joined vertices #%g and #%g\n", IO.int[w1.index], IO.int[w2.index]]; }; forw2 _ w2; w2 _ prew2; prew2 _ PreviousOutlineVertex[w2, forw2]; pointLineRelation _ EG.PointLineTest[w1.coordinates, w2.coordinates, prew2.coordinates]; ENDLOOP; <> pointLineRelation _ EG.PointLineTest[w2.coordinates, w1.coordinates, forw1.coordinates]; WHILE pointLineRelation = RIGHTOFLINE DO ok _ FALSE; IF NOT ConvexPolygonOnOutline[ w2, forw2, w1, forw1] THEN { JoinVertices[w2, w1, NIL, NIL, FALSE, FALSE, FALSE, TRUE]; -- [w1, w2] is an exterior edge SetPolygonFields[w2, w1, FALSE, FALSE, NIL]; -- go around newly formed internal polygon setting leftRegionExterior = FALSE and leftClientData= NIL. forw2 _ w1; -- take account of presence of new edge joining w1 and w2 IF verbosity#NIL THEN verbosity.out.PutF["\nGrowToConvexOutline has joined vertices #%g and #%g\n", IO.int[w2.index], IO.int[w1.index]]; }; prew1 _ w1; w1 _ forw1; forw1 _ NextOutlineVertex[prew1, w1]; pointLineRelation _ EG.PointLineTest[w2.coordinates, w1.coordinates, forw1.coordinates]; ENDLOOP; ENDLOOP; JoinVertices[w2, w1, NIL, NIL, FALSE, FALSE, FALSE, TRUE]; -- [w1, w2] is an exterior edge SetPolygonFields[w2, w1, FALSE, FALSE, NIL]; -- go around newly formed internal polygon setting leftRegionExterior = FALSE and leftClientData= NIL. IF verbosity#NIL THEN verbosity.out.PutF["\nGrowToConvexOutline has joined vertices #%g and #%g\n", IO.int[w2.index], IO.int[w1.index]]; RETURN [w2, w1] }; ConvexifyOutline: PUBLIC PROC [outlineStart, outlineEnd: Vertex, verbosity: Verbosity _ NIL] RETURNS [newOutlineStart, newOutlineEnd: Vertex _ NIL] ~ { firstOutlineStart: Vertex _ outlineStart; DO outlineNext: Vertex _ NextVertex[outlineStart, outlineEnd, TRUE]; SELECT EG.PointLineTest[outlineStart.coordinates, outlineEnd.coordinates, outlineNext.coordinates] FROM LEFTOFLINE, ONLINE => { [outlineStart, outlineEnd] _ StepVertex[outlineStart, outlineEnd, TRUE]; IF outlineStart = firstOutlineStart THEN RETURN[outlineStart, outlineEnd]; }; RIGHTOFLINE => { [outlineStart, outlineEnd] _ GrowToConvexOutline[outlineStart, outlineEnd, outlineNext, verbosity]; firstOutlineStart _ outlineStart; }; ENDCASE; ENDLOOP; }; <<************** Region Extraction **************>> InternalPolygons: PUBLIC PROC [v, w: Vertex] RETURNS [RegionList] = { vTow, wTov: Adjacency; firstv: Vertex; outline: BOOL _ FALSE; polygonOutline: Imager.Trajectory; clientData: REF; vec: Imager.VEC; region: Region; outList: RegionList; firstv _ v; vec _ EG.ImagerVecFromPoint[v.coordinates]; polygonOutline _ ImagerPath.MoveTo[vec]; <> [ vTow, wTov ] _ EG.FindAdjacency[ v, w ]; clientData _ GetEdgeClientData[vTow]; -- only need to set state once <> vec _ EG.ImagerVecFromPoint[w.coordinates]; polygonOutline _ ImagerPath.LineTo[polygonOutline, vec ]; vTow.visited _ TRUE; WHILE w # firstv DO [v, w] _ StepVertex[v,w, outline]; vec _ EG.ImagerVecFromPoint[w.coordinates]; polygonOutline _ ImagerPath.LineTo[polygonOutline, vec ]; [ vTow, wTov ] _ EG.FindAdjacency[ v, w ]; vTow.visited _ TRUE; ENDLOOP; region _ NEW[RegionRec _ [outline: polygonOutline, clientData: clientData] ]; outList _ LIST[region]; <> [v, w] _ StepVertex[v, w, outline]; [ vTow, wTov ] _ EG.FindAdjacency[ v, w ]; IF NOT GetEdgeExterior[wTov] THEN IF NOT wTov.visited THEN TRUSTED { outList _ LOOPHOLE[List.Append[LOOPHOLE[outList], LOOPHOLE[InternalPolygons[w, v]]]]; }; WHILE w # firstv DO [v, w] _ StepVertex[v,w, outline]; [ vTow, wTov ] _ EG.FindAdjacency[ v, w ]; IF NOT GetEdgeExterior[wTov] THEN IF NOT wTov.visited THEN TRUSTED { outList _ LOOPHOLE[List.Append[LOOPHOLE[outList], LOOPHOLE[InternalPolygons[w, v]]]]; }; ENDLOOP; RETURN[outList]; }; RegionBoundaryEdge: PROC [start, end: Vertex, isA: IsAProc] RETURNS [BOOL] ~ { XOR: PROC[a, b: BOOLEAN] RETURNS[BOOLEAN] = { IF (a AND b) THEN RETURN[FALSE]; IF (a OR b) THEN RETURN[TRUE]; RETURN[FALSE]; }; startToEnd, endToStart: Adjacency; [startToEnd, endToStart] _ EG.FindAdjacency[start, end]; RETURN[XOR[isA[GetEdgeClientData[startToEnd]], isA[GetEdgeClientData[endToStart]]]]; }; NextRegionBoundaryEdge: PROC[start, end: Vertex, isA: IsAProc] RETURNS [next: Vertex] = { A: AdjacencyList _ end.adjacentVertices; WHILE A.first.vertex # start DO A _ A.rest ENDLOOP; A _ A.rest; next _ A.first.vertex; WHILE NOT RegionBoundaryEdge[end, next, isA] DO A _ A.rest; next _ A.first.vertex; ENDLOOP; RETURN[next]; }; MaximalRegions: PUBLIC PROC [outlineVertex: Vertex, isA: IsAProc, verbosity: Verbosity _ NIL] RETURNS [outRegionList: RegionList] ~ { MaximalRegionsSubr: PROC [v: Vertex, vertexVisitedValue: BOOLEAN, isA: IsAProc, inRegionList: RegionList, verbosity: Verbosity _ NIL] RETURNS [outRegionList: RegionList] ~ { <> vAdjList: AdjacencyList _ v.adjacentVertices; firstVertex, nextVertex: Vertex; vToNext, nextToV: Adjacency; outRegionList _ inRegionList; IF verbosity#NIL THEN verbosity.out.PutF["\nMaximalRegionsSubr entered with argument #%g\n", IO.int[v.index] ]; <> firstVertex _ nextVertex _ vAdjList.first.vertex; [vToNext, nextToV] _ EG.FindAdjacency[v, nextVertex] ; IF RegionBoundaryEdge[v, nextVertex, isA] AND isA[GetEdgeClientData[vToNext]] AND NOT vToNext.visited THEN { IF verbosity#NIL THEN verbosity.out.PutF["\nMaximalRegionsSubr finds region boundary edge [%g, %g]\n", IO.int[v.index], IO.int[nextVertex.index]]; outRegionList _ CONS[RegionBuilder[v, nextVertex, FALSE, vertexVisitedValue, isA, verbosity], outRegionList]; }; vAdjList _ vAdjList.rest; nextVertex _ vAdjList.first.vertex; WHILE nextVertex#firstVertex DO [vToNext, nextToV] _ EG.FindAdjacency[v, nextVertex] ; IF RegionBoundaryEdge[v, nextVertex, isA] AND isA[GetEdgeClientData[vToNext]] AND NOT vToNext.visited THEN { IF verbosity#NIL THEN verbosity.out.PutF["\nMaximalRegionsSubr finds region boundary edge [%g, %g]\n", IO.int[v.index], IO.int[nextVertex.index]]; outRegionList _ CONS[RegionBuilder[v, nextVertex, FALSE, vertexVisitedValue, isA, verbosity], outRegionList]; }; vAdjList _ vAdjList.rest; nextVertex _ vAdjList.first.vertex; ENDLOOP; v.visited _ vertexVisitedValue; -- now we can say that we've been here. <> IF (nextVertex.visited # vertexVisitedValue) THEN outRegionList _ MaximalRegionsSubr[nextVertex, vertexVisitedValue, isA, outRegionList, verbosity]; vAdjList _ vAdjList.rest; nextVertex _ vAdjList.first.vertex; WHILE nextVertex#firstVertex DO IF (nextVertex.visited # vertexVisitedValue) THEN outRegionList _ MaximalRegionsSubr[nextVertex, vertexVisitedValue, isA, outRegionList, verbosity]; vAdjList _ vAdjList.rest; nextVertex _ vAdjList.first.vertex; ENDLOOP; RETURN[outRegionList]; }; IF NOT ThreeOrMoreVertices[outlineVertex] THEN RETURN[NIL]; outRegionList _ MaximalRegionsSubr[outlineVertex, NOT outlineVertex.visited, isA, NIL, verbosity]; ClearGraphEdgeFields[outlineVertex]; RETURN[outRegionList]; }; <<>> RegionBuilder: PUBLIC PROC [outlineStart, outlineEnd: Vertex, setOutlineVerticesVisited: BOOL, vertexVisitedValue: BOOLEAN, isA: IsAProc, verbosity: Verbosity _ NIL] RETURNS [region: Region] ~ { SearchInternalPolygons: PROC [start, end: Vertex, vertexVisitedValue: BOOLEAN, isA: IsAProc, inHoles: RegionList] RETURNS [outHoles: RegionList] ~ { firstStart: Vertex _ start; startToEnd, endToStart: Adjacency; nextStartToNextEnd, nextEndTonextStart: Adjacency; polygonStep: BOOL _ FALSE; outHoles _ inHoles; IF verbosity#NIL THEN verbosity.out.PutF["\nSearchInternalPolygons entered with edge [%g, %g]\n", IO.int[start.index], IO.int[end.index]]; <> [ startToEnd, endToStart ] _ EG.FindAdjacency[start, end]; WHILE end # firstStart DO [start, end] _ StepVertex[start, end, polygonStep]; [nextStartToNextEnd, nextEndTonextStart] _ EG.FindAdjacency[start, end]; nextStartToNextEnd.visited _ TRUE; IF NOT IPVertex[start] THEN start.visited _ vertexVisitedValue; startToEnd _ nextStartToNextEnd; endToStart _ nextEndTonextStart; ENDLOOP; [start, end] _ StepVertex[start, end, polygonStep]; [nextStartToNextEnd, nextEndTonextStart] _ EG.FindAdjacency[start, end]; nextStartToNextEnd.visited _ TRUE; IF NOT IPVertex[start] THEN start.visited _ vertexVisitedValue; <> [ startToEnd, endToStart ] _ EG.FindAdjacency[start, end]; IF NOT GetEdgeIPEdge[startToEnd] THEN IF NOT endToStart.visited THEN IF RegionBoundaryEdge[end, start, isA] THEN { IF verbosity#NIL THEN verbosity.out.PutF["\nSearchInternalPolygons finds boundary edge [%g, %g]\n", IO.int[end.index], IO.int[start.index]]; outHoles _ CONS[ RegionBuilder[end, start, TRUE, vertexVisitedValue, isA, verbosity], outHoles] } ELSE outHoles _ SearchInternalPolygons[end, start, vertexVisitedValue, isA, outHoles]; WHILE end # firstStart DO [start, end] _ StepVertex[start, end, polygonStep]; [startToEnd, endToStart] _ EG.FindAdjacency[start, end]; IF NOT GetEdgeIPEdge[startToEnd] THEN IF NOT endToStart.visited THEN IF RegionBoundaryEdge[end, start, isA] THEN { IF verbosity#NIL THEN verbosity.out.PutF["\nSearchInternalPolygons finds boundary edge [%g, %g]\n", IO.int[end.index], IO.int[start.index]]; outHoles _ CONS[ RegionBuilder[end, start, TRUE, vertexVisitedValue, isA, verbosity], outHoles]; } ELSE outHoles _ SearchInternalPolygons[end, start, vertexVisitedValue, isA, outHoles]; ENDLOOP; RETURN[outHoles]; }; polygonOutline: Imager.Trajectory _ NIL; vec: Imager.VEC; clientData: REF; startToEnd, endToStart: Adjacency; firstStart: Vertex _ outlineStart; tempVertex: Vertex; holes: RegionList; firstTrajPoint: EG.Point; IF verbosity#NIL THEN verbosity.out.PutF["\nRegionBuilder entered with region boundary edge [%g, %g]\n", IO.int[outlineStart.index], IO.int[outlineEnd.index]]; <> <<>> [ startToEnd, endToStart ] _ EG.FindAdjacency[outlineStart, outlineEnd]; SetEdgeIPEdge[startToEnd, TRUE]; startToEnd.visited _ TRUE; IF setOutlineVerticesVisited THEN outlineEnd.visited _ vertexVisitedValue; tempVertex _ NextRegionBoundaryEdge[outlineStart, outlineEnd, isA]; IF EG.PointLineTest[outlineStart.coordinates, tempVertex.coordinates, outlineEnd.coordinates] # ONLINE THEN { -- don't output this if collinear with prev and next firstTrajPoint _ outlineEnd.coordinates; vec _ EG.ImagerVecFromPoint[firstTrajPoint]; polygonOutline _ ImagerPath.MoveTo[vec]; }; WHILE outlineEnd # firstStart DO outlineStart _ outlineEnd; outlineEnd _ tempVertex; [ startToEnd, endToStart ] _ EG.FindAdjacency[outlineStart, outlineEnd]; SetEdgeIPEdge[startToEnd, TRUE]; startToEnd.visited _ TRUE; IF setOutlineVerticesVisited THEN outlineEnd.visited _ vertexVisitedValue; tempVertex _ NextRegionBoundaryEdge[outlineStart, outlineEnd, isA]; IF EG.PointLineTest[outlineStart.coordinates, tempVertex.coordinates, outlineEnd.coordinates] # ONLINE THEN { IF polygonOutline # NIL THEN { -- don't output this if collinear with prev and next vec _ EG.ImagerVecFromPoint[outlineEnd.coordinates]; polygonOutline _ ImagerPath.LineTo[polygonOutline, vec]; } ELSE { firstTrajPoint _ outlineEnd.coordinates; vec _ EG.ImagerVecFromPoint[firstTrajPoint]; polygonOutline _ ImagerPath.MoveTo[vec]; }; }; ENDLOOP; <> outlineStart _ outlineEnd; outlineEnd _ tempVertex; vec _ EG.ImagerVecFromPoint[firstTrajPoint]; polygonOutline _ ImagerPath.LineTo[polygonOutline, vec]; -- close trajectory <> clientData _ GetEdgeClientData[startToEnd]; <> holes _ SearchInternalPolygons[outlineStart, outlineEnd, vertexVisitedValue, isA, NIL]; region _ NEW[RegionRec _ [outline: polygonOutline, clientData: clientData, holes: holes] ]; }; <<>> <<**************** Input and Output ****************>> <<>> ropeFromEdgeData: EG.RopeFromEdgeData ~ { cEGEdgeData: CEGEdgeData _ NARROW[edgeData]; IF cEGEdgeData = NIL THEN RETURN["NIL"]; out _ Rope.Cat[Convert.RopeFromBool[cEGEdgeData.exteriorEdge], ",", Convert.RopeFromBool[cEGEdgeData.intersectionPolygonEdge], "," ]; out _ Rope.Concat[out, clientProc1[cEGEdgeData.clientData] ]; }; DumpGraph: PUBLIC PROC [v: ConvexEuclideanGraph, ropeFromClientData: RopeFromClientData, filename: Rope.ROPE] ~ { EG.DumpGraph[v, ropeFromEdgeData, filename, ropeFromClientData]; }; <<>> edgeDataFromRope: EG.EdgeDataFromRope ~ { dataStream: IO.STREAM _ IO.RIS[in]; char: CHAR; exteriorEdge, intersectionPolygonEdge: BOOLEAN; clientData: REF; DataFromRopeFail: PUBLIC ERROR [subclass: ATOM _ $Unspecified] = CODE; []_ dataStream.SkipWhitespace[]; char _ dataStream.PeekChar[]; IF char = 'N THEN { [] _ dataStream.GetChar[]; -- toss N IF dataStream.GetChar[] # 'I THEN DataFromRopeFail[$IExpected]; IF dataStream.GetChar[] # 'L THEN DataFromRopeFail[$LExpected]; RETURN[NIL] }; IF char # 'T AND char # 'F THEN DataFromRopeFail[$TorFExpected]; exteriorEdge _ IO.GetBool[dataStream]; IF dataStream.GetChar[] # ', THEN DataFromRopeFail[$commaExpected]; char _ dataStream.PeekChar[]; IF char # 'T AND char # 'F THEN DataFromRopeFail[$TorFExpected]; intersectionPolygonEdge _ IO.GetBool[dataStream]; IF dataStream.GetChar[] # ', THEN DataFromRopeFail[$commaExpected]; char _ dataStream.PeekChar[]; IF char = 'N THEN { [] _ dataStream.GetChar[]; -- toss N IF dataStream.GetChar[] # 'I THEN DataFromRopeFail[$IExpected]; IF dataStream.GetChar[] # 'L THEN DataFromRopeFail[$LExpected]; clientData _ NIL; } ELSE { index: INT _ IO.GetIndex[dataStream]; rope: Rope.ROPE _ Rope.Substr[in, index]; clientData _ clientProc1[rope]; }; RETURN[NEW[CEGEdgeDataRec _ [exteriorEdge: exteriorEdge, intersectionPolygonEdge: intersectionPolygonEdge, clientData: clientData] ] ]; }; ReadIOGraphFromFile: PUBLIC PROC [filename: Rope.ROPE, clientDataFromRope: ClientDataFromRope, MessageStream: IO.STREAM] RETURNS [iOGraph: EG.IOGraph] ~ { RETURN[EG.ReadIOGraphFromFile[filename, edgeDataFromRope, MessageStream, clientDataFromRope] ]; }; GraphFromIOGraph: PUBLIC PROC [iOGraph: EG.IOGraph] RETURNS [v: ConvexEuclideanGraph, numberVertices: CARDINAL] ~ { <> vertexList, lastCell: VertexList; scratchVertexList: VertexList; scratchIOGraph: EG.IOGraph; vertex: Vertex; adjacentVertex: Vertex; aList, aListLast: AdjacencyList; adjacency : Adjacency; ioAList: EG.IOAdjacencyList; iOAdjacency: EG.IOAdjacency; <> vertex _ NEW[EG.VertexRec _ [coordinates: iOGraph.first.coordinates, index: iOGraph.first.index, adjacentVertices: NIL, data: NIL, visited: FALSE] ]; lastCell _ vertexList _ LIST[vertex]; numberVertices _ 1; scratchIOGraph _ iOGraph.rest; WHILE scratchIOGraph # NIL DO vertex _ NEW[EG.VertexRec _ [coordinates: scratchIOGraph.first.coordinates, index: scratchIOGraph.first.index, adjacentVertices: NIL, data: NIL, visited: FALSE] ]; lastCell.rest _ LIST[vertex]; lastCell _ lastCell.rest; numberVertices _ numberVertices + 1; scratchIOGraph _ scratchIOGraph.rest; ENDLOOP; scratchVertexList _ vertexList; -- Need to keep vertexList intact for searching <> WHILE scratchVertexList # NIL DO vertex _ scratchVertexList.first; ioAList _ iOGraph.first.adjacentVertices; aList _ NIL; -- initialize WHILE ioAList # NIL DO -- assumes adjacent vertices occur in reverse clockwise order; this loop will restore correct order. iOAdjacency _ ioAList.first; adjacentVertex _ EG.SearchVertexList[vertexList, iOAdjacency.vertex ]; -- these calls assume call by value, i.e. that vertexList always points to the head of the list adjacency _ NEW[EG.AdjacencyRec _ [vertex: adjacentVertex, data: iOAdjacency.data, visited: FALSE] ]; IF GetEdgeExterior[adjacency] THEN v _ vertex; -- identify vertex on outline of figure aList _ CONS[adjacency, aList]; -- adjacencies in ioAList are in backwards (counterclockwise) order; using CONS here puts them back in clockwise order. IF aList.rest = NIL THEN aListLast _ aList; -- save pointer for setting circularity ioAList _ ioAList.rest; ENDLOOP; aListLast.rest _ aList; -- make list circular vertex.adjacentVertices _ aList; -- attach to current vertex scratchVertexList _ scratchVertexList.rest; iOGraph _ iOGraph.rest; -- advance scratchVertexList and iOGraph in lock step ENDLOOP; RETURN[ v, numberVertices ]; }; GraphFromFile: PUBLIC PROC [filename: Rope.ROPE, clientDataFromRope: ClientDataFromRope, MessageStream: IO.STREAM] RETURNS [v: ConvexEuclideanGraph, numberVertices: CARDINAL] ~ { [v, numberVertices] _ GraphFromIOGraph[ReadIOGraphFromFile[filename, clientDataFromRope, MessageStream] ]; }; END.