DIRECTORY
Rope,
Convert,
IO,
Imager,
ImagerPath,
RealFns,
List,
RatNums,
EuclideanGraphs,
ConvexEuclideanGraphs;

ConvexEuclideanGraphsImpl: CEDAR PROGRAM
IMPORTS IO, Rope, Convert, ImagerPath, RealFns, List, RatNums, EuclideanGraphs
EXPORTS ConvexEuclideanGraphs

= BEGIN OPEN RN: RatNums, EG: EuclideanGraphs, ConvexEuclideanGraphs;

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 EG.PointLineTest[pointArray[I], pointArray[I+1], pointArray[I+2]]#ONLINE THEN EXIT;
I _ I+1;
ENDLOOP;
IF EG.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 EG.PointEqual[pointArray[MyMOD[I,n]], pointArray[MyMOD[I+1,n] ]] DO
Compactify[MyMOD[I+1,n]]; -- check for and remove duplicate points
ENDLOOP;
WHILE EG.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;
};

ThreeOrMoreVertices: PUBLIC PROC [w: EG.EuclideanGraph] 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 ];
};

AddEdge: PUBLIC PROC [root, adjacentVertex: Vertex, exterior: BOOL _ FALSE, IPEdge: BOOL _ FALSE, clientData: REF _ NIL, visitedValue: BOOL _ FALSE] ~ {
cEGEdgeData: CEGEdgeData _ NEW[CEGEdgeDataRec _ [exteriorEdge: exterior, intersectionPolygonEdge: IPEdge, clientData: clientData]];
EG.AddEdge[root, adjacentVertex, cEGEdgeData, visitedValue];
};

InsertVertexInEdges: PUBLIC PROC [v, w: Vertex, p: Point, vertexData: REF _ NIL] RETURNS [newVertex: Vertex] ~ {
vTow, wTov: Adjacency;
vTowData, wTovData: CEGEdgeData;
z: Vertex _ EG.CreateVertex[p, vertexData, v.visited];
[vTow, wTov] _ EG.FindAdjacency[v, w];
vTowData _ NARROW[vTow.data];
wTovData _ NARROW[wTov.data];
AddEdge[z, w, vTowData.exteriorEdge, vTowData.intersectionPolygonEdge, vTowData.clientData, vTow.visited];
EG.DeleteEdge[v, w];
AddEdge[v, z, vTowData.exteriorEdge, vTowData.intersectionPolygonEdge, vTowData.clientData, vTow.visited];
AddEdge[z, v, wTovData.exteriorEdge, wTovData.intersectionPolygonEdge, wTovData.clientData, wTov.visited];
EG.DeleteEdge[w, v];
AddEdge[w, z, wTovData.exteriorEdge, wTovData.intersectionPolygonEdge, wTovData.clientData, wTov.visited];
RETURN[z];
};

JoinVertices: PUBLIC PROC [start, end: Vertex, startToEndData, endToStartData: REF _ NIL, startToEndIPEdge, endToStartIPEdge: BOOL _ FALSE, startToEndExterior, endToStartExterior: BOOL _ FALSE, startToEndVisited, endToStartVisited: BOOL _ FALSE] ~ {
startToEndCEGData: CEGEdgeData _ NEW[CEGEdgeDataRec _ [exteriorEdge: startToEndExterior, intersectionPolygonEdge: startToEndIPEdge, clientData: startToEndData]];
endToStartCEGData: CEGEdgeData _ NEW[CEGEdgeDataRec _ [exteriorEdge: endToStartExterior, intersectionPolygonEdge: endToStartIPEdge, clientData: endToStartData]];
EG.AddEdge[start, end, startToEndCEGData, startToEndVisited];
EG.AddEdge[end, start, endToStartCEGData, endToStartVisited];
};


StepVertex: PUBLIC PROC[ v1, w1: Vertex, outline: BOOL] RETURNS [ v2, w2: Vertex] = {
RETURN [w1, NextVertex[ v1, w1, outline] ]
};

NextVertex: PUBLIC PROC[ v, w: Vertex, outline: BOOL] RETURNS [ z: Vertex] = {
IF outline THEN z _ NextOutlineVertex[v,w] ELSE z _ NextPolygonVertex[v,w];
RETURN [z]
};

PreviousVertex: PUBLIC PROC[ v, w: Vertex, outline: BOOL] RETURNS [ z: Vertex] = {
IF outline THEN z _ PreviousOutlineVertex[v,w] ELSE z _ PreviousPolygonVertex[v,w];
RETURN [z]
};

NextOutlineVertex: PUBLIC PROC[ v, w: Vertex] RETURNS [ z: Vertex] = {
A: AdjacencyList _ 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: Vertex] RETURNS [ Vertex] = {
A: AdjacencyList _ w.adjacentVertices;
WHILE A.first.vertex # v DO
A _ A.rest
ENDLOOP;
RETURN [A.rest.first.vertex]
};

SpecialPreviousOutlineVertex: PUBLIC PROC [w: Vertex] RETURNS [v:Vertex] ~ {
ahl: AdjacencyList _ w.adjacentVertices;
WHILE NOT GetEdgeExterior[ahl.first] DO ahl _ ahl.rest ENDLOOP;
v _ ahl.first.vertex;
};

PreviousOutlineVertex: PUBLIC PROC [v, w: Vertex] RETURNS [z: Vertex] ~ {
A: AdjacencyList _ v.adjacentVertices;
WHILE A.first.vertex # w DO
A _ A.rest
ENDLOOP;
RETURN [A.rest.first.vertex]
};

PreviousPolygonVertex: PUBLIC PROC [v, w: Vertex] RETURNS [z:Vertex] ~ {
A: AdjacencyList _ 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]
};

GetEdgeClientData: PUBLIC PROC [startToEnd: Adjacency] RETURNS [data: REF ANY] = {
cEGEdgeData: CEGEdgeData _ NARROW[startToEnd.data];
RETURN[cEGEdgeData.clientData];
};
SetEdgeClientData: PUBLIC PROC [startToEnd: Adjacency, data: REF ANY] = {
cEGEdgeData: CEGEdgeData _ NARROW[startToEnd.data];
cEGEdgeData.clientData _ data;
};
SetPolygonClientData: PUBLIC PROC [start, end: Vertex, data: REF, setVisited: BOOL _ FALSE] = {
startToEnd, endToStart: Adjacency;
firstStart: Vertex _ start;
[ startToEnd, endToStart ] _ EG.FindAdjacency[ start, end ];
SetEdgeClientData[startToEnd, data];
IF setVisited THEN startToEnd.visited _ TRUE;
WHILE end # firstStart DO
[start, end] _ StepVertex[start, end, FALSE];
[ startToEnd, endToStart ] _ EG.FindAdjacency[ start, end ];
SetEdgeClientData[startToEnd, data];
IF setVisited THEN startToEnd.visited _ TRUE;
ENDLOOP;
};
GetEdgeExterior: PUBLIC PROC [startToEnd: Adjacency] RETURNS [value: BOOL] ~ {
cEGEdgeData: CEGEdgeData _ NARROW[startToEnd.data];
RETURN[cEGEdgeData.exteriorEdge];
};

SetEdgeExterior: PUBLIC PROC [startToEnd: Adjacency, value: BOOL] ~ {
cEGEdgeData: CEGEdgeData _ NARROW[startToEnd.data];
cEGEdgeData.exteriorEdge _ value;
};
GetEdgeIPEdge: PUBLIC PROC [startToEnd: Adjacency] RETURNS [value: BOOL] ~ {
cEGEdgeData: CEGEdgeData _ NARROW[startToEnd.data];
RETURN[cEGEdgeData.intersectionPolygonEdge];
};
SetEdgeIPEdge: PUBLIC PROC [startToEnd: Adjacency, value: BOOL] ~ {
cEGEdgeData: CEGEdgeData _ NARROW[startToEnd.data];
cEGEdgeData.intersectionPolygonEdge _ value;
};
SetPolygonIPEdges: PUBLIC PROC [start, end: Vertex, value: BOOL] ~ {
startToEnd, endToStart: Adjacency;
firstStart: Vertex _ start;
[ startToEnd, endToStart ] _ EG.FindAdjacency[ start, end ];
SetEdgeIPEdge[startToEnd, value];
WHILE end # firstStart DO
[start, end] _ StepVertex[start,end, FALSE]; -- polygon step
[ startToEnd, endToStart ] _ EG.FindAdjacency[ start, end ];
SetEdgeIPEdge[startToEnd, value];
ENDLOOP;
};

ClearGraphIPEdges: PUBLIC PROC[v, w: Vertex] = {
startToEnd, endToStart: Adjacency;
firstIntersection: Vertex _ v;
outline: BOOL _ FALSE;

[ startToEnd, endToStart ] _ EG.FindAdjacency[ v, w ];
startToEnd.visited _ FALSE;
SetEdgeIPEdge[startToEnd, FALSE];
WHILE w # firstIntersection DO
[v, w] _ StepVertex[v,w, outline];
[ startToEnd, endToStart ] _ EG.FindAdjacency[ v, w ];
startToEnd.visited _ FALSE;
SetEdgeIPEdge[startToEnd, FALSE];
ENDLOOP;

[v, w] _ StepVertex[v,w, outline];
[ startToEnd, endToStart ] _ EG.FindAdjacency[ v, w ];
IF endToStart.visited THEN ClearGraphIPEdges[w, v];
WHILE w # firstIntersection DO
[v, w] _ StepVertex[v,w, outline];
[ startToEnd, endToStart ] _ EG.FindAdjacency[ v, w ];
IF endToStart.visited THEN ClearGraphIPEdges[w, v];
ENDLOOP;
};
IPVertexToEdge: PUBLIC PROC [intersectionPolyVertex: Vertex] RETURNS [intersectionPolyNext: Vertex] ~ {
adjacencies: AdjacencyList _ intersectionPolyVertex.adjacentVertices;
WHILE NOT GetEdgeIPEdge[adjacencies.first] DO
adjacencies _ adjacencies.rest;
ENDLOOP;
RETURN[adjacencies.first.vertex];
};
IPVertex: PUBLIC PROC [v: Vertex] RETURNS [BOOL] ~ {
adjacencies: AdjacencyList _ v.adjacentVertices;
adjHead: AdjacencyList _ v.adjacentVertices;
IF adjacencies = NIL THEN RETURN[FALSE];
IF GetEdgeIPEdge[adjacencies.first] THEN RETURN[TRUE];
adjacencies _ adjacencies.rest;
WHILE adjacencies # adjHead DO
IF GetEdgeIPEdge[adjacencies.first] THEN RETURN[TRUE];
adjacencies_ adjacencies.rest;
ENDLOOP;
RETURN[FALSE];
};
ClearEdgeVisitedFields: PUBLIC PROC [v, w: Vertex]  = {
vTow, wTov: Adjacency;
firstv: Vertex _ v;
outline: BOOL _ FALSE;

[ vTow, wTov ] _ EG.FindAdjacency[ v, w ];
vTow.visited _ FALSE;
WHILE w # firstv DO
[v, w] _ StepVertex[v,w, outline];
[ vTow, wTov ] _ EG.FindAdjacency[ v, w ];
vTow.visited _ FALSE;
ENDLOOP;

[v, w] _ StepVertex[v, w, outline];
[ vTow, wTov ] _ EG.FindAdjacency[ v, w ];
IF wTov.visited THEN IF NOT GetEdgeExterior[wTov] THEN
ClearEdgeVisitedFields[w, v ]
ELSE
wTov.visited _ FALSE;
WHILE w # firstv DO
[v, w] _ StepVertex[v,w, outline];
[ vTow, wTov ] _ EG.FindAdjacency[ v, w ];
IF wTov.visited THEN IF NOT GetEdgeExterior[wTov] THEN
ClearEdgeVisitedFields[w, v]
ELSE
wTov.visited _ FALSE;
ENDLOOP;
};

