DIRECTORY
RatNums,
ClientStateInfo,
RVHandleUtils;

RVHUtilsImplB: CEDAR PROGRAM
    IMPORTS RatNums, ClientStateInfo, RVHandleUtils
EXPORTS RVHandleUtils =
BEGIN OPEN CSI: ClientStateInfo, RN: RatNums, RVHandleUtils;

AddVertexToPolygon: PUBLIC PROC [vhandlefirst: VertexHandle, x,y: RN.RatNum, state: CSI.State _ CSI.defaultState] RETURNS [VertexHandle] = {
vhandlethis, vhandlelast: VertexHandle;
ahthistofirst, ahthistolast, ahfirsttothis, ahlasttothis, ahthis, ahfirst : AdjacencyHandle;
ahlist, ahlistthis, ahlistfirst, ahlistlast : AdjacencyHandleList;
leftRegionVisitedValue: BOOL;

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)
ELSE vhandlethis.visited _ vhandlefirst.visited;  -- copy visited value
ahlistfirst _ vhandlefirst.adjacentVertices;

IF ahlistfirst = NIL THEN { -- One vertex previously --
ahfirst _ NEW[Adjacency _ [ vertex: vhandlethis,  leftState: state, leftRegionVisited: FALSE, leftRegionExterior: FALSE, intersectionPolygonEdge: FALSE ]  ]; -- set flag fields = FALSE
ahthis_ NEW[Adjacency _ [ vertex: vhandlefirst,  leftState: NIL, leftRegionVisited: FALSE, leftRegionExterior: TRUE, intersectionPolygonEdge: FALSE ]  ];
vhandlethis.adjacentVertices _ CONS[ ahthis, NIL ];
vhandlethis.adjacentVertices.rest _ vhandlethis.adjacentVertices; -- make circular --
vhandlefirst.adjacentVertices _ CONS[ ahfirst, NIL ];
vhandlefirst.adjacentVertices.rest _ vhandlefirst.adjacentVertices; -- make circular --
RETURN [ vhandlefirst ];
};

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;

leftRegionVisitedValue _ ahlistfirst.first.leftRegionVisited;

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 --

ahfirsttothis _ NEW[Adjacency _ [ vertex: vhandlethis,  leftState: NIL, leftRegionVisited: leftRegionVisitedValue, leftRegionExterior: TRUE, intersectionPolygonEdge: FALSE ]  ];
ahlist _ CONS[ ahfirsttothis, ahlistfirst ];
ahlistfirst.rest _ ahlist;  -- make circular; destroy previous circular link --
vhandlefirst.adjacentVertices _ ahlist;

ahlasttothis _ NEW[Adjacency _ [ vertex: vhandlethis,  leftState: state, leftRegionVisited: leftRegionVisitedValue, leftRegionExterior: FALSE , intersectionPolygonEdge: FALSE]  ];
ahlist _ CONS[ ahlasttothis, ahlistlast ];
ahlistlast.rest _ ahlist;  -- make circular; destroy previous circular link --
vhandlelast.adjacentVertices _ ahlist;
}

ELSE { -- Three or more vertices previously --

IF ahlistfirst.first.vertex = vhandlelast THEN ahlistfirst.first.vertex _ vhandlethis ELSE ahlistfirst.rest.first.vertex _ vhandlethis;

IF ahlistlast.first.vertex = vhandlefirst THEN ahlistlast.first.vertex _ vhandlethis ELSE ahlistlast.rest.first.vertex _ vhandlethis;

};

