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] = {
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 => 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] = {
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] = {
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] ~ {
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;
Compactify: PROC [j: CARDINAL]  ~ {
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];
};

n _ 0;
WHILE L # NIL DO
n _ n + 1;
pointArray[n] _ [ L.first.x, L.first.y ];
L _ L.rest;
ENDLOOP;

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

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;

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;

IF flip THEN {
tempPoint _ pointArray[J];
pointArray[J] _ pointArray[J+1];
pointArray[J+1] _ tempPoint;
};
ENDLOOP;
ENDLOOP;



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;
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] = {
RETURN[ RN.RatNumEqual[p.x, q.x] AND RN.RatNumEqual[ p.y, q.y ] ];
};
VerticalEdge: PUBLIC PROC[ p, q: Point ] RETURNS[BOOLEAN] = {
RETURN[ RN.RatNumEqual[p.x, q.x] ];
};
DistanceSquare: PUBLIC PROC[ p, q: Point ] RETURNS [d: RN.RatNum] = {
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 ] = {
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] = {
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] = {
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] = {
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] = {
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] = {
slope1, slope2, intercept1, intercept2, xIntersect, yIntersect : RN.RatNum;
vertical1, vertical2: BOOL _ FALSE;
start1end1start2, start1end1end2: PointDirectedEdgeRelation;

origin: Point _ MakePointFromRatNums[RN.MakeRatNumZero[], RN.MakeRatNumZero[] ]; 
point: Point;

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] ~ {
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] ~ {
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] ~ {
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]= {
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] = {
vertexhandle: VertexHandle _ NIL;
RETURN[vertexhandle];
};
MakePointFromRatNums: PUBLIC PROC[x1, y1: RN.RatNum] RETURNS [p: Point] = {
p _ [x: x1, y: y1 ];
RETURN[ p ];
};
MakePointFromReals: PUBLIC PROC[x1, y1: REAL] RETURNS [p: 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 ];
};

GetPolygonState: PUBLIC PROC [v, w: VertexHandle] RETURNS [state: CSI.State] = {
vTow, wTov: AdjacencyHandle;
[ vTow, wTov ] _ FindAdjacency[ v, w ];
state _ vTow.leftState;
};
PolygonExtractor: PUBLIC PROC [v, w: VertexHandle] RETURNS [ImagerPolygonAndStateList] = {
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];

state _ GetPolygonState[v, w]; -- only need to set state once

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

[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]  = {
vTow, wTov: AdjacencyHandle;
firstv: VertexHandle _ v;
outline: BOOL _ FALSE;

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

[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]  ~ {
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] = {
vAdjList: AdjacencyHandleList _ v.adjacentVertices;
lastVertex, nextVertex:  VertexHandle;
nextAdj: AdjacencyHandle;
stateRope: Rope.ROPE;
done: BOOL;

v.visited _ visitedValue; -- record that we've visited this 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]] ];

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[']];

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] ~ {

vHList: VertexHandleList;
scratchVHL: VertexHandleList;
scratchIOVHL: IOVertexHandleList;
vHandle: VertexHandle;
adjacentVertex: VertexHandle;
aHList, aHListLast: AdjacencyHandleList;
aHandle : AdjacencyHandle;
ioAHList: IOAdjacencyHandleList;
ioAHandle: IOAdjacencyHandle;

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;

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] ~ {
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] ~ {
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] ~ {
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;

v.visited _ visitedValue; -- record that we've visited this vertex

vDist _ DistanceSquare[v.coordinates, test];
IF RN.RatNumLess[ vDist, currentBestDist] THEN {
currentBest _ v;
currentBestDist _ vDist
};

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] = {
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.

!¦RVHandleUtilsImpl.mesa
Last Edited by: Arnon, June 20, 1985 4:37:28 pm PDT

We assume that the vertices are given to us in counterclockwise order (with respect to figure interior) along the outline of the figure.
ONLINE => ERROR; -- 9/19/85 unsure whether to allow a 180deg angle
[v,w] is a counterclockwise oriented edge on the polygon
[v,w] is a counterclockwise oriented edge on the polygon, must have at least 2 (3?) vertices.
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.
in, out: IO.STREAM; -- viewer stream for debugging verbosity
Compactify pointArray to remove the jth element
[in, out] _ ViewerIO.CreateViewerStreams[IO.PutFR["ConvexHull Log"]];

Load into array
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]] ];
Step 1 - Find interior point P - search for noncollinear set of three points, compute com of that triangle
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
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?
out.PutF["\n I, J, flip =  %g , %g, %g", IO.card[I],IO.card[J], IO.bool[flip] ]; 
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