ClearGraphEdgeFields: PUBLIC PROC [v: Vertex] ~ {
Subr: PROC [v: Vertex, visitedValue: BOOL] ~ {
vAdjList: AdjacencyList _ v.adjacentVertices;
firstVertex, nextVertex: Vertex;
vToNext, nextToV: Adjacency;

firstVertex _ nextVertex _ vAdjList.first.vertex; 
[vToNext, nextToV] _ EG.FindAdjacency[v, nextVertex] ;
vToNext.visited _ FALSE;
SetEdgeIPEdge[vToNext, FALSE];
vAdjList _ vAdjList.rest;
nextVertex _ vAdjList.first.vertex;
WHILE nextVertex#firstVertex DO
[vToNext, nextToV] _ EG.FindAdjacency[v, nextVertex] ;
vToNext.visited _ FALSE;
SetEdgeIPEdge[vToNext, FALSE];
vAdjList _ vAdjList.rest;
nextVertex _ vAdjList.first.vertex;
ENDLOOP;
v.visited _ visitedValue; -- now we can say that we've been here.

IF (nextVertex.visited # visitedValue) THEN Subr[nextVertex, visitedValue];
vAdjList _ vAdjList.rest;
nextVertex _ vAdjList.first.vertex;
WHILE nextVertex#firstVertex DO
IF (nextVertex.visited # visitedValue) THEN Subr[nextVertex, visitedValue];
vAdjList _ vAdjList.rest;
nextVertex _ vAdjList.first.vertex;
ENDLOOP;
};

IF v = NIL OR v.adjacentVertices = NIL THEN RETURN ELSE Subr[v, NOT v.visited];
};

SetOutwardOutlineEdgeFields: PUBLIC PROC [start, end: Vertex, exteriorEdgeValue, intersectionPolygonEdgeValue: BOOL, clientDataValue: REF _ NIL] ~ {
cEGEdgeData: CEGEdgeData;
startToEnd, endToStart: Adjacency;
firstStart: Vertex _ start;
[ startToEnd, endToStart ] _ EG.FindAdjacency[ start, end ];
cEGEdgeData _ NARROW[endToStart.data];
cEGEdgeData.exteriorEdge _ exteriorEdgeValue;
cEGEdgeData.intersectionPolygonEdge _ intersectionPolygonEdgeValue;
cEGEdgeData.clientData _ clientDataValue;
WHILE end # firstStart DO
[start, end] _ StepVertex[start,end, TRUE]; --  outline step
[ startToEnd, endToStart ] _ EG.FindAdjacency[ start, end ];
cEGEdgeData _ NARROW[endToStart.data];
cEGEdgeData.exteriorEdge _ exteriorEdgeValue;
cEGEdgeData.intersectionPolygonEdge _ intersectionPolygonEdgeValue;
cEGEdgeData.clientData _ clientDataValue;
ENDLOOP;
};

SetPolygonFields: PUBLIC PROC [start, end: Vertex, exteriorEdgeValue, intersectionPolygonEdgeValue: BOOL _ FALSE, clientDataValue: REF _ NIL] ~ {
cEGEdgeData: CEGEdgeData;
startToEnd, endToStart: Adjacency;
firstStart: Vertex _ start;
[ startToEnd, endToStart ] _ EG.FindAdjacency[start, end];
cEGEdgeData _ NARROW[startToEnd.data];
cEGEdgeData.exteriorEdge _ exteriorEdgeValue;
cEGEdgeData.intersectionPolygonEdge _ intersectionPolygonEdgeValue;
cEGEdgeData.clientData _ clientDataValue;
WHILE end # firstStart DO
[start, end] _ StepVertex[start, end, FALSE]; --  polygon step
[ startToEnd, endToStart ] _ EG.FindAdjacency[ start, end ];
cEGEdgeData _ NARROW[startToEnd.data];
cEGEdgeData.exteriorEdge _ exteriorEdgeValue;
cEGEdgeData.intersectionPolygonEdge _ intersectionPolygonEdgeValue;
cEGEdgeData.clientData _ clientDataValue;
ENDLOOP;
};



CenterOfMass: PUBLIC PROC[ v, w : Vertex, outline: BOOL ] RETURNS [Point] = {
vfirst: Vertex _ 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 ]  ] ];
};

CountPolygonVertices: PUBLIC PROC [start, end: Vertex, outline: BOOL _ FALSE] RETURNS [numVertices: CARDINAL] ~ {
firstStart: Vertex _ start;
numVertices _ 1;
WHILE end # firstStart DO
numVertices _ numVertices + 1;
[start, end] _ StepVertex[start, end, outline];
ENDLOOP;
};

AddVertexToPolygon: PUBLIC PROC [entryPrior, entryNext: Vertex, coordinates: Point, clientData: REF _ NIL] RETURNS [exitPrior, exitNext: Vertex] = {
newVertex: Vertex _ EG.CreateVertex[coordinates, NIL, FALSE];
numVertices: CARDINAL;
priorToNext, nextToPrior: Adjacency;
edgeVisitedValue: BOOL;
IF entryNext = NIL THEN RETURN[NIL, newVertex];  -- no vertices previously
newVertex.visited _ entryNext.visited;
IF entryPrior = NIL THEN {  -- one vertex previously
AddEdge[newVertex, entryNext, FALSE, FALSE, clientData, FALSE];
AddEdge[entryNext, newVertex, TRUE, FALSE, NIL, FALSE];
RETURN[newVertex, entryNext];
};
[priorToNext, nextToPrior] _ EG.FindAdjacency[entryPrior, entryNext];
edgeVisitedValue _ priorToNext.visited;
numVertices _ CountPolygonVertices[entryPrior, entryNext]; -- do before SeparateVertices
EG.SeparateVertices[entryPrior, entryNext];
AddEdge[entryPrior, newVertex, FALSE, FALSE, clientData, edgeVisitedValue];
AddEdge[newVertex, entryPrior, TRUE, FALSE, NIL, edgeVisitedValue];
AddEdge[newVertex, entryNext, FALSE, FALSE, clientData, edgeVisitedValue];
AddEdge[entryNext, newVertex, TRUE, FALSE, NIL, edgeVisitedValue];
IF numVertices = 2 THEN {
AddEdge[entryNext, entryPrior, FALSE, FALSE, clientData, edgeVisitedValue];
AddEdge[entryPrior, entryNext, TRUE, FALSE, NIL, edgeVisitedValue];
};
RETURN[newVertex, entryNext];
};


