<> <> <<>> DIRECTORY Imager, IO, Rope, RatNums, EuclideanGraphs; ConvexEuclideanGraphs: CEDAR DEFINITIONS = BEGIN OPEN RN: RatNums, EG: EuclideanGraphs; <> <<>> ConvexEuclideanGraph: TYPE = EG.EuclideanGraph; Vertex: TYPE = EG.Vertex; VertexList: TYPE = EG.VertexList; Adjacency: TYPE = EG.Adjacency; AdjacencyList: TYPE = EG.AdjacencyList; Point: TYPE = EG.Point; PointList: TYPE = EG.PointList; <<>> <> <<>> <> <> <<>> <> <<(a) geometrical information for maintainance of the graph outline (the exteriorEdge field), and>> <<(b) state information, consisting of the state itself (leftData field), and info for state updating (intersectionPolygonEdge field). States here are colors.>> <<>> CEGEdgeData: TYPE = REF CEGEdgeDataRec; -- This definition repeated in ConvexEuclideanGraphs.mesa CEGEdgeDataRec: TYPE = RECORD[ exteriorEdge: BOOLEAN, -- true if region to the left of edge to this point is external to the current outline, i.e. if the region on whose boundary this edge lies is the exterior of the current outline. intersectionPolygonEdge: BOOLEAN _ FALSE, -- mark an edge that lies along the intersection polygon formed by the input polygon and the outline of the current figure clientData: REF ]; <<>> <> <<>> <> <> <> <<>> Verbosity: TYPE = REF VerbosityRec; VerbosityRec: TYPE = RECORD[ in, out: IO.STREAM ]; <<>> <<************** Hull Computation **************>> ConvexHull: PROC [L: PointList] RETURNS [Hull: PointList]; <> <> <> <<>> <<>> <<************** Graph Structure **************>> <<>> ThreeOrMoreVertices: PROC [w: EG.EuclideanGraph] RETURNS [BOOL]; <> AddEdge: PROC [root, adjacentVertex: Vertex, exterior: BOOL _ FALSE, IPEdge: BOOL _ FALSE, clientData: REF _ NIL, visitedValue: BOOL _ FALSE]; <> InsertVertexInEdges: PROC [v, w: Vertex, p: Point, vertexData: REF _ NIL] RETURNS [newVertex: Vertex]; <> JoinVertices: PROC [start, end: Vertex, startToEndData, endToStartData: REF _ NIL, startToEndIPEdge, endToStartIPEdge: BOOL _ FALSE, startToEndExterior, endToStartExterior: BOOL _ FALSE, startToEndVisited, endToStartVisited: BOOL _ FALSE]; <<>> <<************** Graph Traversal **************>> <<>> StepVertex: PROC[v1, w1: Vertex, outline: BOOL] RETURNS [ v2, w2: Vertex]; NextVertex: PROC[v, w: Vertex, outline: BOOL] RETURNS [ z: Vertex]; PreviousVertex: PROC[v, w: Vertex, outline: BOOL] RETURNS [z: Vertex]; NextOutlineVertex: PROC[v, w: Vertex] RETURNS [ z: Vertex]; NextPolygonVertex: PROC[ v, w: Vertex] RETURNS [ Vertex]; SpecialPreviousOutlineVertex: PROC [w: Vertex] RETURNS [v:Vertex]; <> <> PreviousOutlineVertex: PROC [v, w: Vertex] RETURNS [z: Vertex]; <> <<>> PreviousPolygonVertex: PROC [v, w: Vertex] RETURNS [z:Vertex]; <> <<>> <<>> <<************** Edge Fields **************>> GetEdgeClientData: PROC [startToEnd: Adjacency] RETURNS [data: REF ANY]; <<[start, End] is an edge. Obtain its client data.>> <<>> SetEdgeClientData: PROC [startToEnd: Adjacency, data: REF ANY]; <<[start, End] is an edge. Set its client data.>> <<>> SetPolygonClientData: PROC [start, end: Vertex, data: REF, setVisited: BOOL _ FALSE]; <<[start, end] is a (counterclockwise) directed edge of an internal polygon. Its client data is set. If setVisited, then the visited fields of its edges are set TRUE.>> <<>> GetEdgeExterior: PROC [startToEnd: Adjacency] RETURNS [value: BOOL]; <<[start, End] is an edge. Obtain the value of its exterior field.>> <<>> SetEdgeExterior: PROC [startToEnd: Adjacency, value: BOOL]; <<[start, End] is an edge. Set the value of its exterior field.>> <<>> GetEdgeIPEdge: PROC [startToEnd: Adjacency] RETURNS [value: BOOL]; <<[start, End] is an edge. Obtain the value of its intersectionPolygonEdge field.>> <<>> SetEdgeIPEdge: PROC [startToEnd: Adjacency, value: BOOL]; <<[start, End] is an edge. The value of its intersectionPolygonEdge field is set.>> <<>> SetPolygonIPEdges: PROC [start, end: Vertex, value: BOOL]; <<[start, end] is a (counterclockwise) directed edge of an internal polygon. The value of the intersectionPolygonEdge fields is set.>> <<>> ClearGraphIPEdges: PROC [v, w: Vertex]; <<[intersectionPolyStart, intersectionPolyEnd] 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.>> <<>> IPVertexToEdge: PROC [intersectionPolyVertex: Vertex] RETURNS [intersectionPolyNext: Vertex]; <> IPVertex: PROC [v: Vertex] RETURNS [BOOL]; <> ClearEdgeVisitedFields: 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 ConvexEuclideanGraph.>> ClearGraphEdgeFields: PROC [v: Vertex]; <> SetOutwardOutlineEdgeFields: PROC [start, end: Vertex, exteriorEdgeValue, intersectionPolygonEdgeValue: BOOL, clientDataValue: REF _ NIL]; <<[start, end] is a (counterclockwise) directed edge of an outline. The fields of all "outward-facing" edges of the outline are set to the specified values.>> <<>> SetPolygonFields: PROC [start, end: Vertex, exteriorEdgeValue, intersectionPolygonEdgeValue: BOOL _ FALSE, clientDataValue: REF _ NIL]; <<[start, end] is a (counterclockwise) directed edge of an (internal) polygon. The fields of all edges of the polygon are set to the specified values.>> <<>> <<>> <<************** Convex (internal) polygon operations **************>> CenterOfMass: PROC[ v, w : Vertex, outline: BOOL] RETURNS [Point]; <<[v,w] is a counterclockwise oriented edge on the polygon>> <<>> CountPolygonVertices: PROC [start, end: Vertex, outline: BOOL _ FALSE] RETURNS [numVertices: CARDINAL]; <<[start, end] is an edge of a polygon with at least two vertices.>> AddVertexToPolygon: PROC [entryPrior, entryNext: Vertex, coordinates: Point, clientData: REF _ NIL] RETURNS [exitPrior, exitNext: Vertex]; <> PointSectorRelation: TYPE = {EQUALCOM, RIGHTSPOKEINTERIOR, EQUALRIGHTVERTEX, LEFTSPOKEINTERIOR, EQUALLEFTVERTEX, POLYGONEDGEINTERIOR, SECTORINTERIOR, RIGHTRAYINTERIOR, LEFTRAYINTERIOR, SUBTENDINTERIOR, OUTSIDESUBTEND}; PointSectorTest: PROC [rightvertex, leftvertex, centerOfMass, test: Point] RETURNS[PointSectorRelation]; <> <> <<>> FindSubtendForPoint: 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].>> VertexExternalToPolygon: PROC [firstCOM: Point, firstStart, firstEnd, secondStart, secondEnd: Vertex] RETURNS [found: BOOL, newFirstStart, newFirstEnd, newSecondStart, newSecondEnd: Vertex _ NIL]; <<[firstStart, firstEnd] is a (counterclockwise) directed edge of an internal polygon of a Convex EG.EuclideanGraph, as is [secondStart, secondEnd]. firstCOM is center of mass of first. If some vertex of second lies external to first, then found _ TRUE, and [newFirstStart, newFirstEnd] is a (counterclockwise) directed edge of first in whose (closed) wedge the exterior point newSecondStart lies; newSecondEnd is the vertex of second which follows newSecondStart. If no points of second are exterior to first, then found = FALSE, and the other output parameters are undefined.>> <<>> ConvexPolygon: 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.>> ConvexPolygonCompareStatus: TYPE = { Encloses, External, Intersection }; << >> ConvexPolygonCompare: 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]; <<[innerStart, innerEnd] is a counterclockwise oriented edge on the "inner" polygon, whose center of mass is innerCOM. innerOutline specifies whether inner polygon is to be outline or polygon stepped. [outerStart, outerEnd] is a counterclockwise oriented edge on the "outer" polygon, such that outerStart lies in the subtend of the wedge of the sector of the inner polygon defined by [innerStart, innerEnd], but not in (the closure of) the wedge itself. Outer polygon is always polygon stepped.>> <> <> <<>> <<************** Graph Searching **************>> <<>> FindInternalPolygonForPoint: PROC [v, w: Vertex, test: Point] RETURNS [pointSectorStatus: PointSectorRelation, y, z: Vertex]; <<[v, w] is a (counterclockwise) directed edge of an internal polygon of a Convex EG.EuclideanGraph within whose outline test is known to lie. Either [y, z] is a (counterclockwise) directed edge of the unique internal polygon in whose interior test lies, such that test lies in the closed wedge of this polygon defined by [y, z], or [y, z] is a (counterclockwise) directed edge of an internal polygon such that test lies in the closed edge [y, z].>> <<>> SearchInternalPolygonsForPoint: PROC [v, w: Vertex, test: Point] RETURNS [found: BOOL, y, z: Vertex]; <<[v, w] is a (counterclockwise) directed edge of an internal polygon of a Convex EG.EuclideanGraph. If test is found within the closure of the current structure (i.e. in its interior or on its outline), then found = TRUE, and either [y, z] is a (counterclockwise) directed edge of the unique internal polygon in whose interior test lies, such that test lies in the closed wedge of this polygon defined by [y, z], or [y, z] is a (counterclockwise) directed edge of an internal polygon such that test lies in the closed edge [y, z]. If test is not found within the closure of the current structure, then found = FALSE, y = v, and z = w.>> <<>> <<************** Graph Outline **************>> ConvexPolygonOnOutline: PROC[ prew2, w2, prew1, w1: Vertex] RETURNS [BOOL]; <> <<>> <<>> GrowToConvexOutline: PROC[w2, v, w1: Vertex, verbosity: Verbosity _ NIL] RETURNS [v3, w3: Vertex]; ConvexifyOutline: PROC [outlineStart, outlineEnd: Vertex, verbosity: Verbosity _ NIL] RETURNS [newOutlineStart, newOutlineEnd: Vertex]; <<[outlineStart, outlineEnd] is an edge of a closed EG.EuclideanGraph, i.e. one which has an outline. An outline may loop back and touch itself (at a single vertex), but may not cross itself. This edge is assumed to be counterclockwise-oriented with respect to the interior of the outline. We walk around the outline, calling GrowToConvexOutline to add new edges so that at the end we have a Convex EG.EuclideanGraph, i.e. a convex outline and convex internal polygons.>> <> <> <> <<[x, y] _ FindExternalAcuteAngle[nextIntersectionVertex];>> <<[newCombinedStart, newCombinedEnd] _ GrowToConvexOutline[y, nextIntersectionVertex, x];>> <<>> <<>> <<************** Region Extraction **************>> RegionList: TYPE = LIST OF Region; Region: TYPE = REF RegionRec; RegionRec: TYPE = RECORD [ outline: Imager.Trajectory, -- should be a convex polygon. clientData: REF, -- of (outline - holes) holes: RegionList _ NIL -- note that holes can themselves contain holes. ]; InternalPolygons: PROC [v, w: Vertex] RETURNS [RegionList]; <<[v, w] is a counterclockwise oriented edge of an internal polygon of a ConvexEuclideanGraph. Extract all the internal polygons, and their respective clientData's, from the graph.>> <> <<>> IsAProc: TYPE = PROC [clientData: REF] RETURNS [BOOL]; -- definition of region boundaries <<>> MaximalRegions: PROC [outlineVertex: Vertex, isA: IsAProc, verbosity: Verbosity _ NIL] RETURNS [outRegionList: RegionList]; <<[v,w] is a counterclockwise oriented edge of an internal polygon of a ConvexEuclideanGraph. >> <<>> RegionBuilder: PROC [outlineStart, outlineEnd: Vertex, setOutlineVerticesVisited: BOOL, vertexVisitedValue: BOOLEAN, isA: IsAProc, verbosity: Verbosity _ NIL] RETURNS [region: Region]; <<>> <<>> <<**************** Input and Output ****************>> <<>> RopeFromClientData: TYPE = EG.RopeFromRefProc; <> <> <<>> ClientDataFromRope: TYPE = EG.RefFromRopeProc; <> <<>> DumpGraph: PROC [v: ConvexEuclideanGraph, ropeFromClientData: RopeFromClientData, filename: Rope.ROPE]; <> <<>> GraphFromFile: PROC [filename: Rope.ROPE, clientDataFromRope: ClientDataFromRope, MessageStream: IO.STREAM] RETURNS [v: ConvexEuclideanGraph, numberVertices: CARDINAL]; <<>> <<>> END. <>