RETURN [ vhandlefirst ];

};
Diamond: PUBLIC PROC [top: Point, scale: RN.RatNum, state: CSI.State] RETURNS [diamond:VertexHandle] ~ {
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];
};
DiamondRightUp: PUBLIC PROC [v, w: VertexHandle, state: CSI.State] ~ {
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;

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;

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;

ahlistLeft _ vHandleLeft.adjacentVertices;
ahlistBottom _ vHandleBottom.adjacentVertices;
leftRegionVisitedValue _ ahlistLeft.first.leftRegionVisited;

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;

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;

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;
};
DiamondGrid: PUBLIC PROC [top: Point, scale: RN.RatNum, state: CSI.State, size: CARDINAL, visitedValue: BOOL] RETURNS [diamondGrid: VertexHandle] = {
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;

FOR i: CARDINAL IN [1..size] DO
FOR j: CARDINAL IN [1..size] DO
newVertexX _  RN.RatNumAdd[
topX,
RN.RatNumAdd[
RN.RatNumMultiply[scale4, RN.RatNumFromSmallCards[MIN[1, i-1], i-1, 1] ],
RN.RatNumMultiply[scale4, RN.RatNumFromSmallCards[MIN[1, j-1], j-1, 1] ]
]
];
newVertexY _  RN.RatNumAdd[
topY,
RN.RatNumSubtract[
RN.RatNumMultiply[scale2, RN.RatNumFromSmallCards[MIN[1, i-1], i-1, 1] ],
RN.RatNumMultiply[scale2, RN.RatNumFromSmallCards[MIN[1, j-1], j-1, 1] ]
]
];
gridArray[i][j] _  NEW[ Vertex _ [coordinates: MakePointFromRatNums[newVertexX, newVertexY], index: vertexIndex, adjacentVertices: NIL, visited: visitedValue] ];
vertexIndex _ vertexIndex + 1;
ENDLOOP;
ENDLOOP;

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;

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;

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;

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;

FOR i: CARDINAL DECREASING IN [2..size-1] DO
ahthistonext _ NEW[Adjacency _ [ vertex: gridArray[i-1][1],  leftState: state, leftRegionVisited: visitedValue, leftRegionExterior: FALSE, intersectionPolygonEdge: FALSE ]  ];
ahlistnext _ CONS[ ahthistonext, NIL ];
ahthistoprev_ NEW[Adjacency _ [ vertex: gridArray[i][2],  leftState: state, leftRegionVisited: visitedValue, leftRegionExterior: FALSE, intersectionPolygonEdge: FALSE ]  ];
ahlistprev _ CONS[ ahthistoprev, ahlistnext ];
ahthistoprev2_ NEW[Adjacency _ [ vertex: gridArray[i+1][1],  leftState: NIL, leftRegionVisited: visitedValue, leftRegionExterior: TRUE, intersectionPolygonEdge: FALSE ]  ];
ahlistthis _ CONS[ ahthistoprev2, ahlistprev ];
ahlistnext.rest _ ahlistthis; -- make circular --
gridArray[i][1].adjacentVertices _ ahlistthis;
ENDLOOP;

FOR j: CARDINAL IN [2..size-1] DO
ahthistonext _ NEW[Adjacency _ [ vertex: gridArray[1][j+1],  leftState: state, leftRegionVisited: visitedValue, leftRegionExterior: FALSE, intersectionPolygonEdge: FALSE ]  ];
ahlistnext _ CONS[ ahthistonext, NIL ];
ahthistoprev_ NEW[Adjacency _ [ vertex: gridArray[2][j],  leftState: state, leftRegionVisited: visitedValue, leftRegionExterior: FALSE, intersectionPolygonEdge: FALSE ]  ];
ahlistprev _ CONS[ ahthistoprev, ahlistnext ];
ahthistoprev2_ NEW[Adjacency _ [ vertex: gridArray[1][j-1],  leftState: NIL, leftRegionVisited: visitedValue, leftRegionExterior: TRUE, intersectionPolygonEdge: FALSE ]  ];
ahlistthis _ CONS[ ahthistoprev2, ahlistprev ];
ahlistnext.rest _ ahlistthis; -- make circular --
gridArray[1][j].adjacentVertices _ ahlistthis;
ENDLOOP;

FOR i: CARDINAL IN [2..size-1] DO
ahthistonext _ NEW[Adjacency _ [ vertex: gridArray[i+1][size],  leftState: state, leftRegionVisited: visitedValue, leftRegionExterior: FALSE, intersectionPolygonEdge: FALSE ]  ];
ahlistnext _ CONS[ ahthistonext, NIL ];
ahthistoprev_ NEW[Adjacency _ [ vertex: gridArray[i][size-1],  leftState: state, leftRegionVisited: visitedValue, leftRegionExterior: FALSE, intersectionPolygonEdge: FALSE ]  ];
ahlistprev _ CONS[ ahthistoprev, ahlistnext ];
ahthistoprev2_ NEW[Adjacency _ [ vertex: gridArray[i-1][size],  leftState: NIL, leftRegionVisited: visitedValue, leftRegionExterior: TRUE, intersectionPolygonEdge: FALSE ]  ];
ahlistthis _ CONS[ ahthistoprev2, ahlistprev ];
ahlistnext.rest _ ahlistthis; -- make circular --
gridArray[i][size].adjacentVertices _ ahlistthis;
ENDLOOP;

FOR j: CARDINAL DECREASING IN [2..size-1] DO
ahthistonext _ NEW[Adjacency _ [ vertex: gridArray[size][j-1],  leftState: state, leftRegionVisited: visitedValue, leftRegionExterior: FALSE, intersectionPolygonEdge: FALSE ]  ];
ahlistnext _ CONS[ ahthistonext, NIL ];
ahthistoprev_ NEW[Adjacency _ [ vertex: gridArray[size-1][j],  leftState: state, leftRegionVisited: visitedValue, leftRegionExterior: FALSE, intersectionPolygonEdge: FALSE ]  ];
ahlistprev _ CONS[ ahthistoprev, ahlistnext ];
ahthistoprev2_ NEW[Adjacency _ [ vertex: gridArray[size][j+1],  leftState: NIL, leftRegionVisited: visitedValue, leftRegionExterior: TRUE, intersectionPolygonEdge: FALSE ]  ];
ahlistthis _ CONS[ ahthistoprev2, ahlistprev ];
ahlistnext.rest _ ahlistthis; -- make circular --
gridArray[size][j].adjacentVertices _ ahlistthis;
ENDLOOP;

FOR i: CARDINAL IN [2..size-1] DO
FOR j: CARDINAL IN [2..size-1] DO
ah _ NEW[ Adjacency _ [vertex: gridArray[i+1][j],
leftState: state,
leftRegionVisited : visitedValue,
leftRegionExterior: FALSE,
intersectionPolygonEdge: FALSE]
];
ahlist _ CONS[ ah, NIL ];
ahlsave _ ahlist;  -- save pointer to last list cell for making circular list

ah _ NEW[ Adjacency _ [vertex: gridArray[i][j-1],
leftState: state,
leftRegionVisited : visitedValue,
leftRegionExterior: FALSE,
intersectionPolygonEdge: FALSE]
];
ahlist _ CONS[ ah, ahlist ];

ah _ NEW[ Adjacency _ [vertex: gridArray[i-1][j],
leftState: state,
leftRegionVisited : visitedValue,
leftRegionExterior: FALSE,
intersectionPolygonEdge: FALSE]
];
ahlist _ CONS[ ah, ahlist ];

ah _ NEW[ Adjacency _ [vertex: gridArray[i][j+1],
leftState: state,
leftRegionVisited : visitedValue,
leftRegionExterior: FALSE,
intersectionPolygonEdge: FALSE]
];
ahlist _ CONS[ ah, ahlist ];

ahlsave.rest _ ahlist;  -- make list of adjacencies circular
gridArray[i][j].adjacentVertices _ ahlist;

ENDLOOP;
ENDLOOP;

diamondGrid _ gridArray[1][1];
};