PointSectorTest: PUBLIC PROC [rightvertex, leftvertex, centerOfMass, test: Point] RETURNS[PointSectorRelation _ EQUALCOM] = {
pointEdgeRelation: EG.PointDirectedEdgeRelation _ EG.PointDirectedEdgeTest[ centerOfMass, rightvertex, test];
SELECT pointEdgeRelation FROM
BEFORESTART => RETURN[ OUTSIDESUBTEND ];
EQUALSTART => RETURN[ EQUALCOM ];
BETWEENSTARTEND => RETURN[ RIGHTSPOKEINTERIOR ];
EQUALEND => RETURN[ EQUALRIGHTVERTEX ];
AFTEREND => RETURN[ RIGHTRAYINTERIOR ];
RIGHTOFEDGE => RETURN[ OUTSIDESUBTEND ];
LEFTOFEDGE => {
pointEdgeRelation _ EG.PointDirectedEdgeTest[ centerOfMass, leftvertex, test];
SELECT pointEdgeRelation FROM
BEFORESTART => RETURN[ OUTSIDESUBTEND ];
BETWEENSTARTEND => RETURN[ LEFTSPOKEINTERIOR ];
EQUALEND => RETURN[ EQUALLEFTVERTEX ];
AFTEREND => RETURN[ LEFTRAYINTERIOR ];
LEFTOFEDGE => RETURN[ OUTSIDESUBTEND ];
RIGHTOFEDGE => {
pointLineRelation: EG.PointLineRelation _ EG.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: Vertex, centerOfMass, test: Point, outline: BOOL ] RETURNS [status: PointSectorRelation, t, u: Vertex] = {
pointSectorRelation: PointSectorRelation _ PointSectorTest[ v.coordinates, w.coordinates, centerOfMass, test];
WHILE pointSectorRelation = OUTSIDESUBTEND DO
[v, w] _ StepVertex [ v, w, outline];
pointSectorRelation _ PointSectorTest[ v.coordinates, w.coordinates, centerOfMass, test];
ENDLOOP;
RETURN[ pointSectorRelation, v, w ];
};

VertexExternalToPolygon: PUBLIC PROC [firstCOM: Point, firstStart, firstEnd, secondStart, secondEnd: Vertex] RETURNS [found: BOOL, newFirstStart, newFirstEnd, newSecondStart, newSecondEnd: Vertex _ NIL] ~ {
pointSectorStatus: PointSectorRelation;
initSecondVertex: Vertex _ secondStart;
done: BOOL _ FALSE;
[pointSectorStatus, newFirstStart, newFirstEnd] _ FindSubtendForPoint[ firstStart, firstEnd, firstCOM, secondStart.coordinates, FALSE ]; -- [v5,w5] defines a particular sector of this polygon
WHILE NOT done DO 
IF pointSectorStatus = RIGHTRAYINTERIOR OR pointSectorStatus = LEFTRAYINTERIOR OR pointSectorStatus = SUBTENDINTERIOR THEN
RETURN[TRUE, newFirstStart, newFirstEnd, secondStart, secondEnd];
[secondStart, secondEnd] _ StepVertex[secondStart, secondEnd, FALSE];
IF secondStart = initSecondVertex THEN
done _ TRUE
ELSE
[pointSectorStatus, newFirstStart, newFirstEnd] _ FindSubtendForPoint[newFirstStart, newFirstEnd, firstCOM, secondStart.coordinates, FALSE ];
ENDLOOP;
RETURN[FALSE, newFirstStart, newFirstEnd, newSecondStart, newSecondEnd];
};
ConvexPolygon: PUBLIC PROC[ v, w : Vertex, outline: BOOL ] RETURNS [BOOL] = {
vfirst: Vertex _ v;
z: Vertex _ NextVertex[v, w, outline];
IF z = v OR z = w THEN RETURN[TRUE];
SELECT EG.PointLineTest[v.coordinates, w.coordinates, z.coordinates] FROM -- check first angle
RIGHTOFLINE => RETURN[FALSE];
LEFTOFLINE => NULL;
ONLINE => NULL; -- 1/7/86 allow a 180deg angle
ENDCASE;
v _ w;  [w, z] _ StepVertex[ w, z, outline ]; -- step past
WHILE v # vfirst DO
SELECT EG.PointLineTest[v.coordinates, w.coordinates, z.coordinates] FROM -- check first angle
RIGHTOFLINE => RETURN[FALSE];
LEFTOFLINE => NULL;
ONLINE => NULL; -- 1/7/86  allow a 180deg angle
ENDCASE;
v _ w;  [w, z] _ StepVertex[ w, z, outline ];
ENDLOOP;
RETURN[TRUE];
};

ConvexPolygonCompare: PUBLIC PROC[ innerCOM: Point, innerStart, innerEnd: Vertex, innerOutline: BOOL, outerStart, outerEnd: Vertex, checkExternal: BOOL _ TRUE] RETURNS [status: ConvexPolygonCompareStatus, innerPrevious, innerCommon, innerNext, outerPrevious, outerCommon, outerNext: Vertex _ NIL] = {
external: BOOL _ FALSE;
innerStartFirst: Vertex _ innerStart;
outerStartFirst: Vertex _ outerStart;
pointSectorRelation: PointSectorRelation;
pointLineRelation: EG.PointLineRelation;
edgeCompareStatus: EG.BiasedEdgeCompareStatus;
intersection: Point;
polygonStep: BOOL _ FALSE;
done: BOOL _ FALSE;

CheckEdgeContact: PROC ~ INLINE {

pointLineRelation _ EG.PointLineTest[innerStart.coordinates, innerEnd.coordinates, outerStart.coordinates];

SELECT pointLineRelation FROM

ONLINE => edgeCompareStatus _ Disjoint; -- we assume outerStart is disjoint from the edge.

LEFTOFLINE => edgeCompareStatus _ Disjoint; -- 

RIGHTOFLINE => {
edgeCompareStatus _ EG.BiasedEdgeCompare[outerStart, outerEnd, innerStart, innerEnd];
SELECT edgeCompareStatus FROM
OuterEndEqInnerStart => {
outerCommon _ outerEnd;
outerEnd _ NextVertex[outerStart, outerCommon, polygonStep];
innerCommon _ innerStart;
innerStart _ PreviousVertex[innerCommon, innerEnd, innerOutline];
};
OuterEndInInner => {
outerCommon _ outerEnd;
innerCommon _ InsertVertexInEdges[innerStart, innerEnd, outerEnd.coordinates];
outerEnd _ NextVertex[outerStart, outerCommon, polygonStep];  -- this statement needs to come after previous one
};
OuterEndEqInnerEnd => {
outerCommon _ outerEnd;
outerEnd _ NextVertex[outerStart, outerCommon, polygonStep];
innerCommon _ innerEnd;
innerEnd _ NextVertex[innerStart, innerCommon, innerOutline];
};
InnerStartInOuter => {
innerCommon _ innerStart;
outerCommon _ InsertVertexInEdges[outerStart, outerEnd, innerStart.coordinates];
innerStart _ PreviousVertex[innerCommon, innerEnd, innerOutline];  -- this statement needs to come after previous one
};
ProperIntersection => {
intersection _ EG.IntersectLines[innerStart.coordinates, innerEnd.coordinates, outerStart.coordinates, outerEnd.coordinates];
innerCommon _ InsertVertexInEdges[innerStart, innerEnd, intersection];
outerCommon _ InsertVertexInEdges[outerStart, outerEnd, intersection];
};
InnerEndInOuter => {
innerCommon _ innerEnd;
outerCommon _ InsertVertexInEdges[outerStart, outerEnd, innerEnd.coordinates];
innerEnd _ NextVertex[innerStart, innerCommon, innerOutline]; -- this statement needs to come after previous one
};
Disjoint => NULL;  -- this one falls through
ENDCASE;
};

ENDCASE;

}; -- CheckEdgeContact

pointSectorRelation _ PointSectorTest[ innerStart.coordinates, innerEnd.coordinates, innerCOM, outerEnd.coordinates ];

WHILE NOT done DO

SELECT pointSectorRelation FROM

RIGHTRAYINTERIOR, LEFTRAYINTERIOR, SUBTENDINTERIOR => NULL;

ENDCASE => { -- outerEnd either inside (closed) inner polygon, or R or L of this sector	
CheckEdgeContact[];
SELECT edgeCompareStatus FROM
Disjoint => NULL;
ENDCASE => RETURN[Intersection, innerStart, innerCommon, innerEnd, outerStart, outerCommon, outerEnd];
WHILE pointSectorRelation = OUTSIDESUBTEND DO
[innerStart, innerEnd] _ StepVertex[innerStart, innerEnd, innerOutline]; -- step inner polygon to catch up with outer polygon edge
CheckEdgeContact[];
SELECT edgeCompareStatus FROM
Disjoint => NULL;
ENDCASE => RETURN[Intersection, innerStart, innerCommon, innerEnd, outerStart, outerCommon, outerEnd];
pointSectorRelation _ PointSectorTest[ innerStart.coordinates, innerEnd.coordinates, innerCOM, outerEnd.coordinates ];
ENDLOOP;
};


IF checkExternal THEN IF EG.PointLineTest[ outerStart.coordinates, outerEnd.coordinates, innerStartFirst.coordinates] = RIGHTOFLINE THEN external _ TRUE; -- if inner polygon is external to outer polygon, then any vertex of the inner polygon (we arbitrarily picked innerStartFirst) must lie 'external' to at least one edge of the outer polygon. This test will eventually uncover such an outer edge if one exists.

[outerStart, outerEnd] _ StepVertex[outerStart, outerEnd, polygonStep];

IF outerStart = outerStartFirst THEN
done _ TRUE
ELSE
pointSectorRelation _ PointSectorTest[ innerStart.coordinates, innerEnd.coordinates, innerCOM, outerEnd.coordinates ]; 

ENDLOOP;

IF external THEN
RETURN[External, innerStart, innerCommon, innerEnd, outerStart, outerCommon, outerEnd]
ELSE
RETURN [Encloses, innerStart, innerCommon, innerEnd, outerStart, outerCommon, outerEnd];
};


FindInternalPolygonForPoint: PUBLIC PROC [v, w: Vertex, test: Point] RETURNS [pointSectorStatus: PointSectorRelation, y, z: Vertex] ~ {
polygonCOM: Point;
v5: Vertex _ v;
w5: Vertex _ w;
temp: Vertex;
polygonCOM _ CenterOfMass[v5, w5, FALSE]; -- COM of current internal polygon.
[pointSectorStatus, v5, w5] _ FindSubtendForPoint[ v5, w5, polygonCOM, test, FALSE];
WHILE pointSectorStatus = RIGHTRAYINTERIOR OR pointSectorStatus = LEFTRAYINTERIOR OR pointSectorStatus = 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
polygonCOM _ CenterOfMass[ v5, w5, FALSE];
[pointSectorStatus, v5, w5] _ FindSubtendForPoint[ v5, w5, polygonCOM, test, FALSE ];
ENDLOOP;
RETURN[ pointSectorStatus, v5, w5];
};

SearchInternalPolygonsForPoint: PUBLIC PROC [v, w: Vertex, test: Point] RETURNS [found: BOOL, y, z: Vertex] ~ {
polygonCOM: Point;
pointSectorStatus: PointSectorRelation;
v5: Vertex _ v;
w5: Vertex _ w;
temp: Vertex;
v5Tow5, w5Tov5: Adjacency;
[v5Tow5, w5Tov5] _ EG.FindAdjacency[v5, w5];
IF GetEdgeExterior[v5Tow5] THEN ERROR;
polygonCOM _ CenterOfMass[ v5, w5, FALSE]; -- COM of current internal polygon.
[pointSectorStatus, v5, w5] _ FindSubtendForPoint[ v5, w5, polygonCOM, test, FALSE ]; -- [v5,w5] defines a particular sector of this polygon
WHILE pointSectorStatus = RIGHTRAYINTERIOR OR pointSectorStatus = LEFTRAYINTERIOR OR pointSectorStatus = 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] _ EG.FindAdjacency[ v5, w5];
IF GetEdgeExterior[v5Tow5]  THEN RETURN[FALSE, v, w];
polygonCOM _ CenterOfMass[ v5, w5, FALSE];
[pointSectorStatus, v5, w5] _ FindSubtendForPoint[ v5, w5, polygonCOM, test, FALSE ];
ENDLOOP;
RETURN[TRUE, v5, w5];
};


ConvexPolygonOnOutline: PUBLIC PROC[prew2, w2, prew1, w1: Vertex] RETURNS [BOOL] = {
x, y, z: Vertex;
SELECT EG.PointLineTest[w2.coordinates, prew2.coordinates, w1.coordinates] FROM
RIGHTOFLINE => RETURN[FALSE];
LEFTOFLINE => NULL;
ONLINE => NULL; -- 180deg angle ok
ENDCASE;
SELECT EG.PointLineTest[prew2.coordinates, w1.coordinates, prew1.coordinates] FROM
RIGHTOFLINE => RETURN[FALSE];
LEFTOFLINE => NULL;
ONLINE => NULL;
ENDCASE;
x _ w1;  y _ prew1;  z _ PreviousOutlineVertex[y, x];
WHILE x # w2 DO
SELECT EG.PointLineTest[x.coordinates, y.coordinates, z.coordinates] FROM
RIGHTOFLINE => RETURN[FALSE];
LEFTOFLINE => NULL;
ONLINE => NULL;
ENDCASE;
x _ y;  y _ z;  z _ PreviousOutlineVertex[y, x];
ENDLOOP;
RETURN[TRUE];
};

GrowToConvexOutline: PUBLIC PROC[w2, v, w1: Vertex, verbosity: Verbosity _ NIL] RETURNS [v3, w3: Vertex] = {
ok: BOOL _ FALSE;
prew1, forw1, prew2, forw2: Vertex;  -- in the counterclockwise order on the outline (with respect to interior of figure), we have (prew2, w2, forw2, prew1, w1, forw1)
pointLineRelation: EG.PointLineRelation;
prew2 _ PreviousOutlineVertex[w2, v];
forw2 _ v;
prew1 _ v;
forw1 _ NextOutlineVertex[v, w1];

WHILE NOT ok DO
ok _ TRUE;

pointLineRelation _ EG.PointLineTest[w1.coordinates, w2.coordinates, prew2.coordinates];
WHILE pointLineRelation = LEFTOFLINE DO
ok _ FALSE;
IF NOT ConvexPolygonOnOutline[prew2, w2, prew1, w1] THEN {
JoinVertices[w1, w2, NIL, NIL, FALSE, FALSE, TRUE, FALSE];  -- [w1, w2] is an exterior edge
SetPolygonFields[w2, w1, FALSE, FALSE, NIL]; -- go around newly formed internal polygon setting leftRegionExterior = FALSE and leftClientData= NIL.
prew1 _ w2;  -- take account of presence of new edge joining w1 and w2
IF verbosity#NIL THEN verbosity.out.PutF["\nGrowToConvexOutline has joined vertices #%g and #%g\n", IO.int[w1.index], IO.int[w2.index]];
};
forw2 _ w2;  w2 _ prew2;  prew2 _ PreviousOutlineVertex[w2, forw2];
pointLineRelation _ EG.PointLineTest[w1.coordinates, w2.coordinates, prew2.coordinates];
ENDLOOP;

pointLineRelation _ EG.PointLineTest[w2.coordinates, w1.coordinates, forw1.coordinates];
WHILE pointLineRelation = RIGHTOFLINE DO
ok _ FALSE;
IF NOT ConvexPolygonOnOutline[ w2, forw2, w1, forw1] THEN {
JoinVertices[w2, w1, NIL, NIL, FALSE, FALSE, FALSE, TRUE];  -- [w1, w2] is an exterior edge
SetPolygonFields[w2, w1, FALSE, FALSE, NIL]; -- go around newly formed internal polygon setting leftRegionExterior = FALSE and leftClientData= NIL.
forw2 _ w1;  -- take account of presence of new edge joining w1 and w2
IF verbosity#NIL THEN verbosity.out.PutF["\nGrowToConvexOutline has joined vertices #%g and #%g\n", IO.int[w2.index], IO.int[w1.index]];
};
prew1 _ w1;  w1 _ forw1;  forw1 _ NextOutlineVertex[prew1, w1];
pointLineRelation _ EG.PointLineTest[w2.coordinates, w1.coordinates, forw1.coordinates];
ENDLOOP;

ENDLOOP;
JoinVertices[w2, w1, NIL, NIL, FALSE, FALSE, FALSE, TRUE];  -- [w1, w2] is an exterior edge
SetPolygonFields[w2, w1, FALSE, FALSE, NIL]; -- go around newly formed internal polygon setting leftRegionExterior = FALSE and leftClientData= NIL.
IF verbosity#NIL THEN verbosity.out.PutF["\nGrowToConvexOutline has joined vertices #%g and #%g\n", IO.int[w2.index], IO.int[w1.index]];
RETURN [w2, w1]
};

ConvexifyOutline: PUBLIC PROC [outlineStart, outlineEnd: Vertex, verbosity: Verbosity _ NIL] RETURNS [newOutlineStart, newOutlineEnd: Vertex _ NIL] ~ {
firstOutlineStart: Vertex _ outlineStart;
DO
outlineNext: Vertex _ NextVertex[outlineStart, outlineEnd, TRUE];
SELECT EG.PointLineTest[outlineStart.coordinates, outlineEnd.coordinates, outlineNext.coordinates] FROM
LEFTOFLINE, ONLINE => {
[outlineStart, outlineEnd] _ StepVertex[outlineStart, outlineEnd, TRUE];
IF outlineStart = firstOutlineStart THEN RETURN[outlineStart, outlineEnd];
};
RIGHTOFLINE => {
[outlineStart, outlineEnd] _ GrowToConvexOutline[outlineStart, outlineEnd, outlineNext, verbosity];
firstOutlineStart _ outlineStart;
};
ENDCASE;
ENDLOOP;
};



InternalPolygons: PUBLIC PROC [v, w: Vertex] RETURNS [RegionList] = {
vTow, wTov: Adjacency;
firstv: Vertex;
outline: BOOL _ FALSE;
polygonOutline: Imager.Trajectory;
clientData: REF;
vec: Imager.VEC;
region: Region;
outList: RegionList;

firstv _ v;
vec _ EG.ImagerVecFromPoint[v.coordinates];
polygonOutline _ ImagerPath.MoveTo[vec];

[ vTow, wTov ] _ EG.FindAdjacency[ v, w ];
clientData _ GetEdgeClientData[vTow]; -- only need to set state once

vec _ EG.ImagerVecFromPoint[w.coordinates];
polygonOutline _ ImagerPath.LineTo[polygonOutline, vec ];
vTow.visited _ TRUE;
WHILE w # firstv DO
[v, w] _ StepVertex[v,w, outline];
vec _ EG.ImagerVecFromPoint[w.coordinates];
polygonOutline _ ImagerPath.LineTo[polygonOutline, vec ];
[ vTow, wTov ] _ EG.FindAdjacency[ v, w ];
vTow.visited _ TRUE;
ENDLOOP;
region _ NEW[RegionRec _ [outline: polygonOutline, clientData: clientData] ];
outList _ LIST[region];

[v, w] _ StepVertex[v, w, outline];
[ vTow, wTov ] _ EG.FindAdjacency[ v, w ];
IF NOT GetEdgeExterior[wTov] THEN
IF NOT wTov.visited THEN TRUSTED {
outList _ LOOPHOLE[List.Append[LOOPHOLE[outList], LOOPHOLE[InternalPolygons[w, v]]]];
};
WHILE w # firstv DO
[v, w] _ StepVertex[v,w, outline];
[ vTow, wTov ] _ EG.FindAdjacency[ v, w ];
IF NOT GetEdgeExterior[wTov] THEN
IF NOT wTov.visited THEN TRUSTED {
outList _ LOOPHOLE[List.Append[LOOPHOLE[outList], LOOPHOLE[InternalPolygons[w, v]]]];
};
ENDLOOP;

RETURN[outList];
};

RegionBoundaryEdge: PROC [start, end: Vertex, isA: IsAProc] RETURNS [BOOL] ~ {
XOR: PROC[a, b: BOOLEAN] RETURNS[BOOLEAN] = {
IF (a AND b) THEN RETURN[FALSE];
IF (a OR b) THEN RETURN[TRUE];
RETURN[FALSE];
};
startToEnd, endToStart: Adjacency;
[startToEnd, endToStart] _ EG.FindAdjacency[start, end];
RETURN[XOR[isA[GetEdgeClientData[startToEnd]], isA[GetEdgeClientData[endToStart]]]];
};

NextRegionBoundaryEdge: PROC[start, end: Vertex, isA: IsAProc] RETURNS [next: Vertex] = {
A: AdjacencyList _ end.adjacentVertices;
WHILE A.first.vertex # start DO
A _ A.rest
ENDLOOP;
A _ A.rest;  next _ A.first.vertex;
WHILE NOT RegionBoundaryEdge[end, next, isA] DO
A _ A.rest;  next _ A.first.vertex;
ENDLOOP;
RETURN[next];
};

MaximalRegions: PUBLIC PROC [outlineVertex: Vertex, isA: IsAProc, verbosity: Verbosity _ NIL] RETURNS [outRegionList: RegionList] ~ {
MaximalRegionsSubr: PROC [v: Vertex, vertexVisitedValue: BOOLEAN, isA: IsAProc, inRegionList: RegionList, verbosity: Verbosity _ NIL] RETURNS [outRegionList: RegionList] ~ {
vAdjList: AdjacencyList _ v.adjacentVertices;
firstVertex, nextVertex: Vertex;
vToNext, nextToV: Adjacency;

outRegionList _ inRegionList;
IF verbosity#NIL THEN verbosity.out.PutF["\nMaximalRegionsSubr entered with argument  #%g\n", IO.int[v.index] ];

firstVertex _ nextVertex _ vAdjList.first.vertex; 
[vToNext, nextToV] _ EG.FindAdjacency[v, nextVertex] ;
IF RegionBoundaryEdge[v, nextVertex, isA] AND isA[GetEdgeClientData[vToNext]] AND NOT vToNext.visited THEN {
IF verbosity#NIL THEN verbosity.out.PutF["\nMaximalRegionsSubr finds region boundary edge [%g, %g]\n", IO.int[v.index], IO.int[nextVertex.index]];
outRegionList _ CONS[RegionBuilder[v, nextVertex, FALSE, vertexVisitedValue, isA, verbosity], outRegionList]; 
};
vAdjList _ vAdjList.rest;
nextVertex _ vAdjList.first.vertex;
WHILE nextVertex#firstVertex DO
[vToNext, nextToV] _ EG.FindAdjacency[v, nextVertex] ;
IF RegionBoundaryEdge[v, nextVertex, isA] AND isA[GetEdgeClientData[vToNext]] AND NOT vToNext.visited THEN {
IF verbosity#NIL THEN verbosity.out.PutF["\nMaximalRegionsSubr finds region boundary edge [%g, %g]\n", IO.int[v.index], IO.int[nextVertex.index]];
outRegionList _ CONS[RegionBuilder[v, nextVertex, FALSE, vertexVisitedValue, isA, verbosity], outRegionList]; 
};
vAdjList _ vAdjList.rest;
nextVertex _ vAdjList.first.vertex;
ENDLOOP;

v.visited _ vertexVisitedValue; -- now we can say that we've been here.

IF (nextVertex.visited # vertexVisitedValue) THEN outRegionList _  MaximalRegionsSubr[nextVertex, vertexVisitedValue, isA, outRegionList, verbosity];
vAdjList _ vAdjList.rest;
nextVertex _ vAdjList.first.vertex;
WHILE nextVertex#firstVertex DO
IF (nextVertex.visited # vertexVisitedValue) THEN outRegionList _  MaximalRegionsSubr[nextVertex, vertexVisitedValue, isA, outRegionList, verbosity];
vAdjList _ vAdjList.rest;
nextVertex _ vAdjList.first.vertex;
ENDLOOP;
RETURN[outRegionList];
};
IF NOT ThreeOrMoreVertices[outlineVertex] THEN RETURN[NIL];
outRegionList _ MaximalRegionsSubr[outlineVertex, NOT outlineVertex.visited, isA, NIL, verbosity];
ClearGraphEdgeFields[outlineVertex];
RETURN[outRegionList];
};
RegionBuilder: PUBLIC PROC [outlineStart, outlineEnd: Vertex, setOutlineVerticesVisited: BOOL, vertexVisitedValue: BOOLEAN, isA: IsAProc, verbosity: Verbosity _ NIL] RETURNS [region: Region] ~ {
SearchInternalPolygons: PROC [start, end: Vertex, vertexVisitedValue: BOOLEAN, isA: IsAProc, inHoles: RegionList] RETURNS [outHoles: RegionList] ~ {
firstStart: Vertex _ start;
startToEnd, endToStart: Adjacency;
nextStartToNextEnd, nextEndTonextStart: Adjacency;
polygonStep: BOOL _ FALSE;
outHoles _ inHoles;

IF verbosity#NIL THEN verbosity.out.PutF["\nSearchInternalPolygons entered with edge [%g, %g]\n", IO.int[start.index], IO.int[end.index]];

[ startToEnd, endToStart ] _ EG.FindAdjacency[start, end];
WHILE end # firstStart DO
[start, end] _ StepVertex[start, end, polygonStep];
[nextStartToNextEnd, nextEndTonextStart] _ EG.FindAdjacency[start, end];
nextStartToNextEnd.visited _ TRUE;
IF NOT IPVertex[start] THEN start.visited _ vertexVisitedValue;
startToEnd _ nextStartToNextEnd;
endToStart _ nextEndTonextStart;
ENDLOOP;
[start, end] _ StepVertex[start, end, polygonStep];
[nextStartToNextEnd, nextEndTonextStart] _ EG.FindAdjacency[start, end];
nextStartToNextEnd.visited _ TRUE;
IF NOT IPVertex[start] THEN start.visited _ vertexVisitedValue;

[ startToEnd, endToStart ] _ EG.FindAdjacency[start, end];
IF NOT GetEdgeIPEdge[startToEnd] THEN
IF NOT endToStart.visited THEN
IF RegionBoundaryEdge[end, start, isA] THEN {
IF verbosity#NIL THEN verbosity.out.PutF["\nSearchInternalPolygons finds boundary edge [%g, %g]\n", IO.int[end.index], IO.int[start.index]];
outHoles _ CONS[ RegionBuilder[end, start, TRUE, vertexVisitedValue, isA, verbosity], outHoles]
}
ELSE
outHoles _ SearchInternalPolygons[end, start, vertexVisitedValue, isA, outHoles];
WHILE end # firstStart DO
[start, end] _ StepVertex[start, end, polygonStep];
[startToEnd, endToStart] _ EG.FindAdjacency[start, end];
IF NOT GetEdgeIPEdge[startToEnd] THEN
IF NOT endToStart.visited THEN
IF RegionBoundaryEdge[end, start, isA] THEN {
IF verbosity#NIL THEN verbosity.out.PutF["\nSearchInternalPolygons finds boundary edge [%g, %g]\n", IO.int[end.index], IO.int[start.index]];
outHoles _ CONS[ RegionBuilder[end, start, TRUE, vertexVisitedValue, isA, verbosity], outHoles];
}
ELSE
outHoles _ SearchInternalPolygons[end, start, vertexVisitedValue, isA, outHoles];
ENDLOOP;
RETURN[outHoles];
};

polygonOutline: Imager.Trajectory _ NIL;
vec: Imager.VEC;
clientData: REF;
startToEnd, endToStart: Adjacency;
firstStart: Vertex _ outlineStart;
tempVertex: Vertex;
holes: RegionList;
firstTrajPoint: EG.Point;

IF verbosity#NIL THEN verbosity.out.PutF["\nRegionBuilder entered with region boundary edge [%g, %g]\n", IO.int[outlineStart.index], IO.int[outlineEnd.index]];

[ startToEnd, endToStart ] _ EG.FindAdjacency[outlineStart, outlineEnd];
SetEdgeIPEdge[startToEnd, TRUE];
startToEnd.visited _ TRUE;
IF setOutlineVerticesVisited THEN outlineEnd.visited _ vertexVisitedValue;

tempVertex _ NextRegionBoundaryEdge[outlineStart, outlineEnd, isA];
IF EG.PointLineTest[outlineStart.coordinates, tempVertex.coordinates, outlineEnd.coordinates] # ONLINE THEN { -- don't output this if collinear with prev and next
firstTrajPoint _ outlineEnd.coordinates;
vec _ EG.ImagerVecFromPoint[firstTrajPoint];
polygonOutline _ ImagerPath.MoveTo[vec];
};

WHILE outlineEnd # firstStart DO

outlineStart _ outlineEnd;  outlineEnd _ tempVertex;

[ startToEnd, endToStart ] _ EG.FindAdjacency[outlineStart, outlineEnd];
SetEdgeIPEdge[startToEnd, TRUE];
startToEnd.visited _ TRUE;
IF setOutlineVerticesVisited THEN outlineEnd.visited _ vertexVisitedValue;

tempVertex _ NextRegionBoundaryEdge[outlineStart, outlineEnd, isA];
IF EG.PointLineTest[outlineStart.coordinates, tempVertex.coordinates, outlineEnd.coordinates] # ONLINE THEN {
IF polygonOutline # NIL THEN { -- don't output this if collinear with prev and next
vec _ EG.ImagerVecFromPoint[outlineEnd.coordinates];
polygonOutline _ ImagerPath.LineTo[polygonOutline, vec];
}
ELSE {
firstTrajPoint _ outlineEnd.coordinates;
vec _ EG.ImagerVecFromPoint[firstTrajPoint];
polygonOutline _ ImagerPath.MoveTo[vec];
};
};

ENDLOOP;

outlineStart _ outlineEnd;  outlineEnd _ tempVertex;
vec _ EG.ImagerVecFromPoint[firstTrajPoint];
polygonOutline _ ImagerPath.LineTo[polygonOutline, vec]; -- close trajectory

clientData _ GetEdgeClientData[startToEnd];

holes _ SearchInternalPolygons[outlineStart, outlineEnd, vertexVisitedValue, isA, NIL];

region _ NEW[RegionRec _ [outline: polygonOutline, clientData: clientData, holes: holes] ];
};

