Last Edited by: Arnon, June 20, 1985 4:44:33 pm PDT

RealFns USING [Sin, Cos],

RatNums,

ClientStateInfo,

RVHandleUtils;

EXPORTS RVHandleUtils =

vhandlefirst 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 vhandlefirst (call it vhandlelast), and before vhandlefirst, in the counterclockwise ordering of vertices. vhandlefirst is returned, so that subsequently added vertices will always be inserted just before vhandlefirst.

The current coding (specifically case of three or more vertices previously) assumes that the figure is nothing more than a polygon, i.e. has no internal edges.

vhandlethis, vhandlelast: VertexHandle;

ahthistofirst, ahthistolast, ahfirsttothis, ahlasttothis, ahthis, ahfirst : AdjacencyHandle;

ahlist, ahlistthis, ahlistfirst, ahlistlast : AdjacencyHandleList;

leftRegionVisitedValue: BOOL;

Make a VertexHandle for the new vertex

vhandlethis ← NEW[ Vertex ← [coordinates: MakePointFromRatNums[x, y], index: vertexIndex, adjacentVertices: NIL, visited: FALSE] ];

vertexIndex ← vertexIndex + 1;

IF vhandlefirst = NIL THEN RETURN [vhandlethis] --This is first vertex(Figure empty prevsly)

ahlistfirst ← vhandlefirst.adjacentVertices;

