EuclideanGraphs.mesa
Last Edited by: Arnon, February 26, 1985 2:21:53 pm PST
DIRECTORY
Rope,
IO,
RatNums USING [RatNum],
Imager;
EuclideanGraphs:
CEDAR
DEFINITIONS
= BEGIN
OPEN
RN: RatNums;
General notes on EuclideanGraphs:
(1) A EuclideanGraph is assumed to be connected. Hence a client who wishes to work with potentially unconnected graphs must maintain a EuclideanGraph for each component.
(2) Regions are not stored explicitly in the graph, but are implicitly determined by it (2/86 - unresolved whether a unique set of regions is determined by a graph; e.g. this may be equivalent to the (fallacious?) notion that a graph uniquely determines a subdivision).
(3) (Client) data stored with (directed) edges can be thought of as being associated with the edge itself, or with the region (in some subdivision for which this is the graph) to the left of the edge.
(4) This package does no manipulation of client data. It is up to the client to fill in the data fields of new vertices and edges.
(5) Procedures for merging Euclidean graphs 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.
(6) It is the client's responsibility to maintain vertexIndex. This interface will simply increment it by one each time a new vertex is allocated.
EuclideanGraph: TYPE = Vertex; -- since EuclideanGraphs assumed connected, a pointer to any vertex is sufficient entree to the graph.
Vertex: TYPE = REF VertexRec;
VertexRec:
TYPE =
RECORD[
coordinates: Point,
index: INTEGER, -- negative index intended for temp vertices, zero index for point at infinity
adjacentVertices: AdjacencyList, -- circular list of adjacent vertices in clockwise order
data: REF ANY ← NIL,
visited: BOOL ← FALSE -- for searching
];
VertexList: TYPE = LIST OF Vertex;
Adjacency: TYPE = REF AdjacencyRec;
AdjacencyRec:
TYPE =
RECORD[
vertex: Vertex,
data: REF ANY ← NIL,
visited: BOOLEAN ← FALSE -- for searching
];
AdjacencyList: TYPE = LIST OF Adjacency;
Point: TYPE = RECORD[ x , y : RN.RatNum ];
PointList: TYPE = LIST OF Point;
vertexIndex: CARDINAL; -- count of vertices allocated
**************** Point and Edge Manipulation ****************
MakePointFromRatNums:
PROC[x1, y1:
RN.RatNum]
RETURNS [p: Point];
Bundle up two RatNums as an point
MakePointFromReals:
PROC[x1, y1:
REAL]
RETURNS [p: Point];
Bundle up two Reals as a (rational) point
ImagerVecFromPoint:
PROC[p: Point]
RETURNS [q: Imager.
VEC];
PointEqual:
PROC[ p, q: Point ]
RETURNS[
BOOLEAN];
Test whether points p and q are the same.
VerticalEdge:
PROC[ p, q: Point ]
RETURNS[
BOOLEAN];
Test whether the edge [p,q] is vertical. No check is made for coincidence of p and q.
DistanceSquare:
PROC[ p, q: Point ]
RETURNS[d:
RN.RatNum];
Compute the square of the distance between two points.
PointLineRelation:
TYPE = {
ONLINE,
LEFTOFLINE,
RIGHTOFLINE};
PointLineTest:
PROC [start, end, test: Point]
RETURNS[PointLineRelation];
Determine the relation of the point test to the line [start, end]. The line may be trivial, i.e. start = end; if so, and if test # start = end, then LEFTOFLINE returned.
PointDirectedEdgeRelation:
TYPE = {
BEFORESTART,
EQUALSTART,
BETWEENSTARTEND,
EQUALEND,
AFTEREND,
LEFTOFEDGE,
RIGHTOFEDGE};
PointDirectedEdgeTest:
PROC [start, end, test: Point]
RETURNS[PointDirectedEdgeRelation];
IntersectLines:
PROC [start1, end1, start2, end2: Point]
RETURNS [intersection: Point];
The edges [start1, end1] and [start2, end2] define lines with exactly one intersection.
BiasedEdgeCompareStatus:
TYPE = {
OuterEndEqInnerStart, OuterEndInInner, OuterEndEqInnerEnd,
InnerStartInOuter, ProperIntersection, InnerEndInOuter,
Disjoint};
BiasedEdgeCompare:
PROC [outerStart, outerEnd, innerStart, innerEnd: Vertex]
RETURNS [outcome: BiasedEdgeCompareStatus];
Compare the half-open edge (outerStart, outerEnd] with the edge [innerStart, innerEnd]. It is assumed that outerStart lies to the outside (right) of [innerStart, innerEnd]. Thus, in particular, the edges cannot ovelap. Information about the location of the point of contact between them, if any, is returned.
**************** Structure Manipulation ****************
FindAdjacency:
PROC[v, w: Vertex]
RETURNS [vTow, wTov: Adjacency];
CountAdjacencies:
PROC[v: Vertex]
RETURNS [number:
CARDINAL];
Overlapping adjacencies counted with multiplicities, i.e. a pair of overlapping adjacencies are counted as two adjacencies
AdjacentVertices:
PROC[v: Vertex]
RETURNS [vertices:
LIST
OF
Vertex];
Given in clockwise order.
Adjacent:
PROC[v, w: Vertex]
RETURNS [
BOOL];
Test if two vertices are adjacent.
SetFigureVisitedValues:
PROC[v:
Vertex, visitedValue:
BOOLEAN];
FindVertexForPoint:
PROC [v: Vertex, test: Point]
RETURNS [w: Vertex];
Find vertex closest to test point
**************** New Basic Ops ****************
TestEdgeOverlap:
PROC [root, testEnd: Vertex]
RETURNS [overlap:
BOOL, overlappedVertex: Vertex ←
NIL];
Assuming testStart.coods = v.coods, check whether an edge of the same slope as [testStart, testEnd] occurs among the adjacencies of v (i.e. check for an overlapping edge). If so, then overlap = TRUE and overlappedVertex is the overlapped adjacent vertex of v. If not, then overlap = FALSE and overlappedVertex ← NIL. It is assumed that testEnd.coods # testStart.coods, i.e. [[testStart, testEnd] is a nontrivial edge.
CreateVertex:
PROC [point: Point, vertexData:
REF ←
NIL, visitedValue:
BOOL ←
FALSE]
RETURNS [newVertex: Vertex];
No adjacencies.
CreateEdge:
PROC [endVertex: Vertex, edgeData:
REF ←
NIL, visitedValue:
BOOL ←
FALSE]
RETURNS [newAdjacency: Adjacency];
AddEdge:
PROC [root, adjacentVertex: Vertex, data:
REF ←
NIL, visitedValue:
BOOL ←
FALSE];
Inserts a new edge [root, adjacentVertex], with specified data and visitedValue, into the adjacencies of root.
DeleteEdge:
PROC [root, adjacentVertex: Vertex];
InsertVertexInEdges:
PROC [v, w: Vertex, p: Point, vertexData:
REF ←
NIL]
RETURNS [newVertex: Vertex];
Split (two directed) edge(s) by insertion of new vertex. It is assumed that p is in the interior of the segment joining v and w. (If debug on, check this). The visitedValue of the new vertex is inherited from v.
SplitVertex:
PROC [v, distinguishedAdjacentVertex: Vertex]
RETURNS [newVertex: Vertex];
Split v into vertices v and (a temp vertex) newVertex, such that v remains involved only in the adjacencies [v, distinguishedAdjacentVertex] and [distinguishedAdjacentVertex, v], while newVertex participates in all other adjacencies formerly participated in by v.
MergeVertices:
PROC [u, v: Vertex];
Adjacencies sorted into clockwise order, edges of same slope occur in unspecified order. Vertex u takes priority, i.e. its index and other fields retained; vertex v disappears.
DeleteVertex:
PROC [v: Vertex];
Delete vertex, and all edges incident upon it.
SeparateVertices:
PROC [v, w: Vertex];
Delete the two directed edges joining a particular pair of vertices. Error if either vertex is left with only one adjacency. Error if there are no edges joining the vertices (one directed edge between them is ok).
SetEdgeData:
PROC [vTow: Adjacency, newData:
REF];
BracketingAdjacenciesRelation:
TYPE = {Interior, Overlaps, EqualRoot};
BracketingAdjacencies:
PROC[root: Vertex, test: Point]
RETURNS [status: BracketingAdjacenciesRelation, priorPosition, followingPosition: AdjacencyList];
Search for the pair of adjacencies of root which bracket test. If root.coordinates = test, then status = EqualRoot and priorPosition = followingPosition = NIL. If for successive (in the clockwise ordering) adjacencies x, y of root, test is interior to Angle(x, root, y) or exterior if root has only one adjacency and so x = y), then status = Interior, priorPosition.first.vertex = x, and followingPosition.first.vertex = y. If for some adjacency x of root, (the ray from root to) x overlaps (the ray from root to) test, then status = Overlaps and priorPosition.first.vertex = x, and followingPosition.first.vertex = y, where y is the vertex that follows x (y may also overlap x).
**************** Input and Output ****************
RopeFromRefProc: TYPE ~ PROC[ref: REF] RETURNS [Rope.ROPE];
RefFromRopeProc: TYPE ~ PROC[rope: Rope.ROPE] RETURNS [REF];
RopeFromEdgeData:
TYPE =
PROC [edgeData:
REF, clientProc1, clientProc2: RopeFromRefProc ←
NIL]
RETURNS [out: Rope.
ROPE];
Any non-blank character can occur in the output rope. clientProc1, clientProc2 are optional proc's to be used in writing out.
IF data=NIL THEN RETURN["NIL"] ELSE RETURN[ ... -- all RopeFromData's should do this
EdgeDataFromRope:
TYPE =
PROC [in: Rope.
ROPE, clientProc1, clientProc2: RefFromRopeProc ←
NIL]
RETURNS [edgeData:
REF];
clientProc1, clientProc2 are optional proc's to be used in reading in.
Remember to catch "NIL"
RopeFromVertexData:
TYPE =
PROC [vertexData:
REF, clientProc1, clientProc2: RopeFromRefProc ←
NIL]
RETURNS [Rope.
ROPE];
Any non-blank character can occur in the output rope. clientProc1, clientProc2 are optional proc's to be used in writing out.
IF data=NIL THEN RETURN["NIL"] ELSE RETURN[ ... -- all RopeFromData's should do this
VertexDataFromRope:
TYPE =
PROC [in: Rope.
ROPE, clientProc1, clientProc2: RefFromRopeProc ←
NIL]
RETURNS [vertexData
: REF];
clientProc1, clientProc2 are optional proc's to be used in reading in.
Remember to catch "NIL"
DumpGraph:
PROC [v: EuclideanGraph, ropeFromEdgeData: RopeFromEdgeData, filename: Rope.
ROPE, clientProc1, clientProc2: RopeFromRefProc ←
NIL];
Dump a EuclideanGraph to a file. Does Depth First Search.
IOGraph: TYPE = LIST OF IOVertex;
IOVertex: TYPE = REF IOVertexRec;
IOVertexRec:
TYPE =
RECORD[
coordinates: Point,
index: INTEGER,
adjacentVertices: IOAdjacencyList, -- circular list, vertices in clockwise order
data: REF ANY ← NIL -- currently no vertex data handled (this is a shortcoming)
visited: BOOL ← FALSE -- for searching
];
IOAdjacency: TYPE = REF IOAdjacencyRec;
IOAdjacencyRec:
TYPE =
RECORD[
vertex: INTEGER, -- use of INT here rather than Vertex distinguishes IO* structures
data: REF ANY ← NIL,
visited: BOOLEAN ← FALSE -- for searching
];
IOAdjacencyList:
TYPE =
LIST
OF IOAdjacency;
ReadIOGraphFromFile:
PROC [filename: Rope.
ROPE, edgeDataFromRope: EdgeDataFromRope, MessageStream:
IO.
STREAM, clientProc1, clientProc2: RefFromRopeProc ←
NIL]
RETURNS [iOGraph: IOGraph];
VertexVerifyIOGraph:
PROC [filename: Rope.
ROPE, MessageStream:
IO.
STREAM]
RETURNS [ maxVertexIndex:
CARDINAL];
Check whether all vertices within the range of [Minimum vertex index read, Maximum vertex index read] occur, and check that each vertex referred to in an adjacency is present as a vertex
SearchVertexList:
PROC [list: VertexList, key:
INT]
RETURNS [Vertex];
Search vertexList for the element whose index is key;