ropeFromEdgeData: EG.RopeFromEdgeData ~ {
cEGEdgeData: CEGEdgeData _ NARROW[edgeData];
IF cEGEdgeData = NIL THEN RETURN["NIL"];
out _ Rope.Cat[Convert.RopeFromBool[cEGEdgeData.exteriorEdge], ",", Convert.RopeFromBool[cEGEdgeData.intersectionPolygonEdge], "," ];
out _ Rope.Concat[out, clientProc1[cEGEdgeData.clientData] ];
};

DumpGraph: PUBLIC PROC [v: ConvexEuclideanGraph, ropeFromClientData: RopeFromClientData, filename: Rope.ROPE] ~ {
EG.DumpGraph[v, ropeFromEdgeData, filename, ropeFromClientData];
};
edgeDataFromRope: EG.EdgeDataFromRope ~ {
dataStream: IO.STREAM _ IO.RIS[in];
char: CHAR;
exteriorEdge, intersectionPolygonEdge: BOOLEAN;
clientData: REF;
DataFromRopeFail: PUBLIC ERROR [subclass: ATOM _ $Unspecified] = CODE;
[]_ dataStream.SkipWhitespace[];  char _ dataStream.PeekChar[];
IF char = 'N THEN {
[] _ dataStream.GetChar[];  -- toss N
IF dataStream.GetChar[] # 'I THEN DataFromRopeFail[$IExpected];
IF dataStream.GetChar[] # 'L THEN DataFromRopeFail[$LExpected];
RETURN[NIL]
};
IF char # 'T AND char # 'F THEN DataFromRopeFail[$TorFExpected];
exteriorEdge _ IO.GetBool[dataStream];
IF dataStream.GetChar[] # ', THEN DataFromRopeFail[$commaExpected];
char _ dataStream.PeekChar[];
IF char # 'T AND char # 'F THEN DataFromRopeFail[$TorFExpected];
intersectionPolygonEdge _ IO.GetBool[dataStream];
IF dataStream.GetChar[] # ', THEN DataFromRopeFail[$commaExpected];
char _ dataStream.PeekChar[];
IF char = 'N THEN {
[] _ dataStream.GetChar[];  -- toss N
IF dataStream.GetChar[] # 'I THEN DataFromRopeFail[$IExpected];
IF dataStream.GetChar[] # 'L THEN DataFromRopeFail[$LExpected];
clientData _ NIL;
}
ELSE {
index: INT _ IO.GetIndex[dataStream];
rope: Rope.ROPE _ Rope.Substr[in, index];
clientData _ clientProc1[rope];
};
RETURN[NEW[CEGEdgeDataRec _ [exteriorEdge: exteriorEdge, intersectionPolygonEdge: intersectionPolygonEdge, clientData: clientData] ]  ];
};