END.


'ºRVHUtilsImplB.mesa
Last Edited by: Arnon, June 20, 1985 4:44:33 pm PDT

RealFns USING [Sin, Cos],
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.
Make a VertexHandle for the new vertex
Find vhandlelast (Note that we know at this point that ahlistfirst # NIL)
Get value of visited field (all vertices in the polygon must have same field value)
Create AdjacencyHandleList for the new vertex
Update AdjacencyHandleList of first vertex (note that it had length one) 
Update AdjacencyHandleList of previous last vertex  (note that it had length one) --
Update AdjacencyHandleList of first vertex in vertexhandlelist (have it point to the new vertex; delete the edge to previous last vertex). Note that vhandlefirst and vhandlelast, like all vertices on the polygon, had exactly two adjacencies previously
Update AdjacencyHandleList of last vertex in vertexhandlelist (have it point to the new vertex; delete the edge to first vertex)
ExpandNontrivialPolygon: PROC[v, w:VertexHandle, point: Point] RETURNS[y, z: VertexHandle] = {
 [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, 
leftState: vTow.leftState,
leftRegionVisited : vTow.leftRegionVisited,
leftRegionExterior : vTow.leftRegionExterior ] -- should be FALSE 
];
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, 
leftState: wTov.leftState,
leftRegionVisited : wTov.leftRegionVisited,
leftRegionExterior : wTov.leftRegionExterior ] -- should be TRUE 
];
x.adjacentVertices _ CONS[ ah, x.adjacentVertices ];

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

