ConvexEuclideanGraphs.mesa
Last Edited by: Arnon, February 26, 1985 2:21:53 pm PST
DIRECTORY
Imager,
IO,
Rope,
RatNums,
EuclideanGraphs;
ConvexEuclideanGraphs:
CEDAR
DEFINITIONS
=
BEGIN
OPEN
RN: RatNums,
EG: EuclideanGraphs;
Routines for manipulation of Convex EuclideanGraphs, i.e. EuclideanGraphs which consists of a convex polygon (the "outline (polygon)") decomposed into convex polygons (the "internal polygons").
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;
Included are routines for manipulation of convex polygons represented as (Convex) EuclideanGraphs.
It is assumed that edge data in the underlying EG.EuclideanGraph is of type CEGEdgeData. In particular, any creator of a CEG is assumed to allocate, for each edge, a (non-NIL) CEGEdgeData for the edge to point to.
There is no manipulation of vertex data. It is assumed that client data for the area outside the outline of a Convex EuclideanGraphs is NIL.
Convex EuclideanGraphs edge data consists of two parts:
(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
];
Procedures for merging Convex EuclideanGraphs are left to the client, since although the geometrical semantics of such a merge is client-independent, the desired manipulation of client data probably varies from client to client. This interface does attempt to provide useful geometrical primitives from which merge operators can be constructed.
Some reasons why the outline of a Convex EG.EuclideanGraph is useful:
can do point location with respect to wedges of the current outline,
can terminate depth first searches of the internal polygons of the current figure.
Verbosity: TYPE = REF VerbosityRec;
VerbosityRec:
TYPE =
RECORD[
in, out: IO.STREAM
];
************** Hull Computation **************
ConvexHull:
PROC [L: PointList]
RETURNS [Hull: PointList];
Convex Hull of up to 30 points.
Graham's algorithm is used (Info. Proc. Letters, I, 1972, 132-133). Modification: there is no need to do his Step 4, i.e. to check for points with equal polar coordinates. If there are exactly two such points, they will be removed in the course of step 5. Not clear what may happen if there are three or more such points.
firstVertex is thought of as being on the polygonal outline of a figure. The new vertex [x,y] is added so as to come after the vertex which precedes firstVertex (call it vhandlelast), and before firstVertex, in the counterclockwise ordering of vertices. firstVertex is returned, so that subsequently added vertices will always be inserted just before firstVertex.
************** Graph Structure **************
ThreeOrMoreVertices:
PROC [w:
EG.EuclideanGraph]
RETURNS [
BOOL];
Suffices to test whether an arbitrary vertex is adjacent to at least two distinct vertices.
AddEdge:
PROC [root, adjacentVertex: Vertex, exterior:
BOOL ←
FALSE, IPEdge:
BOOL ←
FALSE, clientData:
REF ←
NIL, visitedValue:
BOOL ←
FALSE];
Join vertices with two directed edges with specified data. The possible prior existence of geometrically identical edges between the two vertices is the client's business.
InsertVertexInEdges:
PROC [v, w: Vertex, p: Point, vertexData:
REF ←
NIL]
RETURNS [newVertex: Vertex];
We need a version in ConvexEuclideanGraphs in order to create new CEGDataRec's for each new edge (i.e. using the ConvexEuclideanGraph version of AddEdge).
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];
w is a vertex on the outline of a ConvexEuclideanGraph. By checking the exteriorEdge fields of the adjacencies of w, we find the vertex z which precedes w in the counterclockwise ordering of vertices of a polygon.
This routine is "special" because it requires only one input vertex, instead of the two endpoints of an edge, and it uses exteriorEdge fields, which in general is not a safe thing to do.
PreviousOutlineVertex:
PROC [v, w: Vertex]
RETURNS [z: Vertex];
Assuming that [v, w] is an edge on the outline of some ConvexEuclideanGraph containing at least two vertices, find the vertex z which precedes v in the counterclockwise ordering of vertices of a polygon (counterclockwise order defined with respect to the INTERIOR of the figure on whose outline [v, w] lies).
PreviousPolygonVertex:
PROC [v, w: Vertex]
RETURNS [z:Vertex];
Assuming that w is a vertex on the outline of some ConvexEuclideanGraph containing at least two vertices, find the vertex v which precedes w in the counterclockwise ordering of vertices.
************** 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];
Search the adjacencies of intersectionPolyVertex until an intersection polygon edge is found
IPVertex:
PROC [v: Vertex]
RETURNS [
BOOL];
True iff some edge outgoing from v is an Intersection Polygon Edge.
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];
Clears IPEdge and visited fields of all edges in the Graph pointed to by v.
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];
entryPrior = entryNext = NIL for a previously empty polygon. entryPrior = NIL, entryNext#NIL for a polygon with one previous vertex. clientData is the interior clientData for the polygon being created. If previously empty polygon, then at exit exitPrior = NIL, exitNext is new vertex. Otherwise, at exit, exitPrior is new vertex and exitNext = entryNext.
PointSectorRelation:
TYPE = {
EQUALCOM,
RIGHTSPOKEINTERIOR,
EQUALRIGHTVERTEX,
LEFTSPOKEINTERIOR,
EQUALLEFTVERTEX,
POLYGONEDGEINTERIOR,
SECTORINTERIOR,
RIGHTRAYINTERIOR,
LEFTRAYINTERIOR,
SUBTENDINTERIOR,
OUTSIDESUBTEND};
PointSectorTest:
PROC [rightvertex, leftvertex, centerOfMass, test: Point]
RETURNS[PointSectorRelation];
Determine if the test point lies in the sector of a polygon determined by leftvertex, rightvertex, centerOfMass A sector is defined as the (interior of the) triangle having as vertices the center of mass of p, the ith vertex of p (rightvertex as you face out from the center of mass) and the i+1st vertex of p (leftvertex).
Note that for a sector of a convex polygon, Angle(leftvertex, centerOfMass, rightvertex) < 180 degrees.
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.
We trace the outer polygon, stepping the inner polygon to follow, until an intersection of the outer with the inner polygon is found, or we determine that there is no intersection (i.e. we've gone all the way around the outer polygon without finding one). As we trace, if checkExternal true, we simultaneously collect information to be able to decide whether the outer polygon is external to or encloses the inner, in case there is no intersection.
If an intersection is found, then innerCommon and outerCommon are distinct vertices of the two polygons whose coordinates are the intersection point, innerStart and outerStart the respective preceding vertices, and innerEnd and outerEnd the respective following vertices. If no intersection is found, all are undefined.
************** 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];
We assume that the vertices are given to us in counterclockwise order (with respect to figure interior) along the outline of the figure.
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.
Note a previous way of finding args for GrowToConvexOutline:
IF lensInExterior THEN {
New determination of arguments for GrowToConvexOutline - search the adjacencies of nextIntersectionVertex until we find a consecutive pair x,y such that [x,nextIntersectionVertex].leftRegionExterior and [nextIntersectionVertex,y].leftRegionExterior. Some kind of searching like this is necessary, because we can no longer necessarily have our hands on the arguments for GrowToConvexOutline at the end of a lens.
[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.
Uses Depth First Search. The graph must have at least three vertices.
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;
This is for edge client data. Any non-blank character ok.
IF data=NIL THEN RETURN["NIL"] ELSE RETURN[ ... -- all RopeFromData's should do this
ClientDataFromRope:
TYPE =
EG.RefFromRopeProc;
This is for edge client data. Remember to catch "NIL"
DumpGraph:
PROC [v: ConvexEuclideanGraph, ropeFromClientData: RopeFromClientData, filename: Rope.
ROPE];
Dump a EuclideanGraph to a file. Does Depth First Search.
GraphFromFile:
PROC [filename: Rope.
ROPE, clientDataFromRope: ClientDataFromRope, MessageStream:
IO.
STREAM]
RETURNS [v: ConvexEuclideanGraph, numberVertices:
CARDINAL];