ReadIOGraphFromFile: PUBLIC PROC [filename: Rope.ROPE, clientDataFromRope: ClientDataFromRope, MessageStream: IO.STREAM] RETURNS [iOGraph: EG.IOGraph] ~ {
RETURN[EG.ReadIOGraphFromFile[filename, edgeDataFromRope, MessageStream, clientDataFromRope] ];
};

GraphFromIOGraph: PUBLIC PROC [iOGraph: EG.IOGraph] RETURNS [v: ConvexEuclideanGraph, numberVertices: CARDINAL] ~ {

vertexList, lastCell: VertexList;
scratchVertexList: VertexList;
scratchIOGraph: EG.IOGraph;
vertex: Vertex;
adjacentVertex: Vertex;
aList, aListLast: AdjacencyList;
adjacency : Adjacency;
ioAList: EG.IOAdjacencyList;
iOAdjacency: EG.IOAdjacency;

vertex _  NEW[EG.VertexRec _ [coordinates: iOGraph.first.coordinates, 
index: iOGraph.first.index, adjacentVertices: NIL, data: NIL, visited: FALSE] ];
lastCell _ vertexList _ LIST[vertex];
numberVertices _ 1;
scratchIOGraph _ iOGraph.rest;
WHILE scratchIOGraph # NIL DO
vertex _  NEW[EG.VertexRec _ [coordinates: scratchIOGraph.first.coordinates, 
index: scratchIOGraph.first.index, adjacentVertices: NIL, data: NIL, visited: FALSE] ];
lastCell.rest _ LIST[vertex];  lastCell _ lastCell.rest;
numberVertices _ numberVertices + 1;
scratchIOGraph _ scratchIOGraph.rest;
ENDLOOP;
scratchVertexList _ vertexList;  -- Need to keep vertexList intact for searching

WHILE scratchVertexList # NIL DO
vertex _ scratchVertexList.first;
ioAList _ iOGraph.first.adjacentVertices;
aList _ NIL;  -- initialize 
WHILE ioAList # NIL DO -- assumes adjacent vertices occur in reverse clockwise order; this loop will restore correct order.
iOAdjacency _ ioAList.first;
adjacentVertex _ EG.SearchVertexList[vertexList, iOAdjacency.vertex ]; -- these calls assume call by value, i.e. that vertexList always points to the head of the list
adjacency _ NEW[EG.AdjacencyRec _ [vertex: adjacentVertex,  data: iOAdjacency.data, visited: FALSE]  ];
IF GetEdgeExterior[adjacency] THEN v _ vertex; -- identify vertex on outline of figure
aList _ CONS[adjacency, aList];  -- adjacencies in ioAList are in backwards (counterclockwise) order; using CONS here puts them back in clockwise order.
IF aList.rest = NIL THEN aListLast _ aList; -- save pointer for setting circularity
ioAList _ ioAList.rest;
ENDLOOP;
aListLast.rest _ aList;  -- make list circular
vertex.adjacentVertices _ aList; -- attach to current vertex
scratchVertexList _ scratchVertexList.rest; 
iOGraph _ iOGraph.rest;  -- advance scratchVertexList and iOGraph in lock step
ENDLOOP;

RETURN[ v, numberVertices ];
};

GraphFromFile: PUBLIC PROC [filename: Rope.ROPE, clientDataFromRope: ClientDataFromRope, MessageStream: IO.STREAM] RETURNS [v: ConvexEuclideanGraph, numberVertices: CARDINAL] ~ {
[v, numberVertices] _ GraphFromIOGraph[ReadIOGraphFromFile[filename, clientDataFromRope, MessageStream] ];
};


END.

#vConvexEuclideanGraphsImpl.mesa
Last Edited by: Arnon, June 20, 1985 4:37:28 pm PDT


**************  Hull Computation  **************
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.

**************  Graph Structure **************


**************  Graph Traversal  **************
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).

**************  Edge Fields  **************






Clear visited and intersectionPolygonEdge fields of edges of this polygon
Go around edges again; check each to see if an unprocessed polygon lies across it, if so, recursive call on the flipped edge. 



[v,w] is a counterclockwise oriented edge of a polygon contained in the outline of the current figure.  Clear the visited fields of all edges of all polygons interior to a Vertex, assumed by this particular ClearEdgeVisitedFields to be an Vertex. Uses Depth First Search.
Clear visited fields of edges of this polygon
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.
Clears IPEdge and visited fields of all edges in the Graph pointed to by v.
Go around adjacencies clearing fields.
Go around adjacencies again, making recursive calls for unvisited vertices.
**************  Convex (internal) polygon operations **************
[v,w] is a counterclockwise oriented edge on the polygon
We assume that all vertices, and all edges, in the previously existing polygon have the same visited values, which are propagated to vertices and edges in the new structure.
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.  If test = centerOfMass, then status = EQUALCOM and [t, u] _ [v, w].
[v,w] is a counterclockwise oriented edge on the polygon, must have at least 2 (3?) vertices.
Determine which side of [innerStart, innerEnd] outerStart is on.
General claim: assuming that any edge of outer polygon that contacts an edge of inner polygon starts at an outerStart that is outside the inner polygon, then that outerStart must lie to the right of the inner edge that is contacted.  Proof: outerStart is external to inner polygon, hence to the right of line of support through any inner edge contacted by any outer edge starting at outerStart.
If we arrive here, then outerEnd is in RIGHTRAYINTERIOR, LEFTRAYINTERIOR, SUBTENDINTERIOR of current subtend of inner polygon, and there is no contact of [outerStart, outerEnd] with inner polygon.
**************  Graph Searching **************