RETURN[ x, w];
};
Sausify: PUBLIC PROC [brush:VertexHandle, start, end:Point] RETURNS[sausage:VertexHandle]={
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_brush;
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{
sausage_AddVertexToPolygon[sausage,v.coordinates.x,v.coordinates.y];
[v,w]_StepVertex[v,w,outline];
}
ELSE done_TRUE;
ENDLOOP;
sausage_AddVertexToPolygon[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_AddVertexToPolygon[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_AddVertexToPolygon[sausage,v.coordinates.x,v.coordinates.y];
[v,w]_StepVertex[v,w,outline];
ENDLOOP;
RETURN[sausage];
};
Ngon: PUBLIC PROC [N: CARDINAL, xCenter, yCenter, radius: RN.RatNum] RETURNS [gon:VertexHandle] ~ {
Make an N-gon as per the input parameters
PI: REAL_3.14159;
I: CARDINAL;
theta, x, y: RN.RatNum;
gon _ InitVertexHandle[];
FOR I IN [1..N] DO
theta_(I*2.0*PI)/N;
x_xCenter+radius*RealFns.Cos[theta];
y_yCenter+radius*RealFns.Sin[theta];
gon_AddVertexToPolygon[gon,x,y];
ENDLOOP;
};
Make a diamond of height scale and width 1/2 scale, upwards or downwards from top as specified by the sign of scale.
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].
Make a VertexHandle for the right vertex
Make a VertexHandle for the top vertex
Get adjacency lists for left and bottom, and visited value
Create adjacency lists for right and top
Update adjacency list for left
Update adjacency list for bottom
DiamondLeftUp: PUBLIC PROC [v, w: VertexHandle, state: CSI.State] ~ {
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
Create vertices
Corner vertices adjacencies (2 per vertex), lower left first
lower right
upper right
upper left
non-corner boundary vertices (3 adjacencies for each); left side first (top to bottom); go backwards (counterclockwise) through adjacencies
bottom row vertices (left to right)
right side vertices (bottom to top)
top row vertices (right to left)
interior vertices (4 adjacencies for each)

�Êø˜š
œ™J™3J™—š
Ïk	˜	Jšœ�œ™Jš
œ˜Jš
œ˜Jš
œ˜J˜—InamešÏn
œ�œ
�˜šœ�œ(˜3Jš�œ˜—Jš�œ
�œ
�œ�œ˜<J˜šžœ�œ
�œ#�œ�œ	�œ�œ˜Œ
Jš
œð™ðJ™Ÿ
Jš
œ'˜'J˜\J˜BJšœ�œ
˜J˜Jš
œ&™&Jšœ�œ[�œ�œ˜ƒ
Jš
œ˜J˜š
�œ�œ
�œ
�œ�
Ïc,˜\Jš�œ.Ÿ˜G—Jš
œ,˜,J˜š�œ�œ
�œŸ˜7Jš
œ
�œJ�œ�œ�œŸ˜¸
Jšœ�œ1�œ�œ�œ�œ˜™
Jšœ�œ
�œ˜3JšœBŸ˜UJšœ �œ�œ˜5JšœDŸ˜WJš�œ˜J˜J˜—JšŸ7œŸ™IJš�œ �œ(�œ5Ÿ”œŸœŸP˜ŽJš
œ*˜*J˜Jš
œS™SJš
œ=˜=J˜Jš
œ-™-Jšœ�œw�œ�œ˜µ
Jšœ	�œ�œ˜$Jšœ�œt�œ�œ˜¯
Jšœ
�œ˜*JšœŸ˜-š
œ*˜*J˜—Jš�œ �œŸ˜F˜Jš
œI™IJšœ�œt�œ�œ˜±
Jšœ	�œ˜,JšœŸ3˜OJš
œ'˜'J˜Jš
œT™TJšœ�œv�œ�œ˜³
Jšœ	�œ˜*JšœŸ3˜NJš
œ&˜&J˜
J˜—š�œŸ'˜.J˜Jš
Ϟ
™û
Jš�œ(�œ(�œ-˜‡
J˜Jš
œ€
™€
Jš�œ(�œ'�œ,˜…
J˜J˜J˜—š�œ˜J˜—J˜—šžœ�œ"�œ™^J•commentTRUEš
œÂ™ÂJ™J™J™J™)Jšœ�œ2�œ™@J™J™9J™%J™Jš
œA™AJ™J™Jš
œ6™6J™J™J™šœ�œ™"Jš
œ™Jš
œ+™+Jšœ/Ÿ™BJš
œ™—Jšœ�œ™4JšœŸ:™YJ™J™šœ�œ™"Jš
œ™Jš
œ+™+Jšœ/Ÿ™AJš
œ™—Jšœ�œ™4J™Jšœ$Ÿ$™HJ™Jš�œ™Jš
œ™—šžœ�œ
�œ(�œ™[Jš
œ¹
™¹
Jšœ�œ
�œ
™Jš
œ*™*Jš
œ™Jšœ�œ
�œ
™Jš
œ™Jš
œ(™(Jš
œ™Jš
œ™J™Jš
œ6™6Jš�œ
�œ�œ�œX�œ	�œ�œ
�œ�œ�œ
�œ�œ�œ
™è
J™Jš
œ;™;š�œ
�œ�œ�œX�œ	�œ�œ
�œ
�œ
™œ
Jš
œe™e—Jš	�œ�œ�œGŸ%œ
Ÿ'™«
Jšœ�œ
™J™Jš
œ™Jš�œ
�œ�œ�œX�œ	�œO�œ
�œ�œ�œ
�œ�œ
™�J™Jš
œ,™,Jš�œ
�™Jšœd�œ�œ
™€
—šžœ�œ
�œ�	œ�œ�œ™cJ™)Jš�œ
�œ	™Jšœ�	œ
™Jšœ�œ™J™š�œ�œ�™Jšœ
�œ™Jš
œ$™$Jš
œ$™$Jš
œ ™ Jš�œ
™—Jš
œ™—šžœ�œ
�œ�œ�œ�œ˜hJ™tJšœ�œ˜Jšœ�œ˜Jšœ�œ˜)Jšœ�œ
�œ�œ˜MJšœ�œ
�œ�œ˜MJš
œD˜DJšœžœ˜*Jšœžœ˜)Jš
œ;˜;Jšœ
žœ˜*Jš
œ<˜<Jšœž	œ˜%Jš
œ<˜<Jš
œ˜—šžœ�œ
�œ�œ˜FJ™¯Jš
œ˜Jš
œ ˜ Jš
œ&˜&Jš
œ*˜*Jš
œ'˜'Jšœ�œ˜Jšœ�œ˜Jšœ�œ
�œ$˜:Jšœ�œ
�œ$˜:J˜JJ˜.J˜OJšœ�œ
˜J˜Jš
œ(™(Jšœ	�œ˜)Jš
œ˜Jšœ�œe�œ"˜œ
Jš
œ˜J˜Jš
œ&™&Jš
œ˜Jšœ�œ˜%Jšœ
�œa�œ"˜–
Jš
œ˜J˜Jš
œ:™:Jš
œ*˜*Jš
œ.˜.Jš
œ<˜<J˜Jš
œ(™(Jšœ�œu�œ�œ˜²
Jšœ	�œ�œ˜#Jšœ�œv�œ�œ˜´
Jšœ�œ˜.JšœŸ˜.Jš
œ,˜,J˜Jšœ�œv�œ�œ˜²
Jšœ	�œ�œ˜"Jšœ�œu�œ�œ˜°
Jšœ�œ˜)JšœŸ˜,Jš
œ(˜(J˜Jš
œ™Jšœ�œs�œ�œ˜®
Jšœ	�œ�œ˜"Jš�œ.�œ�œ
˜[Jšœ*Ÿ.˜XJšœ,�œ
˜2JšœDŸ
˜NJš
œ˜Jš
œ˜J˜Jš
œ ™ Jšœ�œw�œ�œ˜·
Jšœ	�œ�œ˜&Jš�œ)�œ"�œ
˜ZJš
œ ˜ Jš
œ˜Jš
œ˜—šž
œ�œ
�œ�œ™EJ™³Jš
œ ™ Jš
œ™Jš
œ*™*Jš
œ(™(Jš
œ&™&Jšœ�œ™Jšœ
�œ™Jšœ�œ
�œ
žœ™;Jšœ�œ
�œ
žœ™;J™HJ™.J™OJšœ�œ
™J™Jš
œ&™&Jš
œ™Jšœ�œ
žœ™&Jšœ
�œa�œ$™˜
Jš
œ™J™Jš
œ'™'Jšœ�œ
žœ™-Jš
œ™Jšœ�œc�œ$™›
Jš
œ™J™Jš
œ;™;Jš
œ.™.Jš
œ,™,Jš
œ=™=J™Jš
œ'™'Jšœ�œv�œ�œ™²
Jšœ	�œ�œ™"Jšœ�œu�œ�œ™°
Jšœ�œ™)JšœŸ™,Jš
œ*™*J™Jšœ�œx�œ�œ™·
Jšœ	�œ�œ™%Jšœ
�œs�œ�œ™­
Jšœ
�œ™)JšœŸ™-Jš
œ)™)J™Jš
œ ™ Jšœ�œt�œ�œ™²
Jšœ	�œ�œ™%Jš�œ/�œ"�œ
™`Jšœ,Ÿ.™ZJšœ.�œ
™4JšœFŸ
™PJš
œ ™ Jš
œ™J™Jš
œ™Jšœ�œu�œ�œ™²
Jšœ	�œ�œ™#Jš�œ*�œ �œ
™YJš
œ™Jš
œ™Jš
œ™—šžœ�œ
�œ�œ�œ�œ�œ�œ ˜•
Jš
œ™Jš	œ�œ	�œ
�œ	�œ˜:Jšœ�œ
�œ�œ˜MJšœ�œ
�œ�œ˜MJšœ�œ˜"Jšœ�œ˜Jšœ�œ˜Jš
œ?˜?Jš
œI˜IJ˜J™
codeš�œ�œ
�œ�˜š�œ�œ
�œ�˜šœ�œ˜Lš
œ˜š�œ˜
Lš�œ�œ�œ˜ILš�œ�œ�œ˜HLš
œ
˜
—L˜—šœ�œ˜Lš
œ˜š�œ˜Lš�œ�œ�œ˜ILš�œ�œ�œ˜HLš
œ
˜
—L˜—Lšœ�œm�œ˜¡
Jš
œ˜Lš�œ
˜—Lš�œ
˜—J˜Jš
œ<™<Jšœ�œp�œ�œ˜­
Jšœ
�œ�œ˜'Jšœ�œn�œ�œ˜©
Jšœ
�œ˜.JšœŸ˜1Jš
œ.˜.J˜Jš
œ™Jšœ�œs�œ�œ˜°
Jšœ
�œ�œ˜'Jšœ�œs�œ�œ˜®
Jšœ
�œ˜.JšœŸ˜1Jš
œ1˜1J˜Jš
œ™Jšœ�œx�œ�œ˜µ
Jšœ
�œ�œ˜'Jšœ�œv�œ�œ˜±
Jšœ
�œ˜.JšœŸ˜1Jš
œ4˜4J˜Jš
œ
™
Jšœ�œu�œ�œ˜²
Jšœ
�œ�œ˜'Jšœ�œq�œ�œ˜¬
Jšœ
�œ˜.JšœŸ˜1Jš
œ1˜1J˜Jš
œ‹
™‹
š	�œ�œ
�
œ
�œ
�˜,Jšœ�œr�œ�œ˜¯
Jšœ
�œ�œ˜'Jšœ�œp�œ�œ˜¬
Jšœ
�œ˜.Jšœ�œp�œ�œ˜¬
Jšœ
�œ˜/JšœŸ˜1Jš
œ.˜.Jš�œ
˜—J˜Jš
œ#™#š�œ�œ
�œ
�˜!Jšœ�œr�œ�œ˜¯
Jšœ
�œ�œ˜'Jšœ�œp�œ�œ˜¬
Jšœ
�œ˜.Jšœ�œp�œ�œ˜¬
Jšœ
�œ˜/JšœŸ˜1Jš
œ.˜.Jš�œ
˜J˜—Jš
œ#™#š�œ�œ
�œ
�˜!Jšœ�œu�œ�œ˜²
Jšœ
�œ�œ˜'Jšœ�œu�œ�œ˜±
Jšœ
�œ˜.Jšœ�œs�œ�œ˜¯
Jšœ
�œ˜/JšœŸ˜1Jš
œ1˜1Jš�œ
˜—J˜Jš
œ ™ š	�œ�œ
�
œ
�œ
�˜,Jšœ�œu�œ�œ˜²
Jšœ
�œ�œ˜'Jšœ�œu�œ�œ˜±
Jšœ
�œ˜.Jšœ�œs�œ�œ˜¯
Jšœ
�œ˜/JšœŸ˜1Jš
œ1˜1Jš�œ
˜—J˜Jš
œ*™*š�œ�œ
�œ
�˜!š�œ�œ
�œ
�˜!šœ�œ)˜1Jš
œ˜Jš
œ!˜!Jšœ�œ
˜Jšœ�œ
˜Jš
œ˜—Jšœ	�œ�œ˜JšœŸ:˜MJ˜šœ�œ)˜1Jš
œ˜Jš
œ!˜!Jšœ�œ
˜Jšœ�œ
˜Jš
œ˜—Jšœ	�œ˜J˜šœ�œ)˜1Jš
œ˜Jš
œ!˜!Jšœ�œ
˜Jšœ�œ
˜Jš
œ˜—Jšœ	�œ˜J˜šœ�œ)˜1Jš
œ˜Jš
œ!˜!Jšœ�œ
˜Jšœ�œ
˜Jš
œ˜—Jšœ	�œ˜J˜JšœŸ$˜<Jš
œ*˜*J˜Jš�œ
˜—Jš�œ
˜—J˜Jš
œ˜˜J˜——J˜Jš�œ
˜˜J™—J˜—…—=ªx\