Return untranslated points of hull.
Test whether points p and q are the same.
Test whether points p and q are the same.
Compute square of distance between two points.
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. 
*** 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).
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).
[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.
Compute the exclusive or of two BOOLEANs
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].

Set up dummy intersection 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.
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).
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).
[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).
 v and w are adjacent vertices. Search and find the AdjacencyHandles with each points to the other.
Create an empty 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_10000.0 ELSE slope _ -10000.0
}
ELSE
slope_(p2.y-p1.y)/(p2.x-p1.x);
RETURN[slope];
};
Bundle up two real numbers as an point
Bundle up two real numbers as an point
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];
};

[v, w] is a (counterclockwise) directed edge of an internal polygon. Obtain the polygon's state.

[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.
Extract state
Set leftRegionVisited fields of edges of this polygon, and build trajectory
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] 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.
Set leftRegionVisited fields of edges of this polygon, and build trajectory
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.
Dump a VertexHandle to a file. Does Depth First Search.

Assumes two or more vertices
Record that we've visited v
Write v
Write adjacencies of v
Recursive calls for adjacencies of v
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.
Create initial list of VertexHandles containing vertex indices
Fill in links to adjacent vertices
Search vHList for the element whose index is key;
[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.  
Find vertex closest to test point
Record that we've visited v
Compute distance to test point
Recursive calls for adjacencies of v
[v, w] is a (counterclockwise) directed edge of an internal polygon. Its state is set. setLRE controls whether leftRegionExterior fields are set to FALSE.


�Ê.͘™J™3J™—š
Ïk	˜	Jšœ�œ�œ˜Jš�œ
�œ˜Jš�œ
�œ�œtÏc˜¢
Jšœ�œ�œ˜Jšœ�œ˜$Jš
œ˜Jš
œ˜Jš
œ˜Jšœ	ž˜J˜—
namešœ�œ
�˜ Kš�œ6˜=Jš�œ˜—Jš�œ
�œ
�œ�œ˜<J˜Jšœ
�œ
�œž˜<J˜šÏnœ�œ
�œ.�œ�œ�œ�œ˜pJ•commentTRUE™ˆ
Jš
œ˜
codeš�œB�˜LLš�œ�œ
�œ˜Lš�
œ�œ
˜Lš�œ�œž1˜BLš�œ
˜—š�œE�˜OLš�œ�œ
�œ˜Lš�
œ�œ
˜Lš�œ�œž1˜BLš�œ
˜—Jš
œ7˜7š�œ�˜š�œ<�˜FLš�œ�œ
�œ˜Lš�
œ�œ
˜Lš�œ�œž1™BLš�œ�œž˜*Lš�œ
˜—Jš
œ2˜2Jš�œ
˜—Jš�œ
�œ˜
J˜—š
Ÿœ�œ
�œ �œ�œ˜SJ–TRUE™8Jš
œ˜Jšœ�œ˜ Jšœ�œ˜ Jšœ�œ˜Jšœ�œ˜š�œ�˜Jšœ�œ#˜*Jšœ�œ#˜+J˜
J˜$Jš�œ
˜—Jšœ�œ ˜)Jš�œ�œ�œ ˜OJ˜—šŸ
œ�œ
�œ �œ�œ�œ˜SJ–TRUE™]Jš
œ˜Jš
œ˜Jš
œ˜J˜Jš
�œ�œ�œ
�œ
�œ˜$š�œ<�œ
ž˜[Lš�œ�œ
�œ˜Lš�
œ�œ
˜Lš�œ�œž1˜BLš�œ
˜—Jšœ.ž˜:š�œ�˜š�œ<�œ
ž˜[Lš�œ�œ
�œ˜Lš�
œ�œ
˜Lš�œ�œž1˜BLš�œ
˜—J˜-Jš�œ
˜—Jš�œ
�œ˜
J˜—šŸ
œ�œ�œ˜DLš
œ™L™ÄJšœ�œ˜Jšœ�œ˜Jšœ�œ
˜Jšœ
�œ
˜Jšœ�œ˜J˜Jšœ�œ�œ	�œ˜*Jš
œ˜J˜Jšœ�œ
˜Jšœ	�œ
�œž(™<šŸ
œ�œ�œ˜#Lš
œ/™/L˜š�œ�œ
�œ�˜Lš
œ"˜"Lš�œ
˜—L˜—š
Ÿœ�œ�œ�œ�œ˜3Jš�œ�œ�œ
�œ�œ
�œ�œ˜3L˜—L˜Jšœ)�œ™EL™Jš
œ™L˜š�œ�œ
�˜J˜
Jš
œ)˜)Lšœ,�œ
�œ�œ"�œ�œ�œ�œ"�œ�œ™±
J˜Jš�œ
˜—J˜Jš
œj™jL˜š�œ
�˜Jš�œ@�œ
�œ
�œ
˜SJ˜Jš�œ
˜—Jš	�œ@�œ
�œ
�œž-˜‚
Jš
œ˜Jš
œ˜Jšœ�œ%˜/Jšœ	�œ&˜1Jšœ�œ%˜/Jšœ	�œ%˜0Jšœ�œ ˜)Jšœ�œ"�œ!˜WLšœ/�œ
�œ�œ�œ�œ�œ�œ�œ�œ™¬
J˜J™5š�œ�œ�˜Jšœ�œ3�œ2˜}Jš�œ
˜—J˜Lš
œZ™ZLšž"œ	ž%™Pš�œ�
œ
�˜š�œ�œ
�œ�˜š�œ
�œ �œ�˜Bšœ�œ
�œ"�œ�˜Rš
œ˜šœ�œ �œ ˜[J˜
—Jšœ�œ"�œ#˜Y—š
œ˜Jšœ�œ
˜
—šœ�œ
�œ$�˜=Lš�œ�œž(˜=Lš�œ�œž$˜;Lš�œ�œ
˜—Lš�œ�œ
˜—šœ�œ
�œ"�œ�˜Oš
œ˜Jšœ�œ
˜—š
œ˜šœ�œ �œ ˜[J˜
—Jšœ�œ"�œ#˜Y—Lšœ�œž5˜NLš�œ�œ
˜—šœ�œ
�œ �œ�˜OLšœ�œž(˜Dšœž˜š�œ
�œ"�œ�˜Dš
œ˜Jšœ�œ
˜—š
œ˜Jšœ�œ
˜
—šœ�œ
�œ$�˜=Lš�œ�œž(˜=Lš�œ�œž"˜9Lš�œ�œ
˜—Lš�œ�œ
˜——Lšœ�œ
ž"˜4Lš�œ�œ
˜—Lš�œ�œ
˜—Lšœ)�œ	�œ™QL˜š�œ�œ˜Jš
œ˜Jš
œ ˜ Jš
œ˜J˜—Jš�œ
˜—Jš�œ
˜—J˜Lš
œ ™ š�œ�œ�™Lšœ9�œ
�œ�œ"�œ�œ�œ�œ"�œ�œ�œ�œ �œ%™žJš�œ
™—J˜J˜Jš
œ1™1J˜Jšœžq˜„
š�œ�œ
�œ�˜#š�œ?�˜FJšœž(˜BLš�œ
˜—š�œ^�œ
�˜qLš
œ˜Lš
œ˜Lš�œ
˜—Lš
œ˜Lš�œ
˜—J™Jš
œ#™#Jšœ�œ
˜š�œ�
œ�˜Jšœ�œ�œ.�œ3˜wJš�œ
˜—L˜—š
Ÿ
œ�œ
�œ�œ�œ˜:Jš
œ)™)Jš�œ�œ�œ
�œ˜BJ˜—š
Ÿœ�œ
�œ�œ
�œ˜=Jš
œ)™)Jš�œ�œ˜#J˜—š
Ÿœ�œ
�œ�œ�œ˜EJš
œ.™.Jšœ�œ˜Jšœ	�œ˜&Jšœ	�œ˜&š�œ�œ˜Jš�œ#�œ!˜HJš
œ˜—Jš
œ˜—š
Ÿ
œ�œ
�œ�œ�œ˜]Jšœ•
�
œ™ª
š�œ�œ
˜Lš�œ�œ
�œ�œ�œ
�œ�
œ˜J—š�œ˜šœ
�œ�œ˜/š�œ˜Jš�œ$˜&Jš�œ"˜$Jš
œ˜—š�œ˜Jš�œ$˜&Jš�œ"˜$Jš
œ˜—Jš
œ˜—š�œ
�˜Lšœ�œ�œ˜!Lšœ�œ�œ˜Lšœ�œ�
œ˜#Lš�œ
˜—L˜—L˜L˜—š
Ÿœ�œ
�œ�œ�
œ˜pJšœ8�œ)�œ)�=™Ì
Jš
œ%˜%Jšœ�œ
˜Jš
œ4˜4š�œ�˜Lš�
œ�œ�
œ˜#Lš�œ�œ�œ˜%š�œ˜Jš�œ�œ
�œ�
œ˜5Jš�œ�œ
�œ�œ˜1Jšœ�œJ˜XJšœ
�œH˜WJš
�œ�œ�œ
�œ
�œ˜9Jš�œ
�œI�œ
�œ
�œ�œ
�œ
�œ˜}J˜—Lš�œ
˜—J˜J˜—š
Ÿœ�œ
�œ6�œ�œ˜}Jš	žJœ&žaœ
žœžEœ
ž™ÃJš
œg˜gš�œ�˜Lš�œ�œ
˜'Lš�
œ�œ
˜!Lš�œ�œ
˜0Lš�œ�œ
˜'Lš�œ�œ
˜'Lš�œ�œ
˜(š�
œ�
˜Jš
œK˜Kš�œ�˜Lš�œ�œ
˜(Lš�œ�œ
˜/Lš�œ�œ
˜&Lš�œ�œ
˜&Lš�
œ�˜&š�œ˜Lš
œU˜Uš�œ�˜Lš�œ�œ
�œ˜&Lš�
œ�œ
�œ˜%Lš�œ�œ
�œ˜'Lš�œ
˜—L˜—Lš�œ�œž˜/L˜——Lš�œ
˜—L˜J˜—š
Ÿœ�œ
�œ9�œ�œ6˜�
J–TRUE™Ù
Jš
œn˜nš	�œ�œ
�œ�
œ
�˜TJ˜%Jš
œY˜YJš�œ
˜—Jš�œ˜$J˜—šŸœ�œ
�œ�œ�œ
�œ˜4Jš
œ(™(Jš
�œ�œ�œ
�œ
�œ˜ Jš
�œ�œ�œ
�œ
�œ˜Jš�œ
�œ˜Jš
œ˜J˜—š
Ÿœ�œ
�œL�œ
�œ˜}Jšœ�œ�œ
˜š�œ�œ
�˜Lš�œ
�œ�œ
˜L˜Lš�œ
˜—Lš�œ˜
L˜—š
Ÿœ�œ
�œ%�œ,�œ˜”
Jš
œ÷™÷J™JšœA�œ˜KJšœ�œ�œ
˜#Jš
œ<˜<J˜Jš
œ™Jšœ%�œ�œ˜QJ˜
J˜Jš
œŠ
™Š
Jš�œ�œ�œ�œ˜IJš�œ�œ�œ�œ˜IJš	�œ�œ
�œ
�œžT˜sJ˜Jš
œA˜AJš
œ=˜=J˜š�œ�˜š�œ�œ�˜5š�œž‚
˜ 
Jš
œ'˜'Jš
œ'˜'Jš�œ�œ�œ
�œ�œ�œ˜Jš�œ
�œ�œ
�œ˜/Jš�œ$˜&Jš�œ#˜%J˜—š�œ
�œ�œ
�œ˜/Jš�œ$˜&Jš�œ#˜%J˜—Jš
�œ
�œ�œ�œ�œ&˜hJš
�œ
�œ�œ�œ�œ&˜hš�œ
�œ�œ
�œ�œž˜Cšœ
�œ˜Jš�œ)˜+Jš�œ ˜"J˜—Jšœ
�œ�œ'˜PJ˜
—š�œ
�œ�œž.˜GJš
œ˜Jšœ
�œ�œ&˜OJ˜
—š�œžA˜HJš
œ˜Jšœ
�œ�œ&˜OJ˜—Jš
œ7˜7š�œ,�˜6š�œ�œ,�˜IJš�œ�œ�œ˜CJš�œ�œ�œ�œ˜9Jš�œ�œ�œ�œ˜6Jš�œ�œž;˜M—Jš�
œ�œ�œ˜>Jš�œ�œ�œ˜:Jš�œ�œ�œ�œ˜9Jš�œ�œ�œ�œ˜6Jš�œ�œž%˜7—Jš
œ˜—Jš�œ�œ�œ˜@Jš�
œ�œ�œ˜<Jš�œ�œ�œ˜8Jš�œ�œ�œ�œ˜9Jš�œ�œ�œ�œ˜6Jš�œ
˜—š�œ˜Jšœ
�œ˜(Jš�œ�˜Jš�œ�œ˜4š�œ�
˜Jšœ
�œ�œ˜'Jšœ
�œ�œ˜"Jš�œ˜J˜—š�
œ˜Jšœ
�œ�œ˜'Jšœ
�œ�œ˜"Jš�œ˜J˜—š�œ˜
Jšœ
�œ�
œ˜%Jšœ
�œ�œ˜"Jš�œ˜J˜—š�œ�œž+˜FJšœ
�œ�œ˜"Jš�œ˜J˜—Jš�œ
˜J˜—š�
œ˜Jšœ
�œ˜)Jš�œ�˜Jš�
œ�œ�œ˜4š�œ�
˜Jšœ
�œ�œ˜'Jšœ
�œ�œ˜"Jš�œ˜J˜—š�œ˜
Jšœ
�œ�
œ˜%Jšœ
�œ�œ˜"Jš�œ˜J˜—Jš�œ�œ˜(š�œ˜
Jšœ
�œ�œ˜"Jš�œ˜J˜—Jš�œ�œž,˜?J˜—š�œ˜
Jšœ
�œ˜'Jš�œ�˜Jš�œ�œ˜4š�œ�
˜Jšœ
�œ�œ˜'Jšœ
�œ�œ˜"Jš�œ˜J˜—š�
œ˜Jšœ
�œ�œ˜'Jšœ
�œ�œ˜"Jš�œ˜J˜—š�œ˜Jšœ
�œ�œ˜"Jš�œ˜J˜—Jš�œ�œ˜%Jš�œ�œž*˜<J˜—š�œ�œ�˜)Jš
�
œ�œ�œ�œ�œ˜Eš�œ�
˜Jšœ
�œ�œ˜'Jšœ
�œ�œ˜"Jš�œ˜J˜—š�
œ˜Jšœ
�œ�œ˜'Jš�œ˜J˜—š�œ˜Jšœ
�œ�
œ˜%Jšœ
�œ�œ˜"Jš�œ˜J˜—Jš�œ�œ�œ�œ˜9š�œ˜Jšœ
�œ�œ˜"Jš�œ˜J˜—Jš�œ
˜—š�œ�œ�˜&Jš�œ�œ�œ�œ˜Eš�œ�
˜Jšœ
�œ�œ˜'Jšœ
�œ�œ˜"Jš�œ˜J˜—š�
œ˜Jšœ
�œ�œ˜'Jšœ
�œ�œ˜"Jš�œ˜J˜—š�œ˜Jšœ
�œ�
œ˜%Jš�œ˜J˜—š�œ˜Jšœ
�œ�œ˜"Jš�œ˜J˜—Jš�œ�œ�œ�œ˜6Jš�œ
˜—Jš�œ
˜—Jš
œ˜—š
Ÿ
œ�œ
�œ!�œ�œ˜aJš�œ$˜*Jš
œ˜—š
Ÿ
œ�œ
�œ�œ�œ˜ZJš�œ	�œ�œ˜KJš�œ˜
Jš
œ˜—š
Ÿœ�œ
�œ�œ�œ˜^Jš�œ	�œ�œ ˜RJš�œ˜
Jš
œ˜—šŸœ�œ
�œ�œ˜RJš
œ,˜,Jš
œ ˜ š�œ�˜Jš
œ ˜ Jš�œ
˜—Jš�œ˜
Jš
œ˜—šŸœ�œ
�œ�œ˜OJš
œ,˜,š�œ�˜Jš
œ
˜
Jš�œ
˜—Jš�œ˜Jš
œ˜—šŸœ�œ
�œ�œ˜QJš
œ­™­Jš
œ.˜.Jš�œ
�œ�œ�œ
˜AJ˜J˜—šŸœ�œ
�œ�œ˜TJš
œ°™°Jš
œ,˜,š�œ�˜Jš
œ
˜
Jš�œ
˜—Jš�œ˜J˜—šŸœ�œ
�œ�œ˜TJš
œ�™�Jš
œ,˜,Jš
œ ˜ š�œ�˜Jš
œ ˜ Jš�œ
˜—Jš�œ˜
Jš
œ˜—šŸ
œ�œ
�œ�œ!˜WJ–TRUEš
œc™cJ˜ Jš
œ˜Jš
œ˜š�œ�˜J˜Jš�œ
˜—š�œ�˜J˜Jš�œ
˜—Jš�œ˜!J˜—šŸœ�œ
�œ
�œ˜9Jš
œ™Jšœ�œ
˜!Jš�œ˜J˜—š
Ÿœ�œ
�œ�œ�œ™>J™7Jšœ�œ
™š�œ
�œ�œ™Jšœ�œ
�œ
�œ
™IJš�œ�œ�œ™9Jš
œ
™
—š
�™J™—Jš�œ™J™—š
Ÿœ�œ
�œ	�œ	�œ˜KJ™&Jš
œ˜Jš�œ˜J˜—š
Ÿœ�œ
�œ	�œ�œ˜DJ™&Jšœ�œ�œ˜:Jš�œ˜J˜J˜—š
Ÿœ�œ
�œ�œ�œ˜EJšœ�œ�œ˜3Jš�œ˜J˜J˜—š
Ÿœ�œB�œ	�œ�œ™ƒ
Jš
œ²™²J™Jš
œ™J™š�œ�œ
�™!Jš
œ`™`Jš
œ#™#Jš�œ
™J™—Jš
œb™bJš�œ™
J™—J™š
Ÿœ�œ
�œ�œ	�œ˜PLš
œ`™`Jš
œ˜Jš
œ'˜'Jš
œ˜J˜J™—šŸœ�œ�œ ˜ZJš
œ„™„Jš
œ˜Jš
œ˜Jšœ	�œ�œ
˜Jš
œ˜Jšœ�œž
˜Jšœ�œ
˜Jš
œ&˜&Jš
œ'˜'J˜Jš
œ˜Jš
œ(˜(Jš
œ$˜$J˜Jš
œ
™
Jšœž˜=J˜Jš
žK™KJš
œ(˜(Jš
œ1˜1Jš
œ'˜'Jšœ�œ
˜š�œ�˜Jš
œ"˜"Jš
œ(˜(Jš
œ1˜1Jš
œ'˜'Jšœ�œ
˜Jš�œ
˜—Jšœ�œH˜VJšœ�œ�œ˜#J˜Jš
œÔ
™Ô
Jš
œ#˜#Jš
œ'˜'š�œ
�œ�˜#š�œ
�œ�˜"Jš
œU˜U——š�œ�˜Jš
œ"˜"Jš
œ'˜'š�œ
�œ�˜#š�œ
�œ�˜"Jš
œU˜U——Jš�œ
˜—J˜Jš�œ˜J˜J˜—šŸœ�œ˜9Jš
œ¡™¡Jš
œ˜Jš
œ˜Jšœ	�œ�œ
˜J˜Jš
žK™KJš
œ'˜'Jšœ�œ
˜š�œ�˜Jš
œ"˜"Jš
œ'˜'Jšœ�œ
˜Jš�œ
˜—J˜Jš
œÒ
™Ò
Jš
œ#˜#Jš
œ'˜'š�œ�˜Jš
œ˜—š�œ�˜Jš
œ"˜"Jš
œ'˜'š�œ�˜Jš
œ˜—Jš�œ
˜—J˜J˜—š
Ÿœ�œ
�œA�œ�œ$˜�
Lšœ�œ
˜#L˜	Lš�œ�œ
�œ
�œ˜Lšœ�œ˜L˜š�œ�œ
�˜Lšœ	�œ˜ L˜Lš�œ
˜—Lš�œ˜Lšœžœ˜(L˜—šŸœ�œ"�œ˜IJš
œ7™7J™Jšœ�œ
˜Jšœ�œ
�œ�œ˜2J˜š	�œ�œ
�œ�œž˜8J˜—š�œ�œ
�œž
˜0Jšœ�œ˜%Jšœ�œ�œ!�œ�œ�œ�œ!�œ�œ˜”
J˜
—š�œž˜Jš
œ7˜7Jšœ�œž#˜SJ˜—J˜"Jš
œ˜Jš�œ
˜J˜J˜—š
Ÿœ�œ �œ�œ
�œ˜SJš
ž™Jš
œ3˜3Jš
œ&˜&Jš
œ˜Jšœ�œ
˜Jšœ�œ
˜J˜Jš
œ™Jšœž(˜BJ˜Jš
œ™Jšœ�œ˜$Jšœ�œ�œ!�œ�œ�œ�œ!�œ�œ˜“
J˜Jš
œ™Jš
œ$˜$JšœžJ˜eJšœ�œ
˜
š�œ
�œ�˜Jš
œ˜Jš
œ˜Jš�œ�œ�œž(˜VJšœ�œ"˜1Jšœ!�œ�œ�œ#˜uJš
œ˜Jš�œ
˜—J˜J˜Jš
œ$™$Jš
œ$˜$JšœžJ˜eJšœ�œ
˜
š�œ
�œ�˜Jš
œ#˜#Jš�œ�œ�œž(˜VJš�œ%�œ7˜bJš
œ˜Jš�œ
˜—J˜Jš�œ
˜J˜J˜—šŸœ�œ
�œ�œ�œ
�œ�œ#˜yJšœ�œ�œ
˜Jšœ�œ
˜Jšœ�œ
˜Jšœ�œž/˜BJšœ�œ˜Jšœ
�œ
˜Jšœ�œ
˜Jšœ�œ˜J˜ J˜J˜Jšœ
�œ
˜Jšœ�œ
�œ�œ˜/J˜Jšœ�œ
˜Jš
œ˜Jš�œ�œ�œ
˜'J˜Jš�œ
�œ�˜˜Jš
œ˜Jš
œ3˜3Jš�œ�œ&˜;Jš
œ3˜3Jš�œ�œ+˜@Jšœ�œ˜(Jš�œ
�œ
�œ2˜FJš
œ3˜3Jš�œ�œ&˜;Jšœ�œ˜(Jš�œ
�œ
�œ2˜FJ˜Jš
œ3˜3Jš�œ�œ,˜AJš
œ3˜3Jš�œ�œ4˜IJ˜Jšœ
�œ
˜Jšœ�œ
˜Jš
œ˜Jš�œ�œ�œ
˜*J˜š�œ
�œ	�˜J˜Jš
œ3˜3Jš�œ�œ+˜@Jš
œ˜Jš
œ3˜3Jš�œ�œ&˜;Jšœ-�œ	˜8Jšœ�œ˜+Jš
œ3˜3Jš�œ�œ&˜;Jš
œ˜Jš
œ3˜3Jš�œ�œ,˜AJ˜Jšœ�œ`˜oJšœ�œ˜(J˜Jš
œ˜Jš�œ�œ�œ
˜*J˜Jš�œ
˜—J˜Jšœž˜1J˜šœ�œ?˜NJš
œ1˜1—Jšœ�œ˜'J˜Jš
œ˜Jš�œ�œ�œ
˜'J˜Jš�œ
˜—J˜J˜J˜—šŸœ�œ �œ#�œ˜oJš
ϐ
™ê
J˜Jš
œ˜Jš
œ˜Jš
œ!˜!Jš
œ˜Jš
œ˜Jš
œ(˜(Jš
œ˜J˜ J˜J˜Jš
œ>™>Jš
œ˜Jšœ	�œ
˜
Jš
œ˜š�œ�œ
�˜Jš
œ$˜$šœ�œ9˜GJšœ3�œ�œ˜J—Jšœ	�œ˜!Jš
œ!˜!Jš�œ
˜—Jšœ#ž4˜WJš
œ˜J˜Jš
ž"™"š�œ�œ
�˜Jš
œ˜Jš
œ+˜+Jšœ	�œž˜š�œ�œ
�œ
žd˜|Jš
œ˜Jšœ8ž[˜“
Jšœ
�œ�
�œ�œ˜Å
Jš�œ�œž'˜WJšœ	�œ˜!Jš�œ�œ
�œž'˜VJš
œ˜Jš�œ
˜—Jšœž˜0Jšœ#ž˜>Jš
œ˜Jšœž/˜JJš�œ
˜—J˜Jš�œ˜J˜J˜—šŸ	œ�œ!�œ�œ˜VJš
œ1™1š�œ
�œ
�˜Jš�œ�œ
�œ˜8Jš
œ˜Jš�œ
˜—Jš�œ�œ˜
J˜J˜—šŸ
œ�œ
�	œ�œ˜XJšœ�œ
˜
š�œ�œ
�˜Jšœ�œ˜J˜Jš�œ
˜—Jš�œ˜Jšœž
˜J˜—šŸœ�œ
�œ�œ�œ
�œ�œ�œ	˜�
Jš
�
œ�œ�œ�	œ�
œ˜6Jš�œ�œ
ž5˜ZJšœ�œ�œ
˜Jšœ�œ
˜Jšœ�œ
˜Jšœ�œž/˜BJšœ
�œ
˜Jšœ�œ
˜Jšœ�œ˜Jšœ
�œ
˜Jšœ�œ
�œ�œ˜/Jš
œ�œ�œ�œ
�
œ�œ�
œ˜JJšœ�œ
˜Jšœ�œ�œž˜KJ˜Jš
œ˜Jš�œ�œ�œ
˜'J˜Jš�œ
�œ�˜˜Jš
œ˜Jšœ�œ
˜ Jš�œ�œ˜>Jš�œ�œ˜>Jš
œ3˜3Jš�œ�œ
�
œ˜;Jš
œ3˜3Jš�œ�œ
�
œ˜@Jšœ�œ˜(Jš�œ
�œ
�œ
�
œ$˜FJš
œ3˜3Jš�œ�œ
�
œ˜;Jšœ�œ˜(Jš�œ
�œ
�œ
�
œ$˜FJ˜Jš
œ3˜3Jš�œ�œ
�
œ˜AJš
œ3˜3Jš�œ�œ
�
œ&˜IJ˜Jšœ
�œ
˜Jš
œ˜Jš�œ�œ�œ
˜*J˜š�œ
�œ	�˜J˜Jš
œ3˜3Jš�œ�œ
�
œ˜@Jš
œ˜Jš�œ�œ˜DJš�œ�œ˜Dš�œ�
œ
�˜-Jšœ�	œ
˜%—Jš
œ3˜3Jš�œ�œ
�
œ˜;Jšœ-�œ	˜8Jš
œ3˜3Jš�œ�œ
�
œ˜;Jš
œ˜Jš
œ3˜3Jš�œ�œ
�
œ˜AJ˜Jš
œ˜Jš�œ�œ�œ
˜*J˜Jš�œ
˜—J˜Jšœž˜1Jš
œ˜Jš�œ�œ�œ
˜'J˜Jš�œ
˜—J˜Jš�
œ,�œ˜SJš�
œ,�œ˜SJš
œ˜š�œ�˜Jš
œ
˜
š�œ�œ
�œ˜"š�œ�	œ
�œ
˜"Jš�
œ=�œ
˜V—š
�˜Jšœ5�œ
˜A—J˜—Jš�œ
˜—J˜J˜—š
Ÿœ�œ
�œ#�œ�œ˜mLš
œê™êJš
œ˜Jš
œ˜Jš
œ˜Jš
œ˜Jš
œ˜Jš
œ ˜ Jš
œ*˜*Jš�œ�œ
�œ
˜(Jšœ#�œž ˜KJšœB�œž6˜�
š�œ
�œ	�œ	�œ
�œž?˜›
Jšœ!ž)˜JJš
œ+˜+Jš�œ�œ
�œ�œ˜7Jšœ#�œ˜*JšœB�œ˜JJš�œ
˜—Jš�œ�œ
˜L˜—šŸœ�œ
�œ �œ˜\Lš
œ!™!Jšœ�œ
˜Jš
œ˜Jš�œ�œ
�œ�œ
�œž˜Eš�œ˜Jš
œ7˜7Jš
œ2˜2Jšœ-�œ&ž#˜yJš�œ˜
J˜—J˜—šŸœ�œ �œ;�œ	�œ �œ˜»
Jš
œ3˜3Jš
œ&˜&Jšœ�œ˜Jšœ�œ
˜J˜Jš
œ™Jšœž(˜BJ˜Jš
œ™Jš
œ,˜,š�œ
�œ%�œ˜0Jš
œ˜Jš
œ˜Jš
œ˜—J˜J™$Jš
œ˜Jš
œ˜Jš
œ$˜$JšœžJ˜eJšœ�œ
˜
š�œ
�œ�˜Jš
œ#˜#Jš�œ�œ�œž(˜VJš�œ%�œ]˜ˆ
Jš
œ˜Jš�œ
˜—J˜Jš�œ
˜J˜J˜—šŸœ�œ
�œ�œ�œ�œ˜]Lš
œš
™š
Jš
œ˜Jš
œ˜Jš
œ'˜'Jš
œ˜Jš�œ�œ�œ
˜/š�œ�˜Jšœ�œ˜ Jš
œ'˜'Jš
œ˜Jš�œ�œ�œ
˜/Jš�œ
˜—J˜L™—š
Ÿœ�œ
�œ�œ�œ˜ELšœ�œ
˜Jšœ�œž˜2Jš�œ�œ)�œž˜_Jš�œ�œ\ž˜�
Jš�œ˜J˜L˜—L™Jš�œ
˜J˜—…—�\ÝÏ