**************  Graph Outline  **************
We assume that the vertices are given to us in counterclockwise order (with respect to figure interior) along the outline of the figure.

w2, v, and w1 are assumed to be in counterclockwise order (with respect to the interior of the outline) on an outline. [v3,w3] is a counterclockwise-oriented (with respect to the interior of the figure) edge on the new outline.
It is assumed that [w2, v, w1] is a nontrivial triangle, i.e. that the outline is not in the neighborhood of [w2, v, w1] have a convex outline, in particular that w1 is to the right of the line from w2 through v.
The triangle [w2, v, w1] is the initial convex polygon. WHILE the figure does not (in the neighborhood of w2, v, w1) have a convex outline, the algorithm enlarges this polygon, breaking it off (i.e. inserting an edge) and starting a new polygon as necessary.
Invariant assumed to hold at the beginning of this loop: w1 and w2 have the property that an edge joining them will "close off", i.e. form, a convex polygon "on the side of [w1,w2] towards the interior of the figure". 
Move w2 backwards (clockwise) along the outline until edges [w1, w2] added to the outline will give a "local convex extension" of the outline, i.e. the outline will satisfy convexity check from before w2 up to and including w1.  For each successive w2 value, we check whether adding edges [w1, prew2] will leave a convex polygon; if not, we put in edges [w1, w2] (by loop invariant, this will yield a convex polygon). 
Move w1 forwards (counterclockwise) along the outline until edges [w2, w1] added to the outline will give a "local convex extension" of the outline, i.e. the outline will satisfy convexity check from before w2 up through and beyond w1.  For each successive w1 value, we check whether adding edges [w2, forw1] will leave a convex polygon; if not, we put in edges [w2, w1] (by loop invariant, this will yield a convex polygon). 
**************  Region Extraction  **************
Extract clientData
Set visited fields of edges of this polygon, and build polygonOutline
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.
Basically a Depth First Search, pausing to build an entire region each time a region boundary edge is discovered.
Go around adjacencies, looking for region boundary edges.
Go around adjacencies again, making recursive calls for unvisited vertices.

Set edge visited fields, and vertex visited fields of non-outline vertices.
Go around edges again, checking opposite facing edges of non-outline edges.  If such an edge is not yet visited, then if a region boundary edge, call RegionBuilder recursively to build a new hole, else call SearchInternalPolygons recursively.  
Trace outline, setting edge IPEdge and visited fields, setting outline vertex visited fields if called for by setOutlineVerticesVisited, and building outline trajectory.  Redundant vertices are omitted from outline trajectory.

Get back to initial outlineStart, outlineEnd
Client data of outline - holes.
Search for holes

****************  Input and Output ****************