IF ahlistfirst = NIL THEN { -- One vertex previously --

Find vhandlelast (Note that we know at this point that ahlistfirst # NIL)

IF ahlistfirst.rest = ahlistfirst THEN vhandlelast ← ahlistfirst.first.vertex ELSE vhandlelast ← PreviousOutlineVertex[vhandlefirst]; -- check specially for case of two vertices previously, since in that case we can't go looking for the previous outline vertex by expecting to find a vertex adjacent to vhandlefirst with leftRegionExterior = TRUE, because in the two vertex case, the single vertex adjacent to vhandlefirst has leftRegionExterior = FALSE in order to remain correct when more vertices are added to the polygon.

ahlistlast ← vhandlelast.adjacentVertices;

Get value of visited field (all vertices in the polygon must have same field value)

leftRegionVisitedValue ← ahlistfirst.first.leftRegionVisited;

Create AdjacencyHandleList for the new vertex

ahthistofirst ← NEW[Adjacency ← [ vertex: vhandlefirst, leftState: state, leftRegionVisited: leftRegionVisitedValue, leftRegionExterior: FALSE, intersectionPolygonEdge: FALSE ] ];

ahlist ← CONS[ ahthistofirst, NIL ];

ahthistolast← NEW[Adjacency ← [ vertex: vhandlelast, leftState: NIL, leftRegionVisited: leftRegionVisitedValue, leftRegionExterior: TRUE, intersectionPolygonEdge: FALSE ] ];

ahlistthis ← CONS[ ahthistolast, ahlist ];

ahlist.rest ← ahlistthis; -- make circular --

vhandlethis.adjacentVertices ← ahlistthis;

IF ahlistfirst.rest = ahlistfirst THEN { -- Two vertices previously --

ELSE { -- Three or more vertices previously --

RETURN [ vhandlefirst ];

};

[v,w] is a counterclockwise-oriented edge of a polygon which is assumed to already have at least three vertices (i.e. have a nonempty interior). point is an external point, which is imbedded in a vertex x. An edge from v to x is created, and an edge [y: x , z: w ] from x to w is created. The edge [x,w] is returned so that the polygon can be further expanded by a new vertex occurring after x in counterclockwise order. The edge [v,w] is deleted.

ahlsave: AdjacencyHandleList;

Create a VertexHandle for the new vertex.

x ← NEW[ Vertex ← [coordinates: point, adjacentVertices: NIL] ];

Get adjacency information needed to create the new edges.

[vTow, wTov] ← FindAdjacency[ v, w];

Set up the edge from v to x (and delete that w is adjacent to v).

vTow.vertex ← x;

Edge from w to x (and delete that v is adjacent to w).

wTov.vertex ← x;

Fill in edge from x to w

ah ← NEW[ Adjacency ← [vertex: w,

x.adjacentVertices ← CONS[ ah, x.adjacentVertices ];

ahlsave ← x.adjacentVertices; -- save pointer to last list cell for making circular list

Edge from x to v.

ah ← NEW[ Adjacency ← [vertex: v,

x.adjacentVertices ← CONS[ ah, x.adjacentVertices ];

ahlsave.rest ← x.adjacentVertices; -- make list of adjacencies circular

RETURN[ x, w];

};

Cartesian Product of brush and vector [start,end] to make a sausage. brush is assumed to be a convex polygon with counterclockwise ordered vertices. sausage is the same sort of polygon.

outline:BOOL←TRUE;

delta:Point←[end.x-start.x,end.y-start.y];

temp:VertexHandle;

done:BOOL←FALSE;

w:VertexHandle𡤋rush;

v:VertexHandle←PreviousOutlineVertex[w];

firstv:VertexHandle←v;

sausage←InitVertexHandle[];

Find an initialvertex (firstv) on the unswept boundary

WHILE NOT done DO temp←NEW[Vertex←[coordinates:[v.coordinates.x+delta.x,v.coordinates.y+delta.y],adjacentVertices:NIL,visited:FALSE]];
IF CCW[temp,v,w] THEN done←TRUE ELSE[v,w]←StepVertex[v,w,outline];
ENDLOOP;
firstv←v;
done←FALSE;

Fill in unswept boundary up to transition to swept boundary

WHILE NOT done DO temp←NEW[Vertex←[coordinates:[v.coordinates.x+delta.x,v.coordinates.y+delta.y],adjacentVertices:NIL,visited:FALSE]];
IF CCW[temp,v,w]THEN{

ELSE done←TRUE;
ENDLOOP;
sausage�VertexToPolygon[sausage,v.coordinates.x,v.coordinates.y];
--put in unswept image of this point; swept image will be added by next loop.

done←FALSE;

FIll in swept boundary

WHILE NOT done DO temp←NEW[Vertex←[coordinates:[v.coordinates.x+delta.x,v.coordinates.y+delta.y],adjacentVertices:NIL,visited:FALSE]];
sausage�VertexToPolygon[sausage,temp.coordinates.x,temp.coordinates.y];
IF CCW[temp,v,w] THEN done←TRUE ELSE[v,w]←StepVertex[v,w,outline];
ENDLOOP;

Remainder of unswept boundary,back to firstv

WHILE v#firstv DO

sausage�VertexToPolygon[sausage,v.coordinates.x,v.coordinates.y];
[v,w]←StepVertex[v,w,outline];
ENDLOOP;
RETURN[sausage];
};

Make an N-gon as per the input parameters

PI: REAL𡤃.14159;

I: CARDINAL;

theta, x, y: RN.RatNum;

gon ← InitVertexHandle[];

FOR I IN [1..N] DO

};

Make a diamond of height scale and width 1/2 scale, upwards or downwards from top as specified by the sign of scale.

topX: RN.RatNum ← top.x;

topY: RN.RatNum ← top.y;

leftX, leftY, bottomY, rightX: RN.RatNum;

scale2: RN.RatNum ← RN.RatNumDivide[ scale, RN.RatNumFromSmallCards[1,2,1] ];

scale4: RN.RatNum ← RN.RatNumDivide[ scale, RN.RatNumFromSmallCards[1,4,1] ];

diamond ← AddVertexToPolygon[InitVertexHandle[], topX, topY, state];

leftX ← RN.RatNumSubtract[ topX, scale4];

leftY ← RN.RatNumSubtract[ topY, scale2];

diamond ← AddVertexToPolygon[diamond, leftX, leftY, state];

bottomY ← RN.RatNumSubtract[ topY, scale];

diamond ← AddVertexToPolygon[diamond, topX, bottomY, state];

rightX ← RN.RatNumAdd[ topX, scale4];

diamond ← AddVertexToPolygon[diamond, rightX, leftY, state];

};

Grow a diamond to the right and upwards. [v, w] is assumed to be an external edge of a structure, and will be interpreted as the lower left edge of the new diamond, i.e. v will be the diamond's left vertex and w its bottom. The diamond height (scale) and width (1/2 scale) will be computed from [v, w].

vHandleLeft: VertexHandle ← v;

vHandleBottom: VertexHandle ← w;

left: Point ← vHandleLeft.coordinates;

bottom: Point ← vHandleBottom.coordinates;

vHandleRight, vHandleTop: VertexHandle;

rightX, rightY: RN.RatNum;

topX, topY: RN.RatNum;

scale2: RN.RatNum ← RN.RatNumSubtract[ left.y, bottom.y ];

scale4: RN.RatNum ← RN.RatNumSubtract[ bottom.x, left.x ];

ahRightToTop, ahRightToBottom, ahTopToLeft, ahTopToRight: AdjacencyHandle;

ahLeftToTop, ahBottomToRight: AdjacencyHandle;

ahlist, ahlistRight, ahlistTop, ahlistLeft, ahlistBottom : AdjacencyHandleList;

leftRegionVisitedValue: BOOL;

Make a VertexHandle for the right vertex

rightX ← RN.RatNumAdd[ bottom.x, scale4];

rightY ← left.y;

vHandleRight ← NEW[ Vertex ← [coordinates: MakePointFromRatNums[rightX, rightY], index: vertexIndex, adjacentVertices: NIL, visited: vHandleLeft.visited] ];

vertexIndex ← vertexIndex + 1;

Make a VertexHandle for the top vertex

topX ← bottom.x;

topY ← RN.RatNumAdd[ left.y, scale2];

vHandleTop ← NEW[ Vertex ← [coordinates: MakePointFromRatNums[topX, topY], index: vertexIndex, adjacentVertices: NIL, visited: vHandleLeft.visited] ];

vertexIndex ← vertexIndex + 1;

Get adjacency lists for left and bottom, and visited value

ahlistLeft ← vHandleLeft.adjacentVertices;

ahlistBottom ← vHandleBottom.adjacentVertices;

leftRegionVisitedValue ← ahlistLeft.first.leftRegionVisited;

Create adjacency lists for right and top

ahRightToTop ← NEW[Adjacency ← [ vertex: vHandleTop, leftState: state, leftRegionVisited: leftRegionVisitedValue, leftRegionExterior: FALSE, intersectionPolygonEdge: FALSE ] ];

ahlist ← CONS[ ahRightToTop, NIL ];

ahRightToBottom← NEW[Adjacency ← [ vertex: vHandleBottom, leftState: NIL, leftRegionVisited: leftRegionVisitedValue, leftRegionExterior: TRUE, intersectionPolygonEdge: FALSE ] ];

ahlistRight ← CONS[ ahRightToBottom, ahlist ];

ahlist.rest ← ahlistRight; -- make circular --

vHandleRight.adjacentVertices ← ahlistRight;

ahTopToLeft ← NEW[Adjacency ← [ vertex: vHandleLeft, leftState: state, leftRegionVisited: leftRegionVisitedValue, leftRegionExterior: FALSE, intersectionPolygonEdge: FALSE ] ];

ahlist ← CONS[ ahTopToLeft, NIL ];

ahTopToRight← NEW[Adjacency ← [ vertex: vHandleRight, leftState: NIL, leftRegionVisited: leftRegionVisitedValue, leftRegionExterior: TRUE, intersectionPolygonEdge: FALSE ] ];

ahlistTop ← CONS[ ahTopToRight, ahlist ];

ahlist.rest ← ahlistTop; -- make circular --

vHandleTop.adjacentVertices ← ahlistTop;

Update adjacency list for left

ahLeftToTop ← NEW[Adjacency ← [ vertex: vHandleTop, leftState: NIL, leftRegionVisited: leftRegionVisitedValue, leftRegionExterior: TRUE, intersectionPolygonEdge: FALSE ] ];

ahlist ← CONS[ ahLeftToTop, NIL ];

WHILE ahlistLeft.rest.first.vertex # vHandleBottom DO ahlistLeft ← ahlistLeft.rest ENDLOOP;

ahlistLeft.rest.first.leftState ← state; -- edge previously on exterior is no longer so

ahlistLeft.rest.first.leftRegionExterior ← FALSE;

ahlistLeft.rest.first.leftRegionVisited ← leftRegionVisitedValue; -- needed?

ahlist.rest ← ahlistLeft.rest;

ahlistLeft.rest ← ahlist;

Update adjacency list for bottom

ahBottomToRight ← NEW[Adjacency ← [ vertex: vHandleRight, leftState: state, leftRegionVisited: leftRegionVisitedValue, leftRegionExterior: FALSE, intersectionPolygonEdge: FALSE ] ];

ahlist ← CONS[ ahBottomToRight, NIL ];

WHILE ahlistBottom.first.vertex # vHandleLeft DO ahlistBottom ← ahlistBottom.rest ENDLOOP;

ahlist.rest ← ahlistBottom.rest;

ahlistBottom.rest ← ahlist;

};

Grow a diamond to the right and downwards. [v, w] is assumed to be an external edge of a structure, and will be interpreted as the lower right edge of the new diamond, i.e. v will be the diamond's bottom vertex and w its right. The diamond height (scale) and width (1/2 scale) will be computed from [v, w].

vHandleBottom: VertexHandle ← v;

vHandleRight: VertexHandle ← w;

bottom: Point ← vHandleBottom.coordinates;

right: Point ← vHandleRight.coordinates;

vHandleTop, vHandleLeft: VertexHandle;

topX, topY: RN.RatNum;

leftX, leftY: RN.RatNum;

scale2: RN.RatNum ← RN.RatNumSubtract[ right.y, bottom.y ];

scale4: RN.RatNum ← RN.RatNumSubtract[ right.x, bottom.x ];

ahTopToLeft, ahTopToRight, ahLeftToBottom, ahLeftToTop: AdjacencyHandle;

ahBottomtoLeft, ahRightToTop: AdjacencyHandle;

ahlist, ahlistRight, ahlistTop, ahlistLeft, ahlistBottom : AdjacencyHandleList;

leftRegionVisitedValue: BOOL;

Make a VertexHandle for the top vertex

topX ← bottom.x;

topY ← RN.RatNumAdd[ right.y, scale2];

vHandleTop ← NEW[ Vertex ← [coordinates: MakePointFromRatNums[topX, topY], index: vertexIndex, adjacentVertices: NIL, visited: vHandleBottom.visited] ];

vertexIndex ← vertexIndex + 1;

Make a VertexHandle for the left vertex

leftX ← RN.RatNumSubtract[ bottom.x, scale4];

leftY ← right.y;

vHandleLeft ← NEW[ Vertex ← [coordinates: MakePointFromRatNums[leftX, leftY], index: vertexIndex, adjacentVertices: NIL, visited: vHandleBottom.visited] ];

vertexIndex ← vertexIndex + 1;

Get adjacency lists for bottom and right, and visited value

ahlistBottom ← vHandleBottom.adjacentVertices;

ahlistRight ← vHandleRight.adjacentVertices;

leftRegionVisitedValue ← ahlistRight.first.leftRegionVisited;

Create adjacency lists for top and left

ahTopToLeft ← NEW[Adjacency ← [ vertex: vHandleLeft, leftState: state, leftRegionVisited: leftRegionVisitedValue, leftRegionExterior: FALSE, intersectionPolygonEdge: FALSE ] ];

ahlist ← CONS[ ahTopToLeft, NIL ];

ahTopToRight← NEW[Adjacency ← [ vertex: vHandleRight, leftState: NIL, leftRegionVisited: leftRegionVisitedValue, leftRegionExterior: TRUE, intersectionPolygonEdge: FALSE ] ];

ahlistTop ← CONS[ ahTopToRight, ahlist ];

ahlist.rest ← ahlistTop; -- make circular --

vHandleRight.adjacentVertices ← ahlistTop;

ahLeftToBottom ← NEW[Adjacency ← [ vertex: vHandleBottom, leftState: state, leftRegionVisited: leftRegionVisitedValue, leftRegionExterior: FALSE, intersectionPolygonEdge: FALSE ] ];

ahlist ← CONS[ ahLeftToBottom, NIL ];

ahLeftToTop← NEW[Adjacency ← [ vertex: vHandleTop, leftState: NIL, leftRegionVisited: leftRegionVisitedValue, leftRegionExterior: TRUE, intersectionPolygonEdge: FALSE ] ];

ahlistLeft ← CONS[ ahLeftToTop, ahlist ];

ahlist.rest ← ahlistLeft; -- make circular --

vHandleTop.adjacentVertices ← ahlistLeft;

Update adjacency list for bottom

ahBottomtoLeft ← NEW[Adjacency ← [ vertex: vHandleLeft, leftState: NIL, leftRegionVisited: leftRegionVisitedValue, leftRegionExterior: TRUE, intersectionPolygonEdge: FALSE ] ];

ahlist ← CONS[ ahBottomtoLeft, NIL ];

WHILE ahlistBottom.rest.first.vertex # vHandleRight DO ahlistBottom ← ahlistBottom.rest ENDLOOP;

ahlistBottom.rest.first.leftState ← state; -- edge previously on exterior is no longer so

ahlistBottom.rest.first.leftRegionExterior ← FALSE;

ahlistBottom.rest.first.leftRegionVisited ← leftRegionVisitedValue; -- needed?

ahlist.rest ← ahlistBottom.rest;

ahlistBottom.rest ← ahlist;

Update adjacency list for right

ahRightToTop ← NEW[Adjacency ← [ vertex: vHandleTop, leftState: state, leftRegionVisited: leftRegionVisitedValue, leftRegionExterior: FALSE, intersectionPolygonEdge: FALSE ] ];

ahlist ← CONS[ ahRightToTop, NIL ];

WHILE ahlistRight.first.vertex # vHandleBottom DO ahlistRight ← ahlistRight.rest ENDLOOP;

ahlist.rest ← ahlistRight.rest;

ahlistRight.rest ← ahlist;

};

size must be at least 2

gridArray: ARRAY [1..20] OF ARRAY [1..20] OF VertexHandle;

scale2: RN.RatNum ← RN.RatNumDivide[ scale, RN.RatNumFromSmallCards[1,2,1] ];

scale4: RN.RatNum ← RN.RatNumDivide[ scale, RN.RatNumFromSmallCards[1,4,1] ];

newVertexX, newVertexY: RN.RatNum;

topX: RN.RatNum ← top.x;

topY: RN.RatNum ← top.y;

ahthistonext, ahthistoprev, ahthistoprev2, ah: AdjacencyHandle;

ahlistnext, ahlistprev, ahlistthis, ahlist, ahlsave: AdjacencyHandleList;

Create vertices

FOR i: CARDINAL IN [1..size] DO

Corner vertices adjacencies (2 per vertex), lower left first

ahthistonext ← NEW[Adjacency ← [ vertex: gridArray[1][2], leftState: state, leftRegionVisited: visitedValue, leftRegionExterior: FALSE, intersectionPolygonEdge: FALSE ] ];

ahlistnext ← CONS[ ahthistonext, NIL ];

ahthistoprev← NEW[Adjacency ← [ vertex: gridArray[2][1], leftState: NIL, leftRegionVisited: visitedValue, leftRegionExterior: TRUE, intersectionPolygonEdge: FALSE ] ];

ahlistthis ← CONS[ ahthistoprev, ahlistnext ];

ahlistnext.rest ← ahlistthis; -- make circular --

gridArray[1][1].adjacentVertices ← ahlistthis;

lower right

ahthistonext ← NEW[Adjacency ← [ vertex: gridArray[2][size], leftState: state, leftRegionVisited: visitedValue, leftRegionExterior: FALSE, intersectionPolygonEdge: FALSE ] ];

ahlistnext ← CONS[ ahthistonext, NIL ];

ahthistoprev← NEW[Adjacency ← [ vertex: gridArray[1][size-1], leftState: NIL, leftRegionVisited: visitedValue, leftRegionExterior: TRUE, intersectionPolygonEdge: FALSE ] ];

ahlistthis ← CONS[ ahthistoprev, ahlistnext ];

ahlistnext.rest ← ahlistthis; -- make circular --

gridArray[1][size].adjacentVertices ← ahlistthis;

upper right

ahthistonext ← NEW[Adjacency ← [ vertex: gridArray[size][size-1], leftState: state, leftRegionVisited: visitedValue, leftRegionExterior: FALSE, intersectionPolygonEdge: FALSE ] ];

ahlistnext ← CONS[ ahthistonext, NIL ];

ahthistoprev← NEW[Adjacency ← [ vertex: gridArray[size-1][size], leftState: NIL, leftRegionVisited: visitedValue, leftRegionExterior: TRUE, intersectionPolygonEdge: FALSE ] ];

ahlistthis ← CONS[ ahthistoprev, ahlistnext ];

ahlistnext.rest ← ahlistthis; -- make circular --

gridArray[size][size].adjacentVertices ← ahlistthis;

upper left

ahthistonext ← NEW[Adjacency ← [ vertex: gridArray[size-1][1], leftState: state, leftRegionVisited: visitedValue, leftRegionExterior: FALSE, intersectionPolygonEdge: FALSE ] ];

ahlistnext ← CONS[ ahthistonext, NIL ];

ahthistoprev← NEW[Adjacency ← [ vertex: gridArray[size][2], leftState: NIL, leftRegionVisited: visitedValue, leftRegionExterior: TRUE, intersectionPolygonEdge: FALSE ] ];

ahlistthis ← CONS[ ahthistoprev, ahlistnext ];

ahlistnext.rest ← ahlistthis; -- make circular --

gridArray[size][1].adjacentVertices ← ahlistthis;

non-corner boundary vertices (3 adjacencies for each); left side first (top to bottom); go backwards (counterclockwise) through adjacencies

FOR i: CARDINAL DECREASING IN [2..size-1] DO

bottom row vertices (left to right)

FOR j: CARDINAL IN [2..size-1] DO

right side vertices (bottom to top)

FOR i: CARDINAL IN [2..size-1] DO

top row vertices (right to left)

FOR j: CARDINAL DECREASING IN [2..size-1] DO

interior vertices (4 adjacencies for each)

FOR i: CARDINAL IN [2..size-1] DO

diamondGrid ← gridArray[1][1];

};