RVHandleUtilsImpl.mesa
Last Edited by: Arnon, June 20, 1985 4:37:28 pm PDT
DIRECTORY
Rope USING [ROPE],
FS USING [StreamOpen],
IO USING [STREAM, Close, PutF, int, rope, PutChar, bool, SkipWhitespace, PeekChar, GetChar, GetInt, GetTokenRope, GetBool, IDProc], -- real, PutFR, card, ViewerIO
Imager USING [VEC, Trajectory],
ImagerPath USING [ MoveTo, LineTo ],
RatNums,
ClientStateInfo,
RVHandleUtils,
RealFns; -- ViewerIO
RVHandleUtilsImpl: CEDAR PROGRAM
IMPORTS FS, IO, ImagerPath, RatNums, ClientStateInfo, RealFns
EXPORTS RVHandleUtils =
BEGIN OPEN CSI: ClientStateInfo, RN: RatNums, RVHandleUtils;
vertexIndex: PUBLIC CARDINAL; -- count of vertices allocated
ConvexPolygonOnOutline: PUBLIC PROC[ prew2, w2, prew1, w1: VertexHandle, outline:BOOL ← TRUE] 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.
x, y, z: VertexHandle;
SELECT PointLineTest[w2.coordinates, prew2.coordinates, w1.coordinates] FROM
RIGHTOFLINE => RETURN[FALSE];
LEFTOFLINE => NULL;
ONLINE => ERROR; -- 9/19/85 unsure whether to allow a 180deg angle
ENDCASE;
SELECT PointLineTest[prew2.coordinates, w1.coordinates, prew1.coordinates] FROM
RIGHTOFLINE => RETURN[FALSE];
LEFTOFLINE => NULL;
ONLINE => ERROR; -- 9/19/85 unsure whether to allow a 180deg angle
ENDCASE;
x ← w1; y ← prew1; z ← PreviousVertex[y, x, outline];
WHILE x # w2 DO
SELECT PointLineTest[x.coordinates, y.coordinates, z.coordinates] FROM
RIGHTOFLINE => RETURN[FALSE];
LEFTOFLINE => NULL;
ONLINE => ERROR; -- 9/19/85 unsure whether to allow a 180deg angle
ONLINE => NULL; -- 11/7/85 180deg angle ok
ENDCASE;
x ← y; y ← z; z ← PreviousVertex[y, x, outline];
ENDLOOP;
RETURN[TRUE];
};
CenterOfMass: PUBLIC PROC[ v, w : VertexHandle, outline: BOOL ] RETURNS [Point] = {
[v,w] is a counterclockwise oriented edge on the polygon
vfirst: VertexHandle ← 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 ] ] ];
};
ConvexPolygon: PUBLIC PROC[ v, w : VertexHandle, outline: BOOL ] RETURNS [BOOL] = {
[v,w] is a counterclockwise oriented edge on the polygon, must have at least 2 (3?) vertices.
z: VertexHandle;
vfirst: VertexHandle ← v;
wfirst: VertexHandle ← w;
z ← NextVertex[v, w, outline];
IF z = v OR z = w THEN RETURN[TRUE];
SELECT PointLineTest[v.coordinates, w.coordinates, z.coordinates] FROM -- check first angle
RIGHTOFLINE => RETURN[FALSE];
LEFTOFLINE => NULL;
ONLINE => ERROR; -- 9/19/85 unsure whether to allow a 180deg angle
ENDCASE;
v ← w; [w, z] ← StepVertex[ w, z, outline ]; -- step past
WHILE v # vfirst DO
SELECT PointLineTest[v.coordinates, w.coordinates, z.coordinates] FROM -- check first angle
RIGHTOFLINE => RETURN[FALSE];
LEFTOFLINE => NULL;
ONLINE => ERROR; -- 9/19/85 unsure whether to allow a 180deg angle
ENDCASE;
v ← w; [w, z] ← StepVertex[ w, z, outline ];
ENDLOOP;
RETURN[TRUE];
};
ConvexHull: PUBLIC 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.
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;
in, out: IO.STREAM; -- viewer stream for debugging verbosity
Compactify: PROC [j: CARDINAL] ~ {
Compactify pointArray to remove the jth element
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"]];
Load into array
n ← 0;
WHILE L # NIL DO
n ← n + 1;
pointArray[n] ← [ L.first.x, L.first.y ];
out.PutF["\n pointArray[%g] = ( %g , %g )", IO.card[n], IO.rope[RN.RatNumToRatRope[pointArray[n].x, FALSE, FALSE]], IO.rope[RN.RatNumToRatRope[pointArray[n].y, FALSE, FALSE]] ];
L ← L.rest;
ENDLOOP;
Step 1 - Find interior point P - search for noncollinear set of three points, compute com of that triangle
I ← 1;
WHILE I <= n-2 DO
IF PointLineTest[pointArray[I], pointArray[I+1], pointArray[I+2]]#ONLINE THEN EXIT;
I ← I+1;
ENDLOOP;
IF 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 ] ];
out.PutF["\n I, interiorP = %g , ( %g , %g )", IO.card[I], IO.rope[RN.RatNumToRatRope[interiorP.x, FALSE, FALSE]], IO.rope[RN.RatNumToRatRope[interiorP.y, FALSE, FALSE]] ];
Step 2 - Translate points by coordinates of interiorP
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;
Step 3 - Bubble sort translated points according to polar angles of vectors from interiorP
- 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;
out.PutF["\n I, J, flip = %g , %g, %g", IO.card[I],IO.card[J], IO.bool[flip] ];
IF flip THEN {
tempPoint ← pointArray[J];
pointArray[J] ← pointArray[J+1];
pointArray[J+1] ← tempPoint;
};
ENDLOOP;
ENDLOOP;
out.PutF["\n New pointArray" ];
FOR I IN [1..n] DO
out.PutF["\n pointArray[%g] = ( %g , %g ), arctan = %g", IO.card[I], IO.rope[RN.RatNumToRatRope[pointArray[I].x, FALSE, FALSE]], IO.rope[RN.RatNumToRatRope[pointArray[I].y, FALSE, FALSE]],
IO.real[RealFns.ArcTan[ RN.RatNumToREAL[pointArray[I].y], RN.RatNumToREAL[pointArray[I].x] ] ] ];
ENDLOOP;
Step 5 - Walk around applying "left of line" test
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 PointEqual[pointArray[MyMOD[I,n]], pointArray[MyMOD[I+1,n] ]] DO
Compactify[MyMOD[I+1,n]]; -- check for and remove duplicate points
ENDLOOP;
WHILE 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;
Return untranslated points of hull.
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;
};
PointEqual: PUBLIC PROC[p, q: Point] RETURNS [BOOLEAN] = {
Test whether points p and q are the same.
RETURN[ RN.RatNumEqual[p.x, q.x] AND RN.RatNumEqual[ p.y, q.y ] ];
};
VerticalEdge: PUBLIC PROC[ p, q: Point ] RETURNS[BOOLEAN] = {
Test whether points p and q are the same.
RETURN[ RN.RatNumEqual[p.x, q.x] ];
};
DistanceSquare: PUBLIC PROC[ p, q: Point ] RETURNS [d: RN.RatNum] = {
Compute square of distance between two points.
deltax, deltay: RN.RatNum;
deltax ← RN.RatNumSubtract[ q.x, p.x];
deltay ← RN.RatNumSubtract[ q.y, p.y];
RETURN[ RN.RatNumAdd[
RN.RatNumMultiply[ deltax, deltax ], RN.RatNumMultiply[ deltay, deltay ]
] ]
};
PointLineTest: PUBLIC PROC [start, end, test: Point] RETURNS[PointLineRelation ← ONLINE ] = {
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.
IF PointEqual[start, end] THEN
IF PointEqual[start, test] THEN RETURN[ ONLINE ] ELSE RETURN[ LEFTOFLINE ]
ELSE {
relation: RN.RatNumRelation ← RN.RatNumCompare[
RN.RatNumMultiply[
RN.RatNumSubtract[ end.x , start.x ],
RN.RatNumSubtract[ test.y , start.y]
],
RN.RatNumMultiply[
RN.RatNumSubtract[ test.x , start.x ],
RN.RatNumSubtract[ end.y , start.y ]
]
];
SELECT relation FROM
ratLess => RETURN[ RIGHTOFLINE ];
ratEqual => RETURN[ ONLINE ];
ratGreater => RETURN[ LEFTOFLINE ];
ENDCASE;
};
};
PointDirectedEdgeTest: PUBLIC PROC [start, end, test: Point] RETURNS[PointDirectedEdgeRelation ← LEFTOFEDGE] = {
*** Perhaps instead of DistanceSquare, can use the test IF ( (ytest - p1.y) * (p2.y - ytest) > 0 ) AND ( (xtest - p1.x) * (p2.x - xtest) > 0 ) THEN between (assuming nonvertical and nonhorizontal points).
pointLineRelation: PointLineRelation;
firstbool, secondbool: BOOL;
pointLineRelation ← PointLineTest[start, end, test];
SELECT pointLineRelation FROM
LEFTOFLINE => RETURN[ LEFTOFEDGE ];
RIGHTOFLINE => RETURN[ RIGHTOFEDGE ];
ONLINE => {
IF PointEqual[start, test] THEN RETURN[ EQUALSTART ];
IF PointEqual[end, test] THEN RETURN[ EQUALEND ];
firstbool ← RN.RatNumGreater[ DistanceSquare[start, end], DistanceSquare[start, test] ];
secondbool ← RN.RatNumGreater[ DistanceSquare[end, start], DistanceSquare[end, test] ];
IF firstbool AND secondbool THEN RETURN[BETWEENSTARTEND];
IF RN.RatNumGreater[ DistanceSquare[test, start], DistanceSquare[test, end] ] THEN RETURN[AFTEREND] ELSE RETURN[BEFORESTART];
};
ENDCASE;
};
PointSectorTest: PUBLIC PROC [rightvertex, leftvertex, centerOfMass, test: Point] RETURNS[PointSectorRelation ← EQUALCOM] = {
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).
pointEdgeRelation: PointDirectedEdgeRelation ← PointDirectedEdgeTest[ centerOfMass, rightvertex, test];
SELECT pointEdgeRelation FROM
BEFORESTART => RETURN[ LEFTOFSUBTEND ];
EQUALSTART => RETURN[ EQUALCOM ];
BETWEENSTARTEND => RETURN[ RIGHTSPOKEINTERIOR ];
EQUALEND => RETURN[ EQUALRIGHTVERTEX ];
AFTEREND => RETURN[ RIGHTRAYINTERIOR ];
RIGHTOFEDGE => RETURN[ RIGHTOFSUBTEND ];
LEFTOFEDGE => {
pointEdgeRelation ← PointDirectedEdgeTest[ centerOfMass, leftvertex, test];
SELECT pointEdgeRelation FROM
BEFORESTART => RETURN[ RIGHTOFSUBTEND ];
BETWEENSTARTEND => RETURN[ LEFTSPOKEINTERIOR ];
EQUALEND => RETURN[ EQUALLEFTVERTEX ];
AFTEREND => RETURN[ LEFTRAYINTERIOR ];
LEFTOFEDGE => RETURN[ LEFTOFSUBTEND ];
RIGHTOFEDGE => {
pointLineRelation: PointLineRelation ← 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: VertexHandle, centerOfMass, test: Point, outline: BOOL ] RETURNS [status: PointSectorRelation, t, u: VertexHandle] = {
[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.
pointSectorRelation: PointSectorRelation ← PointSectorTest[ v.coordinates, w.coordinates, centerOfMass, test];
WHILE pointSectorRelation = RIGHTOFSUBTEND OR pointSectorRelation = LEFTOFSUBTEND DO
[v, w] ← StepVertex [ v, w, outline];
pointSectorRelation ← PointSectorTest[ v.coordinates, w.coordinates, centerOfMass, test];
ENDLOOP;
RETURN[ pointSectorRelation, v, w ];
};
XOR: PUBLIC PROC[a, b: BOOLEAN] RETURNS[BOOLEAN] = {
Compute the exclusive or of two BOOLEANs
IF (a AND b) THEN RETURN[FALSE];
IF (a OR b) THEN RETURN[TRUE];
RETURN[FALSE];
};
DEISValuePresent: PUBLIC PROC[v: DirectedEdgeIntersectionStatusValue, L: DirectedEdgeIntersectionStatus] RETURNS[BOOLEAN] = {
B: BOOL ← FALSE;
WHILE L # NIL DO
IF L.first = v THEN B ← TRUE;
L ← L.rest;
ENDLOOP;
RETURN[B];
};
IntersectDirectedEdges: PUBLIC PROC [start1, end1, start2, end2: Point] RETURNS [outcome: DirectedEdgeIntersectionStatus ← NIL, intPoint: Point] = {
Rational arithmetic version. Check edges [start1, end1] and [start2, q2end2 for proper intersection, i.e. check whether the endpoints of each edge are distinct, whether the edges have at most one point in common, and if so, that the common point is interior to both edges; if no proper intersection, then just classifies the edge relationship and returns intPoint ← [0, 0].
slope1, slope2, intercept1, intercept2, xIntersect, yIntersect : RN.RatNum;
vertical1, vertical2: BOOL ← FALSE;
start1end1start2, start1end1end2: PointDirectedEdgeRelation;
Set up dummy intersection point
origin: Point ← MakePointFromRatNums[RN.MakeRatNumZero[], RN.MakeRatNumZero[] ];
point: Point;
Check for degenerate edge. If we don't exit here, then we know that each edge is a 1-dimensional object, i.e. has two distinct endpoints.
IF PointEqual[ start1, end1] THEN outcome ← CONS[ START1EQEND1, outcome];
IF PointEqual[ start2, end2] THEN outcome ← CONS[ START2EQEND2, outcome];
IF outcome # NIL THEN RETURN; -- there are more cases of point equality one could test for and add to outcome here
start1end1start2 ← PointDirectedEdgeTest[ start1, end1, start2];
start1end1end2 ← PointDirectedEdgeTest[ start1, end1, end2];
SELECT start1end1start2 FROM
LEFTOFEDGE, RIGHTOFEDGE => SELECT start1end1end2 FROM
LEFTOFEDGE, RIGHTOFEDGE => { -- we calculate the intersection point of the lines containing the two edges, and checking its position with respect to the edges.
vertical1 ← VerticalEdge[start1, end1];
vertical2 ← VerticalEdge[start2, end2];
IF vertical1 AND vertical2 THEN RETURN[ CONS[ DISJOINT, outcome], origin];
IF NOT vertical1 THEN slope1 ← RN.RatNumDivide[
RN.RatNumSubtract[ end1.y, start1.y ],
RN.RatNumSubtract[ end1.x, start1.x ]
];
IF NOT vertical2 THEN slope2 ← RN.RatNumDivide[
RN.RatNumSubtract[ end2.y, start2.y ],
RN.RatNumSubtract[ end2.x, start2.x ]
];
IF NOT vertical1 THEN intercept1 ← RN.RatNumSubtract[ start1.y, RN.RatNumMultiply[ slope1, start1.x ] ];
IF NOT vertical2 THEN intercept2 ← RN.RatNumSubtract[ start2.y, RN.RatNumMultiply[ slope2, start2.x ] ];
IF NOT vertical1 AND NOT vertical2 THEN { -- neither edge vertical
xIntersect ← RN.RatNumDivide[
RN.RatNumSubtract[intercept2, intercept1 ],
RN.RatNumSubtract[slope1, slope2 ]
];
yIntersect ← RN.RatNumAdd[ intercept1, RN.RatNumMultiply[ slope1, xIntersect] ];
}
ELSE IF vertical1 THEN { -- 1st edge is vertical, 2nd edge not vertical
xIntersect ← start1.x;
yIntersect ← RN.RatNumAdd[ intercept2, RN.RatNumMultiply[ slope2, xIntersect] ]
}
ELSE { -- IF vertical2, i.e. 1st edge not vertical, 2nd edge is vertical
xIntersect ← start2.x;
yIntersect ← RN.RatNumAdd[ intercept1, RN.RatNumMultiply[ slope1, xIntersect] ]
};
point ← MakePointFromRatNums[ xIntersect, yIntersect ];
SELECT PointDirectedEdgeTest[start1, end1, point] FROM
BETWEENSTARTEND => SELECT PointDirectedEdgeTest[start2, end2, point] FROM
BETWEENSTARTEND => RETURN[ CONS[ PROPERINTERSECT, outcome], point];
BEFORESTART => RETURN[ CONS[ DISJOINT, outcome], origin];
AFTEREND => RETURN[ CONS[ DISJOINT, outcome], origin];
ENDCASE => ERROR; -- EQUALSTART, EQUALEND, LEFTOFEDGE, RIGHTOFEDGE impossible
EQUALSTART => RETURN[ CONS[ START1INEDGE2, outcome], origin];
EQUALEND => RETURN[ CONS[ END1INEDGE2, outcome], origin];
BEFORESTART => RETURN[ CONS[ DISJOINT, outcome], origin];
AFTEREND => RETURN[ CONS[ DISJOINT, outcome], origin];
ENDCASE => ERROR; -- LEFTOFEDGE, RIGHTOFEDGE impossible
};
BETWEENSTARTEND => RETURN[ CONS[ END2INEDGE1, outcome], origin];
EQUALSTART => RETURN[ CONS[ START1EQEND2, outcome], origin];
EQUALEND => RETURN[ CONS[ END1EQEND2, outcome], origin];
BEFORESTART => RETURN[ CONS[ DISJOINT, outcome], origin];
AFTEREND => RETURN[ CONS[ DISJOINT, outcome], origin];
ENDCASE;
BETWEENSTARTEND => {
outcome ← CONS[ START2INEDGE1, outcome];
SELECT start1end1end2 FROM
LEFTOFEDGE, RIGHTOFEDGE => RETURN[ outcome, origin];
BETWEENSTARTEND => {
outcome ← CONS[ END2INEDGE1 , outcome];
outcome ← CONS[ OVERLAP, outcome];
RETURN[ outcome, origin];
};
EQUALSTART => {
outcome ← CONS[ START1EQEND2, outcome];
outcome ← CONS[ OVERLAP, outcome];
RETURN[ outcome, origin];
};
EQUALEND => {
outcome ← CONS[ END1EQEND2, outcome];
outcome ← CONS[ OVERLAP, outcome];
RETURN[ outcome, origin];
};
BEFORESTART, AFTEREND => { -- could distinguish orientation of overlap
outcome ← CONS[ OVERLAP, outcome];
RETURN[ outcome, origin];
};
ENDCASE;
};
EQUALSTART => {
outcome ← CONS[ START1EQSTART2, outcome];
SELECT start1end1end2 FROM
LEFTOFEDGE, RIGHTOFEDGE => RETURN[ outcome, origin];
BETWEENSTARTEND => {
outcome ← CONS[ END2INEDGE1 , outcome];
outcome ← CONS[ OVERLAP, outcome];
RETURN[ outcome, origin];
};
EQUALEND => {
outcome ← CONS[ END1EQEND2, outcome];
outcome ← CONS[ OVERLAP, outcome];
RETURN[ outcome, origin];
};
BEFORESTART => RETURN[ outcome, origin];
AFTEREND => {
outcome ← CONS[ OVERLAP, outcome];
RETURN[ outcome, origin];
};
ENDCASE => ERROR; -- start1end1end2 = EQUALSTART is impossible
};
EQUALEND => {
outcome ← CONS[ END1EQSTART2, outcome];
SELECT start1end1end2 FROM
LEFTOFEDGE, RIGHTOFEDGE => RETURN[ outcome, origin];
BETWEENSTARTEND => {
outcome ← CONS[ END2INEDGE1 , outcome];
outcome ← CONS[ OVERLAP, outcome];
RETURN[ outcome, origin];
};
EQUALSTART => {
outcome ← CONS[ START1EQEND2, outcome];
outcome ← CONS[ OVERLAP, outcome];
RETURN[ outcome, origin];
};
BEFORESTART => {
outcome ← CONS[ OVERLAP, outcome];
RETURN[ outcome, origin];
};
AFTEREND => RETURN[ outcome, origin];
ENDCASE => ERROR; -- start1end1end2 = EQUALEND is impossible
};
BEFORESTART => SELECT start1end1end2 FROM
LEFTOFEDGE, RIGHTOFEDGE => RETURN[ CONS[ DISJOINT, outcome], origin];
BETWEENSTARTEND => {
outcome ← CONS[ END2INEDGE1 , outcome];
outcome ← CONS[ OVERLAP, outcome];
RETURN[ outcome, origin];
};
EQUALSTART => {
outcome ← CONS[ START1EQEND2, outcome];
RETURN[ outcome, origin];
};
EQUALEND => {
outcome ← CONS[ END1EQEND2, outcome];
outcome ← CONS[ OVERLAP, outcome];
RETURN[ outcome, origin];
};
BEFORESTART => RETURN[ CONS[ DISJOINT, outcome], origin];
AFTEREND => {
outcome ← CONS[ OVERLAP, outcome];
RETURN[ outcome, origin];
};
ENDCASE;
AFTEREND => SELECT start1end1end2 FROM
LEFTOFEDGE, RIGHTOFEDGE => RETURN[ CONS[ DISJOINT, outcome], origin];
BETWEENSTARTEND => {
outcome ← CONS[ END2INEDGE1 , outcome];
outcome ← CONS[ OVERLAP, outcome];
RETURN[ outcome, origin];
};
EQUALSTART => {
outcome ← CONS[ START1EQEND2, outcome];
outcome ← CONS[ OVERLAP, outcome];
RETURN[ outcome, origin];
};
EQUALEND => {
outcome ← CONS[ END1EQEND2, outcome];
RETURN[ outcome, origin];
};
BEFORESTART => {
outcome ← CONS[ OVERLAP, outcome];
RETURN[ outcome, origin];
};
AFTEREND => RETURN[ CONS[ DISJOINT, outcome], origin];
ENDCASE;
ENDCASE;
};
StepVertex: PUBLIC PROC[ v1, w1: VertexHandle, outline: BOOL] RETURNS [ v2, w2: VertexHandle] = {
RETURN [w1, NextVertex[ v1, w1, outline] ]
};
NextVertex: PUBLIC PROC[ v, w: VertexHandle, outline: BOOL] RETURNS [ z: VertexHandle] = {
IF outline THEN z ← NextOutlineVertex[v,w] ELSE z ← NextPolygonVertex[v,w];
RETURN [z]
};
PreviousVertex: PUBLIC PROC[ v, w: VertexHandle, outline: BOOL] RETURNS [ z: VertexHandle] = {
IF outline THEN z ← NewPrevOutlineVertex[v,w] ELSE z ← PreviousPolygonVertex[v,w];
RETURN [z]
};
NextOutlineVertex: PUBLIC PROC[ v, w: VertexHandle] RETURNS [ z: VertexHandle] = {
A: AdjacencyHandleList ← 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: VertexHandle] RETURNS [ VertexHandle] = {
A: AdjacencyHandleList ← w.adjacentVertices;
WHILE A.first.vertex # v DO
A ← A.rest
ENDLOOP;
RETURN [A.rest.first.vertex]
};
PreviousOutlineVertex: PUBLIC PROC [w: VertexHandle] RETURNS [v:VertexHandle] ~ {
Assuming that w is a vertex on the outline of some Figure containing at least two vertices, find the vertex v which precedes w in the counterclockwise ordering of vertices (we think of this counterclockwise ordering as being defined with respect to the INTERIOR of the figure on whose outline w lies).
ahl: AdjacencyHandleList ← w.adjacentVertices;
WHILE NOT ahl.first.leftRegionExterior DO ahl ← ahl.rest ENDLOOP;
v ← ahl.first.vertex;
};
NewPrevOutlineVertex: PUBLIC PROC [v, w: VertexHandle] RETURNS [z: VertexHandle] ~ {
Assuming that [v,w] is an edge on the outline of some Figure containing at least two vertices, find the vertex z which precedes w in the counterclockwise ordering of vertices (we think of this counterclockwise ordering as being defined with respect to the INTERIOR of the figure on whose outline w lies).
A: AdjacencyHandleList ← v.adjacentVertices;
WHILE A.first.vertex # w DO
A ← A.rest
ENDLOOP;
RETURN [A.rest.first.vertex]
};
PreviousPolygonVertex: PUBLIC PROC [v, w: VertexHandle] RETURNS [z:VertexHandle] ~ {
[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: AdjacencyHandleList ← 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]
};
FindAdjacency: PUBLIC PROC[v, w: VertexHandle] RETURNS [vTow, wTov: AdjacencyHandle]= {
v and w are adjacent vertices. Search and find the AdjacencyHandles with each points to the other.
ahlv, ahlw: AdjacencyHandleList;
ahlv ← v.adjacentVertices;
ahlw ← w.adjacentVertices;
WHILE ahlv.first.vertex # w DO
ahlv ← ahlv.rest;
ENDLOOP;
WHILE ahlw.first.vertex # v DO
ahlw ← ahlw.rest;
ENDLOOP;
RETURN[ ahlv.first, ahlw.first ];
};
InitVertexHandle: PUBLIC PROC RETURNS [VertexHandle] = {
Create an empty VertexHandle.
vertexhandle: VertexHandle ← NIL;
RETURN[vertexhandle];
};
Slope: PUBLIC PROC[p1, p2: Point] RETURNS [slope:RN.RatNum] ={
Compute the slope of the line determined by two points.
positiveSlope:BOOL;
IF ABS[p2.x-p1.x]<0.0001 THEN {
positiveSlope←(p2.x>=p1.x AND p2.y>=p1.y) OR (p2.x<=p1.x AND p2.y<=p1.y);
IF positiveSlope THEN slope�.0 ELSE slope ← -10000.0
}
ELSE
slope←(p2.y-p1.y)/(p2.x-p1.x);
RETURN[slope];
};
MakePointFromRatNums: PUBLIC PROC[x1, y1: RN.RatNum] RETURNS [p: Point] = {
Bundle up two real numbers as an point
p ← [x: x1, y: y1 ];
RETURN[ p ];
};
MakePointFromReals: PUBLIC PROC[x1, y1: REAL] RETURNS [p: Point] = {
Bundle up two real numbers as an point
p ← [x: RN.RatNumFromREAL[x1], y: RN.RatNumFromREAL[y1] ];
RETURN[ p ];
};
ImagerVecFromPoint: PUBLIC PROC[p: Point] RETURNS [q: Imager.VEC] = {
q ← [ RN.RatNumToREAL[p.x], RN.RatNumToREAL[p.y] ];
RETURN[ q ];
};
Constructor: PUBLIC PROC [convexpolygon: Imager.Trajectory, interiorstate, exteriorstate: CSI.State ] RETURNS [v: VertexHandle] = {
Convert a Trajectory representing a convex polygon to the Combiner's data structure. Assumes that the vertices occur in clockwise order in the trajectory, that is, if we peel off convexpolygon.lp, then go back to convexpolygon.prev, peel off its lp, etc. that we get the vertices in counterclockwise order.
v ← InitVertexHandle[];
WHILE convexpolygon.prev # NIL DO
v ← AddVertexToPolygon[v, convexpolygon.lp.x, convexpolygon.lp.y, interiorstate, exteriorstate];
convexpolygon ← convexpolygon.prev;
ENDLOOP;
v ← AddVertexToPolygon[ v, convexpolygon.lp.x, convexpolygon.lp.y, interiorstate, exteriorstate ];
RETURN[v];
};
GetPolygonState: PUBLIC PROC [v, w: VertexHandle] RETURNS [state: CSI.State] = {
[v, w] is a (counterclockwise) directed edge of an internal polygon. Obtain the polygon's state.
vTow, wTov: AdjacencyHandle;
[ vTow, wTov ] ← FindAdjacency[ v, w ];
state ← vTow.leftState;
};
PolygonExtractor: PUBLIC PROC [v, w: VertexHandle] RETURNS [ImagerPolygonAndStateList] = {
[v,w] is a counterclockwise oriented edge of a polygon contained in the outline of the current figure. Extract the internal polygons and their state from a VertexHandle. Uses Depth First Search. It is assumed that the VertexHandle has at least three vertices.
vTow, wTov: AdjacencyHandle;
firstv: VertexHandle;
outline: BOOL ← FALSE;
trajectory: Imager.Trajectory;
state: CSI.State;
vec: Imager.VEC;
psHandle: ImagerPolygonAndStateHandle;
polygonList: ImagerPolygonAndStateList;
firstv ← v;
vec ← ImagerVecFromPoint[v.coordinates];
trajectory ← ImagerPath.MoveTo[vec];
Extract state
state ← GetPolygonState[v, w]; -- only need to set state once
Set leftRegionVisited fields of edges of this polygon, and build trajectory
vec ← ImagerVecFromPoint[w.coordinates];
trajectory ← ImagerPath.LineTo[trajectory, vec ];
[ vTow, wTov ] ← FindAdjacency[ v, w ];
vTow.leftRegionVisited ← TRUE;
WHILE w # firstv DO
[v, w] ← StepVertex[v,w, outline];
vec ← ImagerVecFromPoint[w.coordinates];
trajectory ← ImagerPath.LineTo[trajectory, vec ];
[ vTow, wTov ] ← FindAdjacency[ v, w ];
vTow.leftRegionVisited ← TRUE;
ENDLOOP;
psHandle ← NEW[ImagerPolygonAndStateRecord ← [trajectory: trajectory, state: state] ];
polygonList ← CONS[ psHandle, NIL];
Go around edges again; check (opposite orientation of) each to see if it's an interior edge (i.e. not on the outline), and if the polygon to which it belongs is unprocessed, if so, recursive call on that polygon.
[v, w] ← StepVertex[v, w, outline];
[ vTow, wTov ] ← FindAdjacency[ v, w ];
IF NOT wTov.leftRegionExterior THEN
IF NOT wTov.leftRegionVisited THEN
polygonList ← AppendImagerPolygonAndStateList[ PolygonExtractor[w, v ], polygonList];
WHILE w # firstv DO
[v, w] ← StepVertex[v,w, outline];
[ vTow, wTov ] ← FindAdjacency[ v, w ];
IF NOT wTov.leftRegionExterior THEN
IF NOT wTov.leftRegionVisited THEN
polygonList ← AppendImagerPolygonAndStateList[ PolygonExtractor[w, v ], polygonList];
ENDLOOP;
RETURN[polygonList];
};
ClearVisitedFields: PUBLIC PROC [v, w: VertexHandle] = {
[v,w] is a counterclockwise oriented edge of a polygon contained in the outline of the current figure. Clear the leftRegionVisited fields of all edges of all polygons interior to a VertexHandle, assumed by this particular ClearVisitedFields to be an VertexHandle. Uses Depth First Search.
vTow, wTov: AdjacencyHandle;
firstv: VertexHandle ← v;
outline: BOOL ← FALSE;
Set leftRegionVisited fields of edges of this polygon, and build trajectory
[ vTow, wTov ] ← FindAdjacency[ v, w ];
vTow.leftRegionVisited ← FALSE;
WHILE w # firstv DO
[v, w] ← StepVertex[v,w, outline];
[ vTow, wTov ] ← FindAdjacency[ v, w ];
vTow.leftRegionVisited ← FALSE;
ENDLOOP;
Go around edges again; check (opposite orientation of) each to see if it's an interior edge (i.e. not on the outline), and if the polygon to which it belongs is uncleared, if so, recursive call on that polygon.
[v, w] ← StepVertex[v, w, outline];
[ vTow, wTov ] ← FindAdjacency[ v, w ];
IF wTov.leftRegionVisited THEN
ClearVisitedFields[w, v ];
WHILE w # firstv DO
[v, w] ← StepVertex[v,w, outline];
[ vTow, wTov ] ← FindAdjacency[ v, w ];
IF wTov.leftRegionVisited THEN
ClearVisitedFields[w, v ];
ENDLOOP;
};
AppendImagerPolygonAndStateList: PUBLIC PROC [l1: ImagerPolygonAndStateList, l2: ImagerPolygonAndStateList ← NIL] RETURNS[val: ImagerPolygonAndStateList] = {
z: ImagerPolygonAndStateList ← NIL;
val ← l2;
IF l1 = NIL THEN RETURN[val];
val ← CONS[l1.first, val];
z ← val;
UNTIL (l1 ← l1.rest) = NIL DO
z.rest ← CONS[l1.first, z.rest];
z ← z.rest;
ENDLOOP;
RETURN[val];
}; -- of AppendImagerPolygonAndStateList
DumpVertexHandle: PUBLIC PROC [v: VertexHandle, filename: Rope.ROPE] ~ {
Dump a VertexHandle to a file. Does Depth First Search.
visitedValue: BOOL;
out: IO.STREAM ← FS.StreamOpen[filename, $create];
IF v = NIL THEN { out.Close[]; RETURN }; -- no vertices
IF v.adjacentVertices = NIL THEN { -- one vertex
out.PutF["\n%g: ", IO.int[v. index]];
out.PutF[" ( %g , %g ) []", IO.rope[RN.RatNumToRatRope[v.coordinates.x, FALSE, TRUE]], IO.rope[RN.RatNumToRatRope[v.coordinates.y, FALSE, TRUE]] ];
}
ELSE { -- two or more vertices
visitedValue ← v.adjacentVertices.first.vertex.visited;
DumpVertexHandleSubr[v, NOT visitedValue, out]; -- specify toggling of visitedValue
};
out.PutChar['\n]; out.PutChar['.];
out.Close[];
RETURN;
};
DumpVertexHandleSubr: PROC[v: VertexHandle, visitedValue: BOOL, out: IO.STREAM] = {
Assumes two or more vertices
vAdjList: AdjacencyHandleList ← v.adjacentVertices;
lastVertex, nextVertex: VertexHandle;
nextAdj: AdjacencyHandle;
stateRope: Rope.ROPE;
done: BOOL;
Record that we've visited v
v.visited ← visitedValue; -- record that we've visited this vertex
Write v
out.PutF["\n%g: ", IO.int[v.index]];
out.PutF[" ( %g , %g ) [", IO.rope[RN.RatNumToRatRope[v.coordinates.x, FALSE, TRUE]], IO.rope[RN.RatNumToRatRope[v.coordinates.y, FALSE, TRUE]] ];
Write adjacencies of v
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
nextAdj ← vAdjList.first;
nextVertex ← nextAdj.vertex;
IF nextVertex = lastVertex THEN done ← TRUE; -- test for last vertex to be processed
stateRope ← CSI.RopeFromState[nextAdj.leftState];
out.PutF[" ( %g , %g , %g ) ", IO.int[nextVertex.index], IO.rope[stateRope], IO.bool[nextAdj.leftRegionExterior]];
vAdjList ← vAdjList.rest;
ENDLOOP;
out.PutChar[']];
Recursive calls for adjacencies of v
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
nextVertex ← vAdjList.first.vertex;
IF nextVertex = lastVertex THEN done ← TRUE; -- test for last vertex to be processed
IF (nextVertex.visited # visitedValue) THEN DumpVertexHandleSubr[ nextVertex, visitedValue, out];
vAdjList ← vAdjList.rest;
ENDLOOP;
RETURN;
};
ReadIOVHLFromFile: PUBLIC PROC [filename: Rope.ROPE, MessageStream: IO.STREAM] RETURNS [ioVHList: IOVertexHandleList] ~ {
done: BOOL ← FALSE;
ratNumOK, doneAdj: BOOL;
stateRope: Rope.ROPE;
charsSkipped: INT; -- dummy to satisfy GetTokenRope parameter list
stateRead: CSI.State;
leftRExt: BOOL;
indexRead, adjIndexRead: INT;
xRead, yRead: RN.RatNum;
ioAHList: IOAdjacencyHandleList;
ioVHandle: IOVertexHandle;
ioAHandle: IOAdjacencyHandle;
puncChar: CHAR;
in: IO.STREAM ← FS.StreamOpen[filename, $read];
ioVHList ← NIL;
[]← in.SkipWhitespace[];
IF in.PeekChar[] = '. THEN done ← TRUE;
WHILE NOT done DO
indexRead ← in.GetInt[ ];
[]← in.SkipWhitespace[]; puncChar ← in.GetChar[ ];
IF puncChar # ': THEN MessageStream.PutF["Colon expected"];
[]← in.SkipWhitespace[]; puncChar ← in.GetChar[ ];
IF puncChar # '( THEN MessageStream.PutF["Left paren expected"];
[ xRead, ratNumOK] ← RN.ReadRatNum[ in];
IF NOT ratNumOK THEN MessageStream.PutF["Error reading x coordinate"];
[]← in.SkipWhitespace[]; puncChar ← in.GetChar[ ];
IF puncChar # ', THEN MessageStream.PutF["Comma expected"];
[ yRead, ratNumOK] ← RN.ReadRatNum[ in];
IF NOT ratNumOK THEN MessageStream.PutF["Error reading y coordinate"];
[]← in.SkipWhitespace[]; puncChar ← in.GetChar[ ];
IF puncChar # ') THEN MessageStream.PutF["Right paren expected"];
[]← in.SkipWhitespace[]; puncChar ← in.GetChar[ ];
IF puncChar # '[ THEN MessageStream.PutF["Left square bracket expected"];
doneAdj ← FALSE;
ioAHList ← NIL;
[]← in.SkipWhitespace[];
IF in.PeekChar[] = '] THEN doneAdj ← TRUE;
WHILE NOT doneAdj DO
[]← in.SkipWhitespace[]; puncChar ← in.GetChar[ ];
IF puncChar # '( THEN MessageStream.PutF["Left paren expected"];
adjIndexRead ← in.GetInt[];
[]← in.SkipWhitespace[]; puncChar ← in.GetChar[ ];
IF puncChar # ', THEN MessageStream.PutF["Comma expected"];
[stateRope, charsSkipped ] ← in.GetTokenRope[IO.IDProc];
stateRead ← CSI.StateFromRope[ stateRope ];
[]← in.SkipWhitespace[]; puncChar ← in.GetChar[ ];
IF puncChar # ', THEN MessageStream.PutF["Comma expected"];
leftRExt ← in.GetBool[];
[]← in.SkipWhitespace[]; puncChar ← in.GetChar[ ];
IF puncChar # ') THEN MessageStream.PutF["Right paren expected"];
ioAHandle ← NEW[IOAdjacency ← [ vertex: adjIndexRead, leftState: stateRead, leftRegionExterior: leftRExt ] ];
ioAHList ← CONS[ ioAHandle , ioAHList ];
[]← in.SkipWhitespace[];
IF in.PeekChar[] = '] THEN doneAdj ← TRUE;
ENDLOOP;
[ ] ← in.GetChar[ ]; -- toss right square bracket
ioVHandle ← NEW[ IOVertex ← [coordinates: MakePointFromRatNums[xRead, yRead],
index: indexRead, adjacentVertices: ioAHList ] ];
ioVHList ← CONS[ ioVHandle, ioVHList ];
[]← in.SkipWhitespace[];
IF in.PeekChar[] = '. THEN done ← TRUE;
ENDLOOP;
};
VHandleFromIOVHL: PUBLIC PROC [ioVHList: IOVertexHandleList] RETURNS [v: VertexHandle, numberVertices: INT] ~ {
Convert an IOVertexHandleList to a VertexHandle. The particular VertexHandle v returned will be chosen so as to be on the outline of the figure. numberVertices is the number of vertices encountered in the converted IOVertexHandleList.
vHList: VertexHandleList;
scratchVHL: VertexHandleList;
scratchIOVHL: IOVertexHandleList;
vHandle: VertexHandle;
adjacentVertex: VertexHandle;
aHList, aHListLast: AdjacencyHandleList;
aHandle : AdjacencyHandle;
ioAHList: IOAdjacencyHandleList;
ioAHandle: IOAdjacencyHandle;
Create initial list of VertexHandles containing vertex indices
numberVertices ← 0;
vHList ← NIL;
scratchIOVHL ← ioVHList;
WHILE scratchIOVHL # NIL DO
numberVertices ← numberVertices + 1;
vHandle ← NEW[ Vertex ← [coordinates: scratchIOVHL.first.coordinates,
index: scratchIOVHL.first.index, adjacentVertices: NIL, visited: FALSE] ];
vHList ← CONS[ vHandle, vHList ];
scratchIOVHL ← scratchIOVHL.rest;
ENDLOOP;
scratchVHL ← ReverseVHL[ vHList ]; -- reverse to put vertices in same order as ioVHList
vHList ← scratchVHL;
Fill in links to adjacent vertices
WHILE scratchVHL # NIL DO
vHandle ← scratchVHL.first;
ioAHList ← ioVHList.first.adjacentVertices;
aHList ← NIL; -- initialize
WHILE ioAHList # NIL DO -- assumes adjacent vertices occur in reverse clockwise order; this loop will restore correct order.
ioAHandle ← ioAHList.first;
adjacentVertex ← SearchVHL[ vHList, ioAHandle.vertex ]; -- these calls assume call by value, i.e. that vHList always points to the head of the list
aHandle ← NEW[Adjacency ← [ vertex: adjacentVertex, leftState: ioAHandle.leftState, leftRegionExterior: ioAHandle.leftRegionExterior, leftRegionVisited: FALSE, intersectionPolygonEdge: FALSE ] ];
IF aHandle.leftRegionExterior THEN v ← vHandle; -- identify vertex on outline of figure
aHList ← CONS[ aHandle, aHList ];
IF aHList.rest = NIL THEN aHListLast ← aHList; -- save pointer for setting circularity
ioAHList ← ioAHList.rest;
ENDLOOP;
aHListLast.rest ← aHList; -- make list circular
vHandle.adjacentVertices ← aHList; -- attach to current vertex
scratchVHL ← scratchVHL.rest;
ioVHList ← ioVHList.rest; -- advance scratchVHL and ioVHList in lock step
ENDLOOP;
RETURN[ v, numberVertices ];
};
SearchVHL: PUBLIC PROC [vHList: VertexHandleList, key: INT] RETURNS [VertexHandle] ~ {
Search vHList for the element whose index is key;
WHILE vHList # NIL DO
IF vHList.first.index = key THEN RETURN [vHList.first ];
vHList ← vHList.rest;
ENDLOOP;
RETURN [NIL];
};
ReverseVHL: PUBLIC PROCEDURE [list: VertexHandleList] RETURNS[val: VertexHandleList] = {
val ← NIL;
UNTIL list = NIL DO
val ← CONS[list.first, val];
list ← list.rest;
ENDLOOP;
RETURN[val];
}; -- of Reverse
VertexVerifyIOVHLFromFile: PUBLIC PROC [filename: Rope.ROPE, MessageStream: IO.STREAM] RETURNS [maxVertexIndex: CARDINAL ← 0] ~ {
VERTEXDATA: TYPE = { PRESENT, ADJACENCY, NOTPRESENT };
MAXFIGUREVERTICES: CARDINAL = 2000; -- maximum number of vertices in figure for verifier.
done: BOOL ← FALSE;
ratNumOK, doneAdj: BOOL;
stateRope: Rope.ROPE;
charsSkipped: INT; -- dummy to satisfy GetTokenRope parameter list
leftRExt: BOOL;
indexRead, adjIndexRead: INT;
xRead, yRead: RN.RatNum;
puncChar: CHAR;
in: IO.STREAM ← FS.StreamOpen[filename, $read];
vertices: ARRAY [1..MAXFIGUREVERTICES] OF VERTEXDATA ← ALL[ NOTPRESENT ];
I: INT;
minVertexIndex: CARDINAL ← MAXFIGUREVERTICES; -- minimum vertex index seen
[]← in.SkipWhitespace[];
IF in.PeekChar[] = '. THEN done ← TRUE;
WHILE NOT done DO
indexRead ← in.GetInt[ ];
vertices[ indexRead ] ← PRESENT;
IF indexRead < minVertexIndex THEN minVertexIndex ← indexRead;
IF indexRead > maxVertexIndex THEN maxVertexIndex ← indexRead;
[]← in.SkipWhitespace[]; puncChar ← in.GetChar[ ];
IF puncChar # ': THEN MessageStream.PutF["Colon expected"];
[]← in.SkipWhitespace[]; puncChar ← in.GetChar[ ];
IF puncChar # '( THEN MessageStream.PutF["Left paren expected"];
[ xRead, ratNumOK] ← RN.ReadRatNum[ in];
IF NOT ratNumOK THEN MessageStream.PutF["Error reading x coordinate"];
[]← in.SkipWhitespace[]; puncChar ← in.GetChar[ ];
IF puncChar # ', THEN MessageStream.PutF["Comma expected"];
[ yRead, ratNumOK] ← RN.ReadRatNum[ in];
IF NOT ratNumOK THEN MessageStream.PutF["Error reading y coordinate"];
[]← in.SkipWhitespace[]; puncChar ← in.GetChar[ ];
IF puncChar # ') THEN MessageStream.PutF["Right paren expected"];
[]← in.SkipWhitespace[]; puncChar ← in.GetChar[ ];
IF puncChar # '[ THEN MessageStream.PutF["Left square bracket expected"];
doneAdj ← FALSE;
[]← in.SkipWhitespace[];
IF in.PeekChar[] = '] THEN doneAdj ← TRUE;
WHILE NOT doneAdj DO
[]← in.SkipWhitespace[]; puncChar ← in.GetChar[ ];
IF puncChar # '( THEN MessageStream.PutF["Left paren expected"];
adjIndexRead ← in.GetInt[];
IF adjIndexRead < minVertexIndex THEN minVertexIndex ← adjIndexRead;
IF adjIndexRead > maxVertexIndex THEN maxVertexIndex ← adjIndexRead;
IF vertices[ adjIndexRead ] = NOTPRESENT THEN
vertices[ adjIndexRead ] ← ADJACENCY;
[]← in.SkipWhitespace[]; puncChar ← in.GetChar[ ];
IF puncChar # ', THEN MessageStream.PutF["Comma expected"];
[stateRope, charsSkipped ] ← in.GetTokenRope[IO.IDProc];
[]← in.SkipWhitespace[]; puncChar ← in.GetChar[ ];
IF puncChar # ', THEN MessageStream.PutF["Comma expected"];
leftRExt ← in.GetBool[];
[]← in.SkipWhitespace[]; puncChar ← in.GetChar[ ];
IF puncChar # ') THEN MessageStream.PutF["Right paren expected"];
[]← in.SkipWhitespace[];
IF in.PeekChar[] = '] THEN doneAdj ← TRUE;
ENDLOOP;
[ ] ← in.GetChar[ ]; -- toss right square bracket
[]← in.SkipWhitespace[];
IF in.PeekChar[] = '. THEN done ← TRUE;
ENDLOOP;
MessageStream.PutF["\nMinimum vertex index read is %g", IO.int[ minVertexIndex] ];
MessageStream.PutF["\nMaximum vertex index read is %g", IO.int[ maxVertexIndex] ];
I ← minVertexIndex - 1;
WHILE I < maxVertexIndex DO
I ← I + 1;
IF vertices[ I ] # PRESENT THEN {
IF vertices[ I ] = ADJACENCY THEN
MessageStream.PutF["\nVertex No. %g is only referred to in an adjacency", IO.int[ I] ]
ELSE
MessageStream.PutF["\nVertex No. %g is not present", IO.int[ I] ]
};
ENDLOOP;
};
FindPolygonForPoint: PUBLIC PROC [v, w: VertexHandle, test: Point] RETURNS [ok: BOOL, y, z: VertexHandle] ~ {
[v, w] is a (counterclockwise) directed edge of an internal polygon. If test is found within the closure of the current structure (i.e. in its interior or on its outline), then ok = TRUE, and [y, z] is a (counterclockwise) directed edge of the unique internal polygon in whose interior test lies, or a (counterclockwise) directed edge of an internal polygon in whose boundary test lies. If test is not found within the closure of the current structure, then ok = FALSE, y = v, and z = w.
polygoncom: Point;
status: PointSectorRelation;
v5: VertexHandle ← v;
w5: VertexHandle ← w;
temp: VertexHandle;
v5Tow5, w5Tov5: AdjacencyHandle;
[v5Tow5, w5Tov5] ← FindAdjacency[ v5, w5];
IF v5Tow5.leftRegionExterior THEN ERROR;
polygoncom ← CenterOfMass[ v5, w5, FALSE]; -- find com of internal polygon.
[status, v5, w5] ← FindSubtendForPoint[ v5, w5, polygoncom, test, 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 test
temp ← v5; v5 ← w5; w5 ← temp; -- flip v5 and w5 to move to next polygon
[ v5Tow5, w5Tov5] ← FindAdjacency[ v5, w5];
IF v5Tow5.leftRegionExterior THEN RETURN[ FALSE, v, w];
polygoncom ← CenterOfMass[ v5, w5, FALSE];
[status, v5, w5] ← FindSubtendForPoint[ v5, w5, polygoncom, test, FALSE ];
ENDLOOP;
RETURN[ TRUE, v5, w5];
};
FindVertexForPoint: PUBLIC PROC [v: VertexHandle, test: Point] RETURNS [w: VertexHandle] ~ {
Find vertex closest to test point
visitedValue: BOOL;
currentDist: RN.RatNum;
IF v = NIL OR v.adjacentVertices = NIL THEN RETURN[v] -- no vertices
ELSE {
visitedValue ← v.adjacentVertices.first.vertex.visited;
currentDist ← DistanceSquare[v.coordinates, test];
[w, currentDist] ← FindVertexForPointSubr[v, NOT visitedValue, test, v, currentDist]; -- specify toggling of visitedValue
RETURN[w];
};
};
FindVertexForPointSubr: PROC[v: VertexHandle, visitedValue: BOOL, test: Point, currentBest: VertexHandle, currentBestDist: RN.RatNum] RETURNS [best: VertexHandle, bestDist: RN.RatNum] = {
vAdjList: AdjacencyHandleList ← v.adjacentVertices;
lastVertex, nextVertex: VertexHandle;
vDist: RN.RatNum;
done: BOOL;
Record that we've visited v
v.visited ← visitedValue; -- record that we've visited this vertex
Compute distance to test point
vDist ← DistanceSquare[v.coordinates, test];
IF RN.RatNumLess[ vDist, currentBestDist] THEN {
currentBest ← v;
currentBestDist ← vDist
};
Recursive calls for adjacencies of v
best ← currentBest;
bestDist ← currentBestDist;
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
nextVertex ← vAdjList.first.vertex;
IF nextVertex = lastVertex THEN done ← TRUE; -- test for last vertex to be processed
IF (nextVertex.visited # visitedValue) THEN [best, bestDist] ← FindVertexForPointSubr[ nextVertex, visitedValue, test, best, bestDist];
vAdjList ← vAdjList.rest;
ENDLOOP;
RETURN;
};
SetPolygonState: PUBLIC PROC [v, w: VertexHandle, state: CSI.State, setLRE: BOOL ← FALSE] = {
[v, w] is a (counterclockwise) directed edge of an internal polygon. Its state is set. setLRE controls whether leftRegionExterior fields are set to FALSE.
vTow, wTov: AdjacencyHandle;
firstv: VertexHandle ← v;
[ vTow, wTov ] ← FindAdjacency[ v, w ];
vTow.leftState ← state;
IF setLRE THEN vTow.leftRegionExterior ← FALSE;
WHILE w # firstv DO
[v, w] ← StepVertex[v,w, FALSE];
[ vTow, wTov ] ← FindAdjacency[ v, w ];
vTow.leftState ← state;
IF setLRE THEN vTow.leftRegionExterior ← FALSE;
ENDLOOP;
};
ThreeOrMoreVertices: PUBLIC PROC [w: VertexHandle] 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 ];
};
END.