Convert an IOGraph to a Vertex. The particular Vertex 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 IOGraph.
Create initial list of vertex indices
Fill in links to adjacent vertices
�Ê0÷˜š
œ™J™3J™—š
Ïk	˜	Jš
œ˜Jš
œ˜Jš�œ
˜Jš
œ˜Jš
œ˜Jš
œ˜J˜Jš
œ˜Jš
œ˜Jš
œ˜—J˜
head2šœ�œ
�˜(Inameš�œ
�œD˜NJš�œ˜J˜—Jš	œ�œ
�œ
�œ�œ)˜EJ˜Icode™J™0šÏn
œ�œ
�œ�œ˜DMš
œ™M™ÄJšœ�œ˜Jšœ�œ˜Jšœ�œ
˜Jšœ
�œ
˜Jšœ�œ˜Jš
œ˜Jšœ�œ�œ	�œ˜*Jš
œ˜Jš
œ˜Jšœ�œ
˜Jšœ	�œ
�œÏc(™<šž
œ�œ�œ˜#Mš
œ/™/M˜š�œ�œ
�œ�˜Mš
œ"˜"Mš�œ
˜—M˜—š
žœ�œ�œ�œ�œ˜3Jš�œ�œ�œ
�œ�œ
�œ�œ˜3M˜—M˜Jšœ)�œ™EM™Jš
œ™M˜š�œ�œ
�˜J˜
Jš
œ)˜)Mšœ,�œ
�œ�œ"�œ�œ�œ�œ"�œ�œ™±
J˜Jš�œ
˜—J˜Jš
œj™jM˜š�œ
�˜Jš
�œ
�œ@�œ
�œ
�œ
˜VJ˜Jš�œ
˜—Jš�œ
�œ@�œ
�œ
�œŸ-˜…
Jš
œ˜Jš
œ˜Jšœ�œ%˜/Jšœ	�œ&˜1Jšœ�œ%˜/Jšœ	�œ%˜0Jšœ�œ ˜)Jšœ�œ"�œ!˜WMšœ/�œ
�œ�œ�œ�œ�œ�œ�œ�œ™¬
J˜J™5š�œ�œ�˜Jšœ�œ3�œ2˜}Jš�œ
˜—J˜Mš
œZ™ZMšŸ"œ	Ÿ%™Pš�œ�
œ
�œ
�˜š�œ�œ
�œ�˜š�œ
�œ �œ�˜Bšœ�œ
�œ"�œ�˜Rš
œ˜šœ�œ �œ ˜[J˜
—Jšœ�œ"�œ#˜Y—š
œ˜Jšœ�œ
˜
—šœ�œ
�œ$�˜=Mš�œ�œŸ(˜=Mš�œ�œŸ$˜;Mš�œ�œ
˜—Mš�œ�œ
˜—šœ�œ
�œ"�œ�˜Oš
œ˜Jšœ�œ
˜—š
œ˜šœ�œ �œ ˜[J˜
—Jšœ�œ"�œ#˜Y—Mšœ�œŸ5˜NMš�œ�œ
˜—šœ�œ
�œ �œ�˜OMšœ�œŸ(˜DšœŸ˜š�œ
�œ"�œ�˜Dš
œ˜Jšœ�œ
˜—š
œ˜Jšœ�œ
˜
—šœ�œ
�œ$�˜=Mš�œ�œŸ(˜=Mš�œ�œŸ"˜9Mš�œ�œ
˜—Mš�œ�œ
˜——Mšœ�œ
Ÿ"˜4Mš�œ�œ
˜—Mš�œ�œ
˜—Mšœ)�œ	�œ™QM˜š�œ�œ˜Jš
œ˜Jš
œ ˜ Jš
œ˜J˜—Jš�œ
˜—Jš�œ
˜—J˜Mš
œ ™ š�œ�œ�™Mšœ9�œ
�œ�œ"�œ�œ�œ�œ"�œ�œ�œ�œ �œ%™žJš�œ
™—J˜J˜Jš
œ1™1J˜JšœŸq˜„
š�œ�œ
�œ�˜#š�œ
�œ?�˜IJšœŸ(˜BMš�œ
˜—š�œ
�œ^�œ
�˜tMš
œ˜Mš
œ˜Mš�œ
˜—Mš
œ˜Mš�œ
˜—J™Jš
œ#™#Jšœ�œ
˜š�œ�
œ
�œ�˜Jšœ�œ�œ.�œ3˜wJš�œ
˜—M˜M˜—J™J™.šžœ�œ
�œ�œ�œ�œ˜JMšœ�œ
˜Jšœ�œŸ˜2Jš�œ�œ)�œŸ˜_Jš�œ�œ\Ÿ˜�
Jš�œ˜J˜M˜—šžœ�œ
�œ*�œ�œ
�œ�œ�œ�œ�œ�œ˜˜
Mšœ�œe˜ƒ
Jš�œ:˜<M˜M˜—šžœ�œ
�œ&�œ�œ�œ˜pMš
œ˜Mš
œ ˜ Mšœ�œ(˜6Mšœ�œ˜&Mšœ�œ˜Mšœ�œ˜Mš
œj˜jMš�œ˜Mš
œj˜jMš
œj˜jMš�œ˜Mš
œj˜jMš�œ˜
M˜M˜—šžœ�œ
�œ6�œ�œ&�œ�œ*�œ�œ(�œ�œ˜ù
Mšœ!�œ}˜¡
Mšœ!�œ}˜¡
Jš�œ;˜=Jš�œ;˜=J˜J˜J™—J™™/J˜—š
ž
œ�œ
�œ�œ�œ˜UJš�œ$˜*Jš
œ˜J˜—š
ž
œ�œ
�œ�œ�œ˜NJš�œ	�œ�œ˜KJš�œ˜
Jš
œ˜J˜—š
žœ�œ
�œ�œ�œ˜RJš�œ	�œ �œ ˜SJš�œ˜
Jš
œ˜J˜—šžœ�œ
�œ�œ˜FJš
œ&˜&Jš
œ ˜ š�œ�˜Jš
œ ˜ Jš�œ
˜—Jš�œ˜
Jš
œ˜J˜—šžœ�œ
�œ�œ˜CJš
œ&˜&š�œ�˜Jš
œ
˜
Jš�œ
˜—Jš�œ˜Jš
œ˜J˜—šžœ�œ
�œ
�œ˜LJš
œ­™­Jš
œ(˜(Jš�œ
�œ�œ�œ
˜?J˜J˜J˜—šžœ�œ
�œ�œ˜IJš
œ°™°Jš
œ&˜&š�œ�˜Jš
œ
˜
Jš�œ
˜—Jš�œ˜J˜J˜—šžœ�œ
�œ�œ˜HJš
œ�™�Jš
œ&˜&Jš
œ ˜ š�œ�˜Jš
œ ˜ Jš�œ
˜—Jš�œ˜
Jš
œ˜J˜—J™J™+šžœ�œ
�œ�œ�œ
�œ˜RJšœ�œ˜3Jš�œ˜J˜J™—š
žœ�œ
�œ�œ
�œ˜IJšœ�œ˜3Jš
œ˜J˜J™—šžœ�œ
�œ�œ�œ�œ˜_Jš
œ"˜"Jš
œ˜Jšœ�œ˜<Jš
œ$˜$Jš�œ�œ�œ
˜-š�œ�˜Jšœ&�œ˜-Jšœ�œ˜<Jš
œ$˜$Jš�œ�œ�œ
˜-Jš�œ
˜—J˜M™—š
žœ�œ
�œ�œ	�œ˜NJšœ�œ˜3Jš�œ˜!J˜M˜—šžœ�œ
�œ �œ˜EJšœ�œ˜3Jš
œ!˜!J˜J™—š
ž
œ�œ
�œ�œ	�œ˜LJšœ�œ˜3Jš�œ&˜,J˜J™—šž
œ�œ
�œ �œ˜CJšœ�œ˜3Jš
œ,˜,J˜J™—šžœ�œ
�œ�œ˜DJš
œ"˜"Jš
œ˜Jšœ�œ˜<Jš
œ!˜!š�œ�˜Jšœ%�œŸ˜<Jšœ�œ˜<Jš
œ!˜!Jš�œ
˜—J˜J˜—šžœ�œ
�œ˜0Jš
œ"˜"Jš
œ˜Jšœ	�œ�œ
˜J˜Jš
œI™IJšœ�œ˜6Jšœ�œ
˜Jšœ�œ˜!š�œ�˜Jš
œ"˜"Jšœ�œ˜6Jšœ�œ
˜Jšœ�œ˜!Jš�œ
˜—J˜Jš
œ~™~Jš
œ"˜"Jšœ�œ˜6Jš�œ�œ˜3š�œ�˜Jš
œ"˜"Jšœ�œ˜6Jš�œ�œ˜3Jš�œ
˜—J˜M™—šžœ�œ
�œ"�œ#˜gMš
œE˜Eš�œ
�œ"�˜-Mš
œ˜Mš�œ
˜—Mš�œ˜!M˜M™—š
žœ�œ
�œ
�œ�œ˜4Jš
œ0˜0Jš
œ,˜,Jš
�œ�œ
�œ
�œ
�œ˜(Mš�œ"�œ
�œ
�œ˜6Jš
œ˜š�œ�˜Mš�œ"�œ
�œ
�œ˜6Jš
œ˜Jš�œ
˜—Jš�œ
�œ˜J˜M™—šžœ�œ
�œ˜7Jš
œ�™�Jš
œ˜Jš
œ˜Jšœ	�œ�œ
˜J˜Jš
Ÿ-™-Jšœ�œ˜*Jšœ�œ
˜š�œ�˜Jš
œ"˜"Jšœ�œ˜*Jšœ�œ
˜Jš�œ
˜—J˜Jš
œÒ
™Ò
Jš
œ#˜#Jšœ�œ˜*š	�œ�œ
�œ
�œ�˜6Jš
œ˜—š
�˜Jšœ�œ
˜—š�œ�˜Jš
œ"˜"Jšœ�œ˜*š	�œ�œ
�œ
�œ�˜6Jš
œ˜—š
�˜Jšœ�œ
˜—Jš�œ
˜—J˜J˜—šžœ�œ
�œ˜1J™Kšžœ�œ�œ˜.Jš
œ-˜-Jš
œ ˜ Jš
œ˜J˜Jš
œ&™&Jš
œ2˜2Jšœ�œ˜6Jšœ�œ
˜Jšœ�œ˜Jš
œ˜Jš
œ#˜#š�œ�˜Jšœ�œ˜6Jšœ�œ
˜Jšœ�œ˜Jš
œ˜Jš
œ#˜#Jš�œ
˜—JšœŸ'˜AJ˜Jš
œK™KJš�œ%�œ ˜KJš
œ˜Jš
œ#˜#š�œ�˜Jš�œ%�œ ˜KJš
œ˜Jš
œ#˜#Jš�œ
˜—J˜J˜—Mš�œ�œ
�œ�œ
�œ
�œ
�œ	�œ˜OM˜J˜—šžœ�œ
�œG�œ�œ�œ˜”
Jš
œ˜Jš
œ"˜"Jš
œ˜Jšœ�œ˜<Jšœ�œ˜&Jš
œ-˜-Jš
œC˜CJš
œ)˜)š�œ�˜Jšœ%�œŸ˜<Jšœ�œ˜<Jšœ�œ˜&Jš
œ-˜-Jš
œC˜CJš
œ)˜)Jš�œ
˜—J˜J˜—šžœ�œ
�œG�œ�œ�œ�œ˜‘
Jš
œ˜Jš
œ"˜"Jš
œ˜Jšœ�œ˜:Jšœ�œ˜&Jš
œ-˜-Jš
œC˜CJš
œ)˜)š�œ�˜Jšœ&�œŸ˜>Jšœ�œ˜<Jšœ�œ˜&Jš
œ-˜-Jš
œC˜CJš
œ)˜)Jš�œ
˜—J˜J˜J˜—M˜J™Cš
žœ�œ
�œ�œ�œ˜MJ•commentTRUE™8Jš
œ˜Jšœ�œ˜ Jšœ�œ˜ Jšœ�œ˜Jšœ�œ˜š�œ�˜Jšœ�œ#˜*Jšœ�œ#˜+J˜
J˜$Jš�œ
˜—Jšœ�œ ˜)Jš�œ�œ�œ ˜OJ˜J˜—šžœ�œ
�œ�œ�œ�œ�œ˜qMš
œ˜Mš
œ˜š�œ�˜Mš
œ˜Mš
œ/˜/Mš�œ
˜—M˜M˜—šžœ�œ
�œA�œ�œ�œ"˜”
Jš
œ­
™­
Jšœ�œ�œ�œ˜=Jšœ
�œ
˜Jš
œ$˜$Jšœ�œ
˜Jš�œ
�œ
�œ
�œ
�œŸ˜JJš
œ&˜&š�œ�œ
�œŸ˜4Jšœ�œ�œ�œ˜?Jš	œ�œ�œ�œ�œ˜7Jš�œ˜J˜—Jšœ�œ&˜EJš
œ'˜'Jšœ;Ÿ˜XJš�œ)˜+Jšœ�œ�œ ˜KJšœ�œ�œ�œ˜CJšœ�œ�œ ˜JJšœ�œ�œ�œ˜Bš�œ�œ˜Jšœ�œ�œ ˜KJšœ�œ�œ�œ˜CJ˜—Jš�œ˜J˜J˜J˜—š
žœ�œ
�œ6�œ�œ˜}Jš	ŸJœ&Ÿaœ
ŸœŸEœ
Ÿ™ÃJšœ�œ�œ9˜mš�œ�˜Mš�œ�œ�œ˜(Mš�
œ�œ�œ˜!Mš�œ�œ�œ˜0Mš�œ�œ�œ˜'Mš�œ�œ�œ˜'Mš�œ�œ�œ˜(š�
œ˜Jšœ�œ8˜Nš�œ�˜Mš�œ�œ�œ˜(Mš�œ�œ�œ˜/Mš�œ�œ�œ˜&Mš�œ�œ�œ˜&Mš�
œ�œ�œ˜'š�œ˜Mšœ�œ�œ/˜[š�œ�˜Mš�œ�œ
�œ˜&Mš�
œ�œ
�œ˜%Mš�œ�œ
�œ˜'Mš�œ
˜—M˜—Mš�œ�œŸ˜/M˜——Mš�œ
˜—M˜J˜—š
žœ�œ
�œ3�œ�œ0˜‘
J–TRUEšœ��œ™žJš
œn˜nš�œ�œ
�˜-J˜%Jš
œY˜YJš�œ
˜—Jš�œ˜$J˜J˜—šžœ�œ
�œI�œ	�œE�œ˜Î
Jš
œ'˜'Jš
œ'˜'Jšœ�œ�œ
˜Jšœ€
�œŸ6˜¿
š�œ
�œ�œ
˜š
�œ�œ
�œ�œ
�œ�œ
�˜zJš�œ
�œ6˜A—Jšœ>�œ˜Eš�œ �˜&Jšœ�˜—š
�˜Jšœ…
�œ˜�
—Jš�œ
˜—Jš�œ
�œ<˜HM˜—šž
œ�œ
�œ�œ�œ�œ˜MJ–TRUE™]Jš
œ˜Jš
œ&˜&Jš
�œ�œ�œ
�œ
�œ˜$š�œ
�œ<�œ
Ÿ˜^Mš�œ�œ
�œ˜Mš�
œ�œ
˜Mš�œ�œŸ˜.Mš�œ
˜—Jšœ.Ÿ˜:š�œ�˜š�œ
�œ<�œ
Ÿ˜^Mš�œ�œ
�œ˜Mš�
œ�œ
˜Mš�œ�œŸ˜/Mš�œ
˜—J˜-Jš�œ
˜—Jš�œ
�œ˜
J˜J˜—šžœ�œ
�œ?�œ/�œ�œ�œ}�œ˜¬Jšœ
�œ�œ
˜Jš
œ%˜%Jš
œ%˜%Jš
œ)˜)Jšœ�œ˜(Jšœ�œ˜.Jš
œ˜Jšœ
�œ�œ
˜Jšœ�œ�œ
˜J˜šžœ�œ�œ˜!M˜Mš
œ@™@Mšœ�œU˜kM˜Mš�œ�˜M˜š�œ"Ÿ2˜ZM˜—š�
œ"Ÿ˜/M™ŠM˜—š�œ˜Jšœ�œ?˜Uš�œ�˜š
œ˜Jš
œ˜Mš
œ<˜<Mš
œ˜Mš
œA˜AJš
œ˜—š
œ˜Jš
œ˜Jš
œN˜NMšœ>Ÿ2˜pJš
œ˜—š
œ˜Jš
œ˜Mš
œ<˜<Mš
œ˜Mš
œ=˜=Jš
œ˜—š
œ˜Mš
œ˜Jš
œP˜PMšœCŸ2˜uJš
œ˜—š
œ˜Jšœ�œl˜}Jš
œF˜FJš
œF˜FJ˜—š
œ˜Mš
œ˜Jš
œN˜NMšœ>Ÿ2˜pJš
œ˜—Jšœ�œŸ˜,Jš�œ
˜—J˜J˜Jš�œ
˜M˜—MšœŸ˜M˜—Jš
œv˜vJ˜š�œ
�œ�˜J˜š�œ�˜M˜š�œ�œ�œ�œ
˜;M˜—š�œŸK˜XMš
œ˜š�œ�˜Mšœ�œ
˜Jš�œ�œU˜f—š�œ�œ
�˜-JšœIŸ9˜‚
Mš
œ˜š�œ�˜Mšœ�œ
˜Jš�œ�œU˜f—Jš
œv˜vJš�œ
˜—J˜—J˜—š
π
™Ä
J˜—Jš�œ�œ
�œ
�œ]�œ
�œ�œŸ�˜›J˜Jš
œG˜GJ˜š�œ�˜$Jšœ�˜—š
�˜Jš
œw˜w—J˜Jš�œ
˜J˜—š�œ
�˜Jš�œP˜V—š
�˜Jš�œR˜X—J˜J˜—M˜J™.šžœ�œ
�œ�œ;˜‡
Jš
œ˜Jš
œ˜Jš
œ˜Jš
œ
˜
Jšœ"�œŸ#˜MJšœM�œ˜Tš�œ�œ
�œ�œ
�œ�œ
�œŸ?˜¼
Jšœ!Ÿ)˜JJšœ#�œ˜*JšœM�œ˜UJš�œ
˜—Jš�œ˜#M˜M˜—š
žœ�œ
�œ�œ	�œ˜oJš
œ˜Jš
œ'˜'Jš
œ˜Jš
œ˜Jš
œ
˜
Jš
œ˜Jšœ�œ˜,Jš�œ�œ
�œ
˜&Jšœ#�œŸ#˜NJšœM�œŸ6˜Œ
š�œ�œ
�œ�œ
�œ�œ
�œŸ?˜¼
Jšœ!Ÿ)˜JJšœ�œ˜.Jš�œ�œ
�œ
�œ˜5Jšœ#�œ˜*JšœM�œ˜UJš�œ
˜—Jš�œ
�œ
˜M˜M˜—J™™-J˜—š
žœ�œ
�œ�œ�œ˜TJ–TRUE™ˆ
Jš
œ˜š�œ
�œB�˜OMš�œ�œ
�œ˜Mš�
œ�œ
˜Mš�œ�œŸ˜"Mš�œ
˜—š�œ
�œE�˜RMš�œ�œ
�œ˜Mš�
œ�œ
˜Mš�œ�œ
˜Mš�œ
˜—Jš
œ5˜5š�œ�˜š�œ
�œ<�˜IMš�œ�œ
�œ˜Mš�
œ�œ
˜Mš�œ�œ
˜Mš�œ
˜—Jš
œ0˜0Jš�œ
˜—Jš�œ
�œ˜
J˜J˜J™—š
žœ�œ
�œ+�œ�œ˜lJ–TRUEš
ϋ
™ã
Jš
œÔ
™Ô
Jš
œ‚™‚Jšœ�œ�œ
˜Jšœ�œŸ‚
˜§
Jšœ�œ˜(Jš
œ%˜%J˜
J˜
Jš
œ!˜!J˜J™Ú
š�œ
�œ�˜Jšœ�œ
˜
J˜J™¢Jšœ�œB˜Xš�œ�
œ
�˜'Jšœ�œ
˜š�œ
�œ.�œ˜:Jšœ�œ�œ�œ�œ�œ�œŸ˜[Jšœ�œ�œ�œŸf˜“
Jšœ
Ÿ9˜FJš
�œ�œ
�œO�œ�œ˜ˆ
J˜—Jš
œC˜CJšœ�œB˜XJš�œ
˜—J˜Jš
œª™ªJšœ�œB˜Xš�œ�œ
�˜(Jšœ�œ
˜š�œ
�œ/�œ˜;Jšœ�œ�œ�œ�œ�œ�œŸ˜[Jšœ�œ�œ�œŸf˜“
Jšœ
Ÿ9˜FJš
�œ�œ
�œO�œ�œ˜ˆ
J˜—Jš
œ?˜?Jšœ�œB˜XJš�œ
˜J˜—Jš�œ
˜—Jšœ�œ�œ�œ�œ�œ�œŸ˜[Jšœ�œ�œ�œŸf˜“
Jš
�œ�œ
�œO�œ�œ˜ˆ
Jš�œ	˜J˜J˜—šžœ�œ
�œ;�œ�œ+�œ˜—
Jš
œ)˜)š
�˜Jšœ;�œ˜Aš�œ
�œZ�˜gš�
œ�œ˜MšœB�œ˜HMš�œ"�œ
�œ˜JM˜—š�œ˜Jš
œc˜cJš
œ!˜!J˜—Mš�œ
˜—Mš�œ
˜—˜J˜——J˜™1M˜—šžœ�œ
�œ�œ˜EJš
œ˜Jš
œ˜Jšœ	�œ�œ
˜Jš
œ"˜"Jšœ�œ
˜Jšœ�œ
˜Jš
œ˜Jš
œ˜J˜Jš
œ˜Jšœ�œ#˜+Jš
œ(˜(J˜Jš
œ™Jšœ�œ˜*Jšœ&Ÿ˜DJ˜JšŸœŸ:™EJšœ�œ#˜+Jš
œ9˜9Jšœ�œ
˜š�œ�˜Jš
œ"˜"Jšœ�œ#˜+Jš
œ9˜9Jšœ�œ˜*Jšœ�œ
˜Jš�œ
˜—Jšœ	�œA˜MJšœ
�œ	˜J˜Jš
œÔ
™Ô
Jš
œ#˜#Jšœ�œ˜*š�œ
�œ�˜!š�œ
�œ�œ
�œ˜"Jšœ
�œ
�œ�œ˜UJ˜——š�œ�˜Jš
œ"˜"Jšœ�œ˜*š�œ
�œ�˜!š�œ
�œ�œ
�œ˜"Jšœ
�œ
�œ�œ˜UJ˜——Jš�œ
˜—J˜Jš�œ
˜J˜J˜—šžœ�œ$�œ�œ˜Nš
�œ�œ�œ�œ
�œ˜-Jš
�œ�œ�œ
�œ
�œ˜ Jš
�œ�œ�œ
�œ
�œ˜Jš�œ
�œ˜Jš
œ˜—Jš
œ"˜"Jšœ�œ˜8Jš�œ
�œJ˜TM˜M˜—šžœ�œ#�œ˜YJš
œ(˜(š�œ�˜Jš
œ
˜
Jš�œ
˜—Jš
œ#˜#š�œ
�œ$�˜/Jš
œ#˜#Jš�œ
˜—Jš�œ˜
Jš
œ˜—M˜š
žœ�œ
�œ>�œ�œ ˜…
š
žœ�œ!�œA�œ�œ ˜­
Jš
œq™qJš
œ-˜-Jš
œ ˜ Jš
œ˜J˜Jš
œ˜Jš�œ�œ
�œI�œ˜pJ˜Jš
œ9™9Jš
œ2˜2Jšœ�œ˜6š
�œ(�œ!�œ
�œ�œ˜lJš
�œ�œ
�œR�œ�œ˜’
Jšœ�œ�œ7˜nJ˜—Jš
œ˜Jš
œ#˜#š�œ�˜Jšœ�œ˜6š
�œ(�œ!�œ
�œ�œ˜lJš
�œ�œ
�œR�œ�œ˜’
Jšœ�œ�œ7˜nJ˜—Jš
œ˜Jš
œ#˜#Jš�œ
˜J˜—Jšœ Ÿ'˜GJ˜Jš
œK™KJš�œ+�œd˜•
Jš
œ˜Jš
œ#˜#š�œ�˜Jš�œ+�œd˜•
Jš
œ˜Jš
œ#˜#Jš�œ
˜—Jš�œ˜J˜—Jš
�œ
�œ$�œ
�œ
�œ˜;Jšœ2�œ�œ
˜bJš
œ$˜$Jš�œ˜J˜J™—šž
œ�œ
�œ?�œ�œ'�œ�œ˜Â
šžœ�œ*�œ%�œ˜”
Jš
œ˜Jš
œ"˜"Jš
œ2˜2Jšœ
�œ�œ
˜Jš
œ˜J˜Jš
�œ�œ
�œM�œ�œ˜Š
J˜Jš
œK™KJšœ�œ˜:š�œ�˜Jš
œ3˜3Jšœ+�œ˜HJšœ�œ
˜"Jš�œ
�œ�œ$˜?Jš
œ ˜ Jš
œ ˜ Jš�œ
˜—Jš
œ3˜3Jšœ+�œ˜HJšœ�œ
˜"š�œ
�œ�œ$˜?J˜—Jš
ϙ
™ô
Jšœ�œ˜:š�œ
�œ�˜%š�œ
�œ�˜š�œ%�˜-Jš
�œ�œ
�œO�œ�œ˜Œ
Jšœ�œ�œ0˜_J˜
—š
�˜Jš
œQ˜Q———š�œ�˜Jš
œ3˜3Jšœ�œ˜8š�œ
�œ�˜%š�œ
�œ�˜š�œ%�˜-Jš
�œ�œ
�œO�œ�œ˜Œ
Jšœ�œ�œ1˜`J˜
—š
�˜Jš
œQ˜Q———Jš�œ
˜—Jš�œ˜M˜M˜—Jšœ$�œ
˜(Jšœ�œ
˜Jšœ�œ
˜Jš
œ"˜"Jš
œ"˜"Jš
œ˜J˜Jšœ�œ˜J˜Jš
�œ�œ
�œT�œ�œ˜Ÿ
J˜Jš
ω
™â
J™Jšœ�œ)˜HJšœ�œ˜ Jšœ�œ
˜Jš�œ�œ)˜JJ˜Jš
œC˜Cš	�œ
�œ[�œ
�œŸ4˜¢
Mš
œ(˜(Jšœ�œ$˜,Mš
œ(˜(M˜M˜—š�œ�˜ J˜Jš
œ4˜4J˜Jšœ�œ)˜HJšœ�œ˜ Jšœ�œ
˜Jš�œ�œ)˜JJ˜Jš
œC˜Cš�œ
�œ[�œ
�œ˜mš�œ�œ
�œŸ4˜SJšœ�œ,˜4Mš
œ8˜8M˜
—š
�˜Mš
œ(˜(Jšœ�œ$˜,Mš
œ(˜(M˜—M˜—J˜Jš�œ
˜—J˜Jš
œ,™,Jš
œ4˜4Jšœ�œ$˜,Mšœ9Ÿ˜LJ˜Jš
œ™Jš
œ+˜+J˜Jš
œ™JšœR�œ˜WJ˜Jšœ	�œO˜[J˜J˜—J™™3J™—šœ�œ˜)Mšœ�œ˜,Mš�œ�œ
�œ
�œ˜(Mš
œ…
˜…
Mš
œ=˜=M˜M˜—šž	œ�œ
�œR�œ˜qJš�œ>˜@J˜M™—šœ�œ˜)Mš	œ�œ
�œ�œ
�œ˜#Jšœ�œ
˜Jšœ'�œ
˜/Jšœ�œ
˜Jš	œ�œ
�œ�œ�œ
˜FJš
œ?˜?š�œ�œ˜JšœŸ	˜%Jš�œ�œ˜?Jš�œ�œ˜?Jš�œ
�œ
˜J˜—Jš�œ�œ�œ!˜@Jšœ�œ˜&Jš�œ�œ"˜CJš
œ˜Jš�œ�œ�œ!˜@Jšœ�œ˜1Jš�œ�œ"˜CJš
œ˜š�œ�œ˜JšœŸ	˜%Jš�œ�œ˜?Jš�œ�œ˜?Jšœ
�œ
˜J˜
—š�œ˜Jšœ�œ�œ˜%Jšœ�œ˜)Jš
œ˜J˜—Mš�œ
�œ~˜ˆ
M˜M˜—šžœ�œ
�œ�œ9�œ
�œ�œ�œ
˜š
Jš�œ
�œV˜_J˜J˜—šžœ�œ
�œ�œ
�œ+�œ˜sJš
œÈ
™È
J˜Jš
œ!˜!Jš
œ˜Jšœ�œ	˜Jš
œ˜Jš
œ˜Jš
œ ˜ Jš
œ˜Jšœ	�œ˜Jšœ
�œ
˜J˜Jš
œ%™%šœ
�œ
�œ6˜FJšœ.�œ�œ�œ˜P—Jšœ�œ	˜%Jš
œ˜Jš
œ˜š�œ�œ
�˜šœ
�œ
�œ=˜MJšœ5�œ�œ�œ˜W—Jšœ�œ$˜8Jš
œ$˜$Jš
œ%˜%Jš�œ
˜—Jšœ!Ÿ/˜PJ˜Jš
Ÿ"™"š�œ�œ
�˜ Jš
œ!˜!Jš
œ)˜)Jšœ�œŸ˜š�œ�œ
�œ
Ÿd˜{Jš
œ˜Jšœ�œ4Ÿ_˜¦
Jšœ�œ
�œK�œ˜gJš�œ�œ
Ÿ'˜VJšœ�œŸw˜˜
Jš�œ�œ
�œŸ'˜SJš
œ˜Jš�œ
˜—JšœŸ˜.Jšœ!Ÿ˜<Jš
œ,˜,JšœŸ5˜NJš�œ
˜—J˜Jš�œ˜J˜J˜—šž
œ�œ
�œ�œ9�œ
�œ�œ+�œ˜²
Jš
œj˜jJ˜J˜M˜—Jš�œ
˜J˜—…—®@­