DIRECTORY
IO,
Rope,
RatNums,
EuclideanGraphs,
ConvexEuclideanGraphs,
ConvexCombiner;

ConvexCombinerImpl: CEDAR PROGRAM
IMPORTS IO, RatNums, EuclideanGraphs, ConvexEuclideanGraphs
EXPORTS ConvexCombiner

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



Combiner: PUBLIC PROC[currentEnd, inputEnd: Vertex, inputClientData: REF, clientDataCombiner: ClientDataCombiner, verbosity: Verbosity _ NIL] RETURNS [combinedEnd: Vertex]={
intersectionPolyStart, intersectionPolyEnd: Vertex;
[combinedEnd, intersectionPolyStart, intersectionPolyEnd] _ CombineGeometry[currentEnd, inputEnd, TRUE, verbosity];
IF intersectionPolyStart#NIL THEN {
CombineClientData[intersectionPolyStart, intersectionPolyEnd, inputClientData, clientDataCombiner, verbosity];
CEG.ClearGraphIPEdges[intersectionPolyStart, intersectionPolyEnd];
}; -- assume no intersectionPolygonEdge fields set if intersectionPolyStart = NIL.
};
CombineGeometry: PUBLIC PROC[ currentEnd, inputEnd: Vertex, setIntersectionPolygonEdges: BOOL _ TRUE, verbosity: Verbosity _ NIL] RETURNS [combinedEnd, intersectionPolyStart, intersectionPolyEnd: Vertex]={

currentStart, inputStart, combinedStart: Vertex;
currentOutlineCOM, inputCOM: Point;
pointSectorStatus: CEG.PointSectorRelation;
polygonCompareStatus: CEG.ConvexPolygonCompareStatus;
firstInputVertex: Vertex;
done: BOOL _ FALSE;
currentPrevious, currentCommon, currentNext, inputPrevious, inputCommon, inputNext: Vertex;
inputClientData: REF;
startToEnd, endToStart: EG.Adjacency;
outlineStart, outlineEnd, newOutlineStart, newOutlineEnd: Vertex;

IF inputEnd = NIL THEN RETURN[currentEnd, NIL, NIL];
IF currentEnd = NIL THEN RETURN[inputEnd, NIL, NIL];
IF NOT CEG.ThreeOrMoreVertices[currentEnd] OR NOT CEG.ThreeOrMoreVertices[inputEnd] THEN ERROR;

IF currentEnd.visited # inputEnd.visited THEN EG.SetFigureVisitedValues[inputEnd, currentEnd.visited];

currentStart _ CEG.SpecialPreviousOutlineVertex[currentEnd];
firstInputVertex _ inputStart _ CEG.SpecialPreviousOutlineVertex[inputEnd];
[ startToEnd, endToStart ] _ EG.FindAdjacency[ inputStart, inputEnd ];
inputClientData _ CEG.GetEdgeClientData[startToEnd]; 

currentOutlineCOM _ CEG.CenterOfMass[ currentStart, currentEnd, TRUE];
inputCOM _ CEG.CenterOfMass[ inputStart, inputEnd, FALSE];
[pointSectorStatus, currentStart, currentEnd] _ CEG.FindSubtendForPoint[ currentStart, currentEnd, currentOutlineCOM, inputStart.coordinates, TRUE];

outlineStart _ currentStart;  outlineEnd _ combinedEnd _ currentEnd;

WHILE NOT done DO
SELECT pointSectorStatus FROM

SUBTENDINTERIOR, RIGHTRAYINTERIOR, LEFTRAYINTERIOR => {
pointLineRelation: EG.PointLineRelation;

[polygonCompareStatus, currentPrevious, currentCommon, currentNext, inputPrevious, inputCommon, inputNext] _ CEG.ConvexPolygonCompare[ 
innerCOM: currentOutlineCOM,
innerStart: currentStart,
innerEnd: currentEnd,
innerOutline: TRUE,
outerStart: inputStart,
outerEnd: inputEnd,
checkExternal: TRUE
];

SELECT polygonCompareStatus FROM

Intersection => {
pointLineRelation _ EG.PointLineTest[currentCommon.coordinates, currentPrevious.coordinates, inputNext.coordinates]; 
SELECT pointLineRelation FROM
ONLINE, LEFTOFLINE => {
outlineStart _ currentCommon;  outlineEnd _ currentNext;
BoundaryContactOnly[inputCommon, inputNext, currentCommon, verbosity];
[combinedStart, combinedEnd] _ CEG.ConvexifyOutline[outlineStart, outlineEnd, verbosity];
RETURN[combinedEnd, NIL, NIL];
};
RIGHTOFLINE => {
[outlineStart, outlineEnd, intersectionPolyStart, intersectionPolyEnd] _ InputIntersectsCurrent[inputCommon, inputNext, currentCommon, verbosity];
[combinedStart, combinedEnd] _ CEG.ConvexifyOutline[outlineStart, outlineEnd, verbosity];
RETURN[combinedEnd, intersectionPolyStart, intersectionPolyEnd];
};
ENDCASE;
};

Encloses => {
CEG.SetPolygonIPEdges[currentStart, currentEnd, TRUE];
CEG.SetOutwardOutlineEdgeFields[currentStart, currentEnd, FALSE, FALSE, inputClientData];

PolygonEnclosesPolygon[currentOutlineCOM, currentStart, currentEnd, inputStart, inputEnd, verbosity];  -- should pass in data field values???

RETURN [inputEnd, currentStart, currentEnd];
};

External => {
[outlineStart, outlineEnd] _ InputExternalToCurrent[currentStart, currentEnd, inputStart, inputEnd, currentOutlineCOM, inputCOM, verbosity];
[combinedStart, combinedEnd] _ CEG.ConvexifyOutline[outlineStart, outlineEnd, verbosity];
RETURN [combinedEnd, NIL, NIL];
};

ENDCASE;
};

SECTORINTERIOR, RIGHTSPOKEINTERIOR, LEFTSPOKEINTERIOR, EQUALCOM =>  {

inputStartStatus: CEG.PointSectorRelation;
internalStart, internalEnd: Vertex;
found: BOOL;

[inputStartStatus, internalStart, internalEnd] _ CEG.FindInternalPolygonForPoint[currentStart, currentEnd, inputStart.coordinates];
SELECT inputStartStatus FROM
EQUALRIGHTVERTEX => {
currentCommon _ internalStart;
[newOutlineStart, newOutlineEnd, intersectionPolyStart, intersectionPolyEnd] _ InputIntersectsCurrent[inputStart, inputEnd, currentCommon, verbosity];
IF newOutlineStart#NIL THEN { outlineStart _ newOutlineStart; outlineEnd _ newOutlineEnd };
[combinedStart, combinedEnd] _ CEG.ConvexifyOutline[outlineStart, outlineEnd, verbosity];
RETURN [combinedEnd, intersectionPolyStart, intersectionPolyEnd];
};
EQUALLEFTVERTEX => {
currentCommon _ internalEnd;
[newOutlineStart, newOutlineEnd, intersectionPolyStart, intersectionPolyEnd] _ InputIntersectsCurrent[inputStart, inputEnd, currentCommon, verbosity];
IF newOutlineStart#NIL THEN { outlineStart _ newOutlineStart; outlineEnd _ newOutlineEnd };
[combinedStart, combinedEnd] _ CEG.ConvexifyOutline[outlineStart, outlineEnd, verbosity];
RETURN [combinedEnd, intersectionPolyStart, intersectionPolyEnd];
};
POLYGONEDGEINTERIOR => {
currentCommon _ CEG.InsertVertexInEdges[internalStart, internalEnd, inputStart.coordinates];
[newOutlineStart, newOutlineEnd, intersectionPolyStart, intersectionPolyEnd] _ InputIntersectsCurrent[inputStart, inputEnd, currentCommon, verbosity];
IF newOutlineStart#NIL THEN { outlineStart _ newOutlineStart; outlineEnd _ newOutlineEnd };
[combinedStart, combinedEnd] _ CEG.ConvexifyOutline[outlineStart, outlineEnd, verbosity];
RETURN [combinedEnd, intersectionPolyStart, intersectionPolyEnd];
};
ENDCASE;
[found, inputStart, inputEnd, internalStart, internalEnd] _ CEG.VertexExternalToPolygon[inputCOM, inputStart, inputEnd, internalStart, internalEnd];
IF NOT found THEN ERROR;
[polygonCompareStatus, inputPrevious, inputCommon, inputNext, currentPrevious, currentCommon, currentNext] _ CEG.ConvexPolygonCompare[ 
innerCOM: inputCOM,
innerStart: inputStart,
innerEnd: inputEnd,
innerOutline: FALSE,
outerStart: internalStart,
outerEnd: internalEnd,
checkExternal: FALSE
];

SELECT polygonCompareStatus FROM

Intersection => {
[newOutlineStart, newOutlineEnd, intersectionPolyStart, intersectionPolyEnd] _ InputIntersectsCurrent[inputCommon, inputNext, currentCommon, verbosity];
IF newOutlineStart#NIL THEN { outlineStart _ newOutlineStart; outlineEnd _ newOutlineEnd };
[combinedStart, combinedEnd] _ CEG.ConvexifyOutline[outlineStart, outlineEnd, verbosity];
RETURN [combinedEnd, intersectionPolyStart, intersectionPolyEnd];
};

Encloses => {
currentInternalClientData: REF;

[startToEnd, endToStart] _ EG.FindAdjacency[internalStart, internalEnd];
currentInternalClientData _ CEG.GetEdgeClientData[startToEnd];
CEG.SetPolygonClientData[inputStart, inputEnd, currentInternalClientData];

CEG.SetPolygonIPEdges[inputStart, inputEnd, TRUE];
CEG.SetOutwardOutlineEdgeFields[inputStart, inputEnd, FALSE, FALSE, currentInternalClientData];
PolygonEnclosesPolygon[inputCOM, inputStart, inputEnd, internalStart, internalEnd, verbosity];
RETURN [combinedEnd, inputStart, inputEnd]; -- leave combinedEnd _ currentEnd, its initial assignment
};

ENDCASE => ERROR;
};

POLYGONEDGEINTERIOR, EQUALRIGHTVERTEX, EQUALLEFTVERTEX => {
[inputStart, inputEnd] _ CEG.StepVertex[ inputStart, inputEnd, TRUE ]; -- move to next edge of input polygon, looking for first one that goes off the outline of current figure.
IF inputStart =  firstInputVertex THEN
done _ TRUE
ELSE
[pointSectorStatus, currentStart, currentEnd] _ CEG.FindSubtendForPoint[ currentStart, currentEnd, currentOutlineCOM, inputStart.coordinates, TRUE];
};

ENDCASE => ERROR;

ENDLOOP;

CEG.SetPolygonIPEdges[currentStart, currentEnd, TRUE];
RETURN [currentEnd, currentStart, currentEnd];
};

CombineClientData: PUBLIC PROC[intersectionPolyStart, intersectionPolyEnd: Vertex, inputClientData: REF, clientDataCombiner: ClientDataCombiner, verbosity: Verbosity _ NIL] = {
currentClientData, combinedClientData: REF;
start: Vertex _ intersectionPolyStart;
end: Vertex _ intersectionPolyEnd;
firstIntersection: Vertex _ start;
startToEnd, endToStart: EG.Adjacency;
outline: BOOL _ FALSE;

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

[startToEnd, endToStart] _ EG.FindAdjacency[start, end];
currentClientData _ CEG.GetEdgeClientData[startToEnd];
combinedClientData _ clientDataCombiner[currentClientData, inputClientData];
CEG.SetPolygonClientData[start, end, combinedClientData, TRUE];

WHILE end # firstIntersection DO
[start, end] _ CEG.StepVertex[start, end, outline];
[ startToEnd, endToStart ] _ EG.FindAdjacency[ start, end ];
IF NOT CEG.GetEdgeIPEdge[startToEnd] THEN
IF NOT endToStart.visited THEN
CombineClientData[end, start, inputClientData, clientDataCombiner, verbosity];
ENDLOOP;
};

InputIntersectsCurrent: PUBLIC PROC [inputStart, inputEnd, currentVertex: Vertex, verbosity: Verbosity _ NIL] RETURNS [outlineStart, outlineEnd: Vertex _ NIL, intersectionPolyStart, intersectionPolyEnd: Vertex] ~ {
firstIntersection: Vertex _ currentVertex;
returnedToFirstIntersection: BOOL _ FALSE;
previousCurrentVertex, nextCurrentVertex: Vertex;
lensInExterior: BOOL;

WHILE NOT returnedToFirstIntersection DO

[returnedToFirstIntersection, lensInExterior, currentVertex, nextCurrentVertex, inputEnd] _ HandleVertexContact[firstIntersection, inputStart, inputEnd, currentVertex, verbosity];

IF NOT returnedToFirstIntersection THEN
IF lensInExterior THEN {
outlineStart _ currentVertex;  outlineEnd _ inputEnd;
[returnedToFirstIntersection, previousCurrentVertex, currentVertex, inputStart, inputEnd] _ LensDecomposition[ firstIntersection, currentVertex, nextCurrentVertex, inputEnd, lensInExterior, TRUE, verbosity];
}
ELSE
[returnedToFirstIntersection, inputStart, inputEnd, previousCurrentVertex, currentVertex] _ LensDecomposition[ firstIntersection, currentVertex, inputEnd, nextCurrentVertex, lensInExterior, TRUE, verbosity];

IF NOT returnedToFirstIntersection THEN
[inputStart, inputEnd] _ CEG.StepVertex[inputStart, inputEnd, FALSE];

ENDLOOP;

intersectionPolyEnd _ CEG.IPVertexToEdge[firstIntersection];

RETURN[outlineStart, outlineEnd, firstIntersection, intersectionPolyEnd]; 

};

InputExternalToCurrent: PUBLIC PROC[ currentStart, currentEnd, inputStart, inputEnd: Vertex, currentOutlineCOM, inputCOM: Point, verbosity: Verbosity _ NIL] RETURNS [outlineStart, outlineEnd: Vertex] = {
status: CEG.PointSectorRelation;
pointLineRelation: EG.PointLineRelation;
edge1, edge2: EG.Adjacency;
[status, inputStart, inputEnd] _ CEG.FindSubtendForPoint[inputStart, inputEnd, inputCOM, currentOutlineCOM, TRUE];
[status, currentStart, currentEnd] _ CEG.FindSubtendForPoint[ currentStart, currentEnd, currentOutlineCOM, inputStart.coordinates, TRUE];
CEG.JoinVertices[inputStart, currentEnd, NIL, NIL, FALSE, FALSE, TRUE, TRUE, FALSE, FALSE]; -- Edges [currentEnd, inputStart] are both exterior.
IF verbosity#NIL THEN verbosity.out.PutF["\nInputExternalToCurrent joins vertices #%g and #%g\n", IO.int[currentEnd.index], IO.int[inputStart.index]];
pointLineRelation _ EG.PointLineTest[currentEnd.coordinates, inputStart.coordinates, inputEnd.coordinates];
WHILE pointLineRelation = RIGHTOFLINE DO
[edge1, edge2] _ EG.FindAdjacency[currentEnd, inputStart];
CEG.SetEdgeExterior[edge2, FALSE];  -- [inputStart, currentEnd] has become internal
[edge1, edge2] _ EG.FindAdjacency[inputStart, inputEnd];
CEG.SetEdgeExterior[edge2, FALSE]; -- [inputEnd, inputStart] has become internal
[inputStart, inputEnd] _ CEG.StepVertex[inputStart, inputEnd, FALSE];
CEG.JoinVertices[currentEnd, inputStart, NIL, NIL, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE]; -- [inputStart, currentEnd] is an exterior edge
IF verbosity#NIL THEN verbosity.out.PutF["\nInputExternalToCurrent joins vertices #%g and #%g\n", IO.int[currentEnd.index], IO.int[inputStart.index]];
pointLineRelation _ EG.PointLineTest[currentEnd.coordinates, inputStart.coordinates, inputEnd.coordinates];
ENDLOOP;
RETURN [currentStart, currentEnd]
};

PolygonEnclosesPolygon: PUBLIC PROC[ innerCOM: Point, innerStart, innerEnd, outerStart, outerEnd: Vertex, verbosity: Verbosity _ NIL] = {
pointSectorStatus: CEG.PointSectorRelation;
nextInner, prevInner, thisInner: Vertex;
pointLineRelation: EG.PointLineRelation;
outerClientData: REF; 
startToEnd, endToStart: EG.Adjacency;
returnedToFirstIntersection: BOOL _ FALSE;
innerPrevious, innerCommon, outerPrevious, outerCommon: Vertex; -- dummies

[startToEnd, endToStart] _ EG.FindAdjacency[outerStart, outerEnd];
outerClientData _ CEG.GetEdgeClientData[startToEnd];

[pointSectorStatus, innerStart, innerEnd] _ CEG.FindSubtendForPoint[ innerStart, innerEnd, innerCOM, outerStart.coordinates, FALSE];

nextInner _ innerEnd;
thisInner _ innerStart;
prevInner _ CEG.PreviousOutlineVertex[thisInner, nextInner];
pointLineRelation _ EG.PointLineTest[outerStart.coordinates, thisInner.coordinates, prevInner.coordinates];
WHILE pointLineRelation = LEFTOFLINE DO
nextInner _ thisInner;
thisInner _ prevInner;
prevInner _ CEG.PreviousOutlineVertex[thisInner, nextInner];
pointLineRelation _ EG.PointLineTest[outerStart.coordinates, thisInner.coordinates, prevInner.coordinates];
ENDLOOP;
CEG.JoinVertices[thisInner, outerStart, outerClientData, outerClientData];
IF verbosity#NIL THEN verbosity.out.PutF["\nPolygonEnclosesPolygon joins vertices #%g and #%g\n", IO.int[thisInner.index], IO.int[outerStart.index]];
pointLineRelation _ EG.PointLineTest[outerStart.coordinates, thisInner.coordinates, nextInner.coordinates];
WHILE pointLineRelation = RIGHTOFLINE DO
prevInner _ thisInner;
[thisInner, nextInner] _ CEG.StepVertex[thisInner, nextInner, TRUE]; -- outline step, since inner figure could be current figure
CEG.JoinVertices[thisInner, outerStart, outerClientData, outerClientData];
IF verbosity#NIL THEN verbosity.out.PutF["\nPolygonEnclosesPolygon joins vertices #%g and #%g\n", IO.int[thisInner.index], IO.int[outerStart.index]];
pointLineRelation _ EG.PointLineTest[outerStart.coordinates, thisInner.coordinates, nextInner.coordinates];
ENDLOOP;

[returnedToFirstIntersection, innerPrevious, innerCommon, outerPrevious, outerCommon] _ LensDecomposition[outerStart, outerStart, thisInner, outerEnd, TRUE, FALSE, verbosity];  -- lensInExterior = TRUE is the right thing, so that we don't set states of "intersection polygon edges". setIntersectionPolygonEdges = FALSE, since we assume already done by caller, and presence of cone makes it tricky in any case.
IF NOT returnedToFirstIntersection THEN ERROR;
};


HandleVertexContact: PUBLIC PROC [firstIntersection, inputStart, inputEnd, currentVertex: Vertex, verbosity: Verbosity _ NIL] RETURNS [returnedToFirstIntersection: BOOL, nextLensInExterior: BOOL _ FALSE, currentCommonVertex, nextCurrentVertex, nextInputVertex: Vertex _ NIL] ~ {
overlap: BOOL;
overlappedCurrentVertex: Vertex;
distStartCurrent, distStartInput: RN.RatNum;
newVertex, tempVertex: Vertex;
thisToNext, nextToThis: EG.Adjacency;
XOR: PROC[a, b: BOOLEAN] RETURNS[BOOLEAN] = {
IF (a AND b) THEN RETURN[FALSE];
IF (a OR b) THEN RETURN[TRUE];
RETURN[FALSE];
};
returnedToFirstIntersection _ FALSE;
nextInputVertex _ inputEnd;
[overlap, overlappedCurrentVertex] _ EG.TestEdgeOverlap[currentVertex, inputEnd];
WHILE overlap AND NOT returnedToFirstIntersection DO

distStartInput _ EG.DistanceSquare[inputStart.coordinates, inputEnd.coordinates];
distStartCurrent _ EG.DistanceSquare[currentVertex.coordinates, overlappedCurrentVertex.coordinates];
SELECT RN.RatNumCompare[distStartInput, distStartCurrent] FROM
ratGreater => {
newVertex _ CEG.InsertVertexInEdges[inputStart, inputEnd, overlappedCurrentVertex.coordinates];
nextInputVertex _ inputEnd;
inputEnd _ newVertex;
nextCurrentVertex _ overlappedCurrentVertex;
};
ratEqual =>  {
nextInputVertex _ CEG.NextPolygonVertex[inputStart, inputEnd];  -- meaningless if returnedToFirstIntersection; that's ok.
nextCurrentVertex _ overlappedCurrentVertex;
};
ratLess => {
newVertex _ CEG.InsertVertexInEdges[currentVertex, overlappedCurrentVertex, inputEnd.coordinates];
nextCurrentVertex _ newVertex;
nextInputVertex _ CEG.NextPolygonVertex[inputStart, inputEnd];
};
ENDCASE;

IF EG.CountAdjacencies[inputStart] > 1 THEN {
tempVertex _ EG.SplitVertex[inputStart, inputEnd];
EG.MergeVertices[currentVertex, tempVertex];
};

EG.DeleteVertex[inputStart];

[thisToNext, nextToThis] _  EG.FindAdjacency[currentVertex, nextCurrentVertex];
CEG.SetEdgeIPEdge[thisToNext, TRUE];
IF verbosity#NIL THEN verbosity.out.PutF["\nHandleVertexContact marks edge [ #%g , #%g ] on intersection polygon\n", IO.int[currentVertex.index], IO.int[nextCurrentVertex.index]];

inputStart _ inputEnd;  inputEnd _ nextInputVertex; -- move to next input polygon edge
currentVertex _ nextCurrentVertex;  -- now inputStart and currentVertex are next pair of common coordinate, unmerged vertices of input polygon and current figure
returnedToFirstIntersection _  inputStart = firstIntersection;
IF XOR[returnedToFirstIntersection, currentVertex = firstIntersection] THEN ERROR; -- consistency check 
[overlap, overlappedCurrentVertex] _ EG.TestEdgeOverlap[currentVertex, inputEnd];  -- meaningless if returnedToFirstIntersection; that's ok.
ENDLOOP;
IF returnedToFirstIntersection THEN RETURN[TRUE];

EG.MergeVertices[currentVertex, inputStart];

nextCurrentVertex _ CEG.PreviousPolygonVertex[currentVertex, nextInputVertex];
[thisToNext, nextToThis] _  EG.FindAdjacency[currentVertex, nextCurrentVertex];
nextLensInExterior _ CEG.GetEdgeExterior[nextToThis];
IF NOT nextLensInExterior THEN
nextCurrentVertex _ CEG.NextPolygonVertex[nextInputVertex, currentVertex];
RETURN[FALSE, nextLensInExterior, currentVertex, nextCurrentVertex, nextInputVertex];
};

LensDecomposition: PUBLIC PROC[firstIntersection, lensStart, innerEnd, outerEnd: Vertex, lensInExterior: BOOL, setIntersectionPolygonEdges: BOOL _ TRUE, verbosity: Verbosity _ NIL] RETURNS [returnedToFirstIntersection: BOOL, innerPrevious, innerCommon, outerPrevious, outerCommon: Vertex] = {
polygonStepping: BOOL = FALSE;
outlineStepping: BOOL = TRUE;
innerStart, outerStart, outerNext, innerNext: Vertex;
innerStartToInnerEnd, innerEndToInnerStart, outerStartToOuterEnd, outerEndToOuterStart: EG.Adjacency;
intersection: Point;
pointDirectedEdgeRelation: EG.PointDirectedEdgeRelation;
pointLineRelation: EG.PointLineRelation;
edgeCompareStatus: EG.BiasedEdgeCompareStatus;
lensClientData: REF;

UpdateInnerEdgeFields: PROC ~ INLINE {
[innerStartToInnerEnd, innerEndToInnerStart] _ EG.FindAdjacency[innerStart, innerEnd];
CEG.SetEdgeExterior[innerEndToInnerStart, FALSE];
CEG.SetEdgeClientData[innerEndToInnerStart, lensClientData];
IF NOT lensInExterior THEN CEG.SetEdgeClientData[innerStartToInnerEnd, lensClientData];
IF setIntersectionPolygonEdges THEN {
CEG.SetEdgeIPEdge[innerStartToInnerEnd, TRUE];
IF verbosity#NIL THEN verbosity.out.PutF["\nLensDecomposition marks edge [ #%g , #%g ] on intersection polygon\n", IO.int[innerStart.index], IO.int[innerEnd.index]];
};
};

innerStart _ outerStart _ lensStart;
[outerStartToOuterEnd, outerEndToOuterStart] _ EG.FindAdjacency[ outerStart, outerEnd ];
lensClientData _ CEG.GetEdgeClientData[outerStartToOuterEnd]; -- clientData for lens is clientData of outer polygon
outerNext _ CEG.NextVertex[outerStart, outerEnd, polygonStepping]; 
innerNext _ CEG.NextVertex[innerStart, innerEnd, outlineStepping];
DO  -- WHILE NOT EndOfLens

pointDirectedEdgeRelation _ EG.PointDirectedEdgeTest[innerStart.coordinates, innerEnd.coordinates, outerNext.coordinates];
WHILE pointDirectedEdgeRelation = RIGHTOFEDGE DO
outerStart _ outerEnd;  [outerEnd, outerNext] _ CEG.StepVertex[outerEnd, outerNext, polygonStepping];
pointDirectedEdgeRelation _ EG.PointDirectedEdgeTest[innerStart.coordinates, innerEnd.coordinates, outerNext.coordinates];
ENDLOOP;
edgeCompareStatus _ EG.BiasedEdgeCompare[outerEnd, outerNext, innerStart, innerEnd];
SELECT edgeCompareStatus FROM

OuterEndInInner => {
innerEnd _ CEG.InsertVertexInEdges[innerStart, innerEnd, outerNext.coordinates];
UpdateInnerEdgeFields[];
RETURN[FALSE, innerStart, innerEnd, outerEnd, outerNext];
};

OuterEndEqInnerEnd => {
UpdateInnerEdgeFields[];
IF innerEnd = outerNext THEN -- returnedToFirstIntersection
RETURN[TRUE, innerStart, innerEnd, outerEnd, outerNext]
ELSE
RETURN[FALSE, innerStart, innerEnd, outerEnd, outerNext];
};

ProperIntersection => {
intersection _ EG.IntersectLines[innerStart.coordinates, innerEnd.coordinates, outerEnd.coordinates, outerNext.coordinates];
innerEnd _ CEG.InsertVertexInEdges[innerStart, innerEnd, intersection];
outerNext _ CEG.InsertVertexInEdges[outerEnd, outerNext, intersection];
UpdateInnerEdgeFields[];
RETURN[FALSE, innerStart, innerEnd, outerEnd, outerNext]
};

InnerEndInOuter => {
outerNext _ CEG.InsertVertexInEdges[outerEnd, outerNext, innerEnd.coordinates];
UpdateInnerEdgeFields[];
RETURN[FALSE, innerStart, innerEnd, outerEnd, outerNext];
};

Disjoint => {

CEG.JoinVertices[innerEnd, outerEnd, lensClientData, lensClientData];  -- new edges get lens state, other fields default.
IF verbosity#NIL THEN verbosity.out.PutF["\nLensDecomposition joins vertices #%g and #%g in lens\n", IO.int[innerEnd.index], IO.int[outerEnd.index] ];

UpdateInnerEdgeFields[];

pointLineRelation _ EG.PointLineTest[innerEnd.coordinates, innerNext.coordinates, outerEnd.coordinates];
IF pointLineRelation = LEFTOFLINE THEN {
outerStart _ outerEnd;
[outerEnd, outerNext] _ CEG.StepVertex[ outerEnd, outerNext, polygonStepping];  -- need to step outer polygon before doing next JoinVertices
CEG.JoinVertices[ innerEnd, outerEnd, lensClientData, lensClientData ];
IF verbosity#NIL THEN verbosity.out.PutF["\nLensDecomposition corner check joins vertices #%g and #%g in lens\n", IO.int[innerEnd.index], IO.int[outerEnd.index] ];
};

innerStart _ innerEnd;
[innerEnd, innerNext] _ CEG.StepVertex[innerEnd, innerNext, outlineStepping];

};

ENDCASE => ERROR -- OuterEndEqInnerStart, InnerStartInOuter cannot occur (proof by induction).;

ENDLOOP;
};

BoundaryContactOnly: PUBLIC PROC[inputStart, inputEnd, currentVertex: Vertex, verbosity: Verbosity _ NIL] = {
overlap: BOOL;
overlappedCurrentVertex, nextCurrentVertex: Vertex;
distStartCurrent, distStartInput: RN.RatNum;
newVertex, nextInputVertex, tempVertex: Vertex;
thisToNext, nextToThis: EG.Adjacency;
startToEnd, endToStart: EG.Adjacency;
inputClientData: REF;
[ startToEnd, endToStart ] _ EG.FindAdjacency[ inputStart, inputEnd ];
inputClientData _ CEG.GetEdgeClientData[startToEnd];

[overlap, overlappedCurrentVertex] _ EG.TestEdgeOverlap[currentVertex, inputEnd];
WHILE overlap DO

distStartInput _ EG.DistanceSquare[inputStart.coordinates, inputEnd.coordinates];
distStartCurrent _ EG.DistanceSquare[currentVertex.coordinates, overlappedCurrentVertex.coordinates];
SELECT RN.RatNumCompare[distStartInput, distStartCurrent] FROM
ratGreater => {
newVertex _ CEG.InsertVertexInEdges[inputStart, inputEnd, overlappedCurrentVertex.coordinates];
nextInputVertex _ inputEnd;
inputEnd _ newVertex;
nextCurrentVertex _ overlappedCurrentVertex;
};
ratEqual =>  {
nextInputVertex _ CEG.NextPolygonVertex[inputStart, inputEnd];  -- meaningless if returnedToFirstIntersection; that's ok.
nextCurrentVertex _ overlappedCurrentVertex;
};
ratLess => {
newVertex _ CEG.InsertVertexInEdges[currentVertex, overlappedCurrentVertex, inputEnd.coordinates];
nextCurrentVertex _ newVertex;
nextInputVertex _ CEG.NextPolygonVertex[inputStart, inputEnd];
};
ENDCASE;

IF EG.CountAdjacencies[inputStart] > 1 THEN {
tempVertex _ EG.SplitVertex[inputStart, inputEnd];
EG.MergeVertices[currentVertex, tempVertex];
};

EG.DeleteVertex[inputStart];

[thisToNext, nextToThis] _  EG.FindAdjacency[currentVertex, nextCurrentVertex];
CEG.SetEdgeExterior[thisToNext, FALSE];
CEG.SetEdgeClientData[thisToNext, inputClientData];
IF verbosity#NIL THEN verbosity.out.PutF["\nBoundaryContactOnly updates fields of edge [ #%g , #%g ]\n", IO.int[currentVertex.index], IO.int[nextCurrentVertex.index]];

inputStart _ inputEnd;  inputEnd _ nextInputVertex; -- move to next input polygon edge
currentVertex _ nextCurrentVertex;  -- now inputStart and currentVertex are next pair of common coordinate, unmerged vertices of input polygon and current figure
[overlap, overlappedCurrentVertex] _ EG.TestEdgeOverlap[currentVertex, inputEnd];

ENDLOOP;

EG.MergeVertices[currentVertex, inputStart];

};




SimpleCleaner: PUBLIC PROC [currentEnd: Vertex, clientDataEqual: ClientDataEqual, verbosity: Verbosity _ NIL] ~ {
visitedValue: BOOL;

SimpleCleanerSubr: PROC[v: Vertex, visitedValue: BOOL, clientDataEqual: ClientDataEqual, verbosity: Verbosity _ NIL] = {
adjacencies: LIST OF Vertex;
nextVertex, prevV: Vertex;
vToNext, NextTov: EG.Adjacency;

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

adjacencies _ EG.AdjacentVertices[v];
WHILE adjacencies#NIL DO
nextVertex _ adjacencies.first;
IF nextVertex.visited # visitedValue THEN
SimpleCleanerSubr[ nextVertex, visitedValue, clientDataEqual, verbosity]
ELSE {
IF EG.Adjacent[v, nextVertex] AND EG.CountAdjacencies[v] > 2 AND EG.CountAdjacencies[nextVertex] > 2 THEN { -- v and nextVertex may no longer be adjacent (because of deletes), and we don't want to create vertices with only one adjacency.
[vToNext, NextTov] _ EG.FindAdjacency[ v, nextVertex ];
IF NOT CEG.GetEdgeExterior[vToNext] AND NOT CEG.GetEdgeExterior[NextTov] -- don't delete outline edges
THEN IF clientDataEqual[CEG.GetEdgeClientData[vToNext], CEG.GetEdgeClientData[NextTov] ] THEN {
prevV _ CEG.PreviousPolygonVertex[v, nextVertex];
EG.DeleteEdge[v, nextVertex];
EG.DeleteEdge[nextVertex, v]; -- temporarily delete the edges
IF CEG.ConvexPolygon[prevV, v, FALSE] THEN {
IF verbosity#NIL THEN verbosity.out.PutF["\nSimpleCleaner deletes edges [ #%g , #%g ]\n", IO.int[v.index], IO.int[nextVertex.index]]
}
ELSE { -- restore the edges
CEG.AddEdge[v, nextVertex, CEG.GetEdgeExterior[vToNext], CEG.GetEdgeIPEdge[vToNext], CEG.GetEdgeClientData[vToNext], vToNext.visited];
CEG.AddEdge[nextVertex, v, CEG.GetEdgeExterior[NextTov], CEG.GetEdgeIPEdge[NextTov], CEG.GetEdgeClientData[NextTov], NextTov.visited];
};
};
};
};
adjacencies _ adjacencies.rest;
ENDLOOP;
};

IF currentEnd = NIL OR currentEnd.adjacentVertices = NIL THEN ERROR; -- no or one vertex;  
visitedValue _ currentEnd.visited;
SimpleCleanerSubr[currentEnd, NOT visitedValue, clientDataEqual, verbosity];  -- toggle visitedValue
};


END.

! ConvexCombinerImpl.mesa
Last Edited by: Arnon, June 20, 1985 4:44:33 pm PDT

Main procedures
currentEnd is a vertex on the (convex) outline of the current figure.  inputEnd is a vertex on the input polygon.  combinedEnd is a vertex on the (convex) outline of the combined figure.

currentEnd is a vertex on the (convex) outline of the current figure.  inputEnd is a vertex on the input polygon. combinedEnd is a vertex on the (convex) outline of the combined figure. [intersectionPolyStart, intersectionPolyEnd] is a (directed) edge in the new (i.e. combined) geometry which is contained in the intersection polygon (of current figure and input polygon), and such that the interior of the intersection polygon lies to its left.  If the intersection polygon is empty, then intersectionPolyStart _ intersectionPolyEnd _ NIL.
Either currentEnd or inputEnd may be NIL, in which case the other is returned. If non-NIL, it is assumed that each structure has at least three vertices.
If setIntersectionPolygonEdges, then CombineGeometry sets the intersectionPolygonEdge fields of all (directed) edges in the new (i.e. combined) geometry which are contained in the intersection polygon, and such that the interior of the intersection polygon lies to their left.  Although this functionality is provided as an essential preprocessing step for CombineClientData, note that it is a purely geometrical operation.  It can be undone with ClearGraphIPEdges.
Check for empty arguments, valid inputs.
Insure that current figure and input polygon have same setting of vertex visited flag.  Adjacency flag fields (leftRegionVisited, intersectionPolygonEdge) assumed to be cleared (set to FALSE) in both current figure and input polygon.
Find preceding vertices on outline so that [currentStart, currentEnd] is a counterclockwise oriented edge on the (convex) outline of the current figure, and [inputStart, inputEnd] is a counterclockwise oriented edge on the input polygon.  Get client data for input polygon
Centers of mass of both figures, and locate wedge of current figure outline that contains vertex inputStart of the input polygon. 
"Cache" where on the current outline the input activity is taking place. If combinedEnd is not subsequently reassigned, we will return this value.
The validity of this EG.PointLineTest branching follows from the facts that inputPrevious = inputStart is outside the current outline, and input polygon is convex.

Set intersectionPolygonEdge fields of "inward-facing" edges, and clear leftRegionExterior and set clientData fields, of "outward-facing" edges, on outline of current figure
Decompose the annulus formed by input polygon - current outline
1.  Search for containing internal polygon.

2. If on boundary of containing internal polygon, call InputIntersectsCurrent.

3. If in interior of containing internal polygon, find a vertex internalStart of internal polygon which lies in exterior of input polygon.  Set inputStart, inputEnd to edge defining wedge containing internalStart.

4. Compare containing internal and input polygons.
Set clientData of input polygon to state of internal polygon of current figure that encloses it.  This is the right thing to do since CombineClientData assumes that interior of the intersection polygon has current state, and will combine that with input polygon state.  Hence CombineGeometry has side effects with respect to state (this is not the only example of that by any means).
Set intersectionPolygonEdge fields of "inward-facing" edges, and clear leftRegionExterior and set clientData fields, of "outward-facing" edges, on input polygon

Decompose annulus formed by current internal polygon - input polygon.
If we arrive here, then input polygon is identical with outline of current figure.  Set all edges of current figure outline to be intersection polygon edges.
[intersectionPolyStart, intersectionPolyEnd] is an edge in the current (i.e. combined) geometry which is contained in the intersection polygon (of current figure and input polygon). inputClientData is the clientData of the input polygon. clientDataCombiner is the rule for clientData combination.
CombineClientData assumes that the intersectionPolygonEdge fields of all (directed) intersection polygon edges are set.  It doesn't clear them.
The clientData fields of the edges of all polygons internal to the intersection polygon are set to the result of clientData combining inputClientData with the clientData's those polygons had in the current figure. The algorithm is Depth First Search.

Set clientData and leftRegionVisited 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. Don't need to consider first edge since on outermost call, [start, end] is on intersection polygon, and on recursive calls, endToStart.leftRegionVisited will have been set true by the caller.

Combiner cases

Get outer client data
Get wedge of inner polygon for outerStart
Back up along inner polygon

Go forward along inner polygon, adding cone of edges.  It is assumed that clientData and leftRegionExterior fields of previously external (outward-facing) edges of internal polygon have already been updated by caller.
Lens decomposition to finish
Convex decomposers and overlap handlers

Find out which of overlappedCurrentVertex, inputEnd closer to inputStart, create new vertex if appropriate.  
Split off all adjacencies of inputStart other than edges [inputStart, inputEnd].
Delete edges [inputStart, inputEnd] from input polygon, leaving the identical edge of current figure in place.
The current figure edge left in place is on intersection polygon
Merge the common vertices (preparation for LensDecomposition).
Determine nextLensInExterior and nextCurrentVertex.  Algorithm: currentVertex begins the next lens, i.e. is common to both input polygon and current figure; the next outgoing edge [currentVertex, inputEnd] of the input polygon does not overlap an edge of the current figure. In the (at this point partially constructed) internal polygon containing the edge [currentVertex, inputEnd], we find the current figure vertex x which precedes currentVertex, and if [x, currentVertex].leftRegionExterior, then lensInExterior and nextCurrentVertex = x.  If NOT [x, currentVertex].leftRegionExterior, then not lensInExterior, and where y is the current figure vertex following currentVertex in the (at this point partially constructed) internal polygon containing the edge [inputEnd, currentVertex], nextCurrentVertex = y.
Update leftRegionExterior and state for [innerEnd, innerStart], and record that [innerStart, innerEnd] is an edge of the intersection polygon of the input polygon and the outline of the current figure.  If NOT lensInExterior, i.e. input polygon is inner, then need to also set state of (directed edge) [innerStart, innerEnd] to lens state, since it's a new edge in current structure which cuts through an existing region, hence should get the state of that region.
These updates are done for an inner edge only after we know we are ready to move past it. This is important, because if we updated too soon, we might e.g. assign a new state to a region that at one point in time extended for the whole length of an inner edge, but the lens might in fact terminate by the outer polygon cutting across that edge, meaning that this region was being subdivided into two regions, the one of which ultimately outside the lens should not get the new state.
Initialize

Follow the lens, biting off convex polygons
Find last outer vertex "above" current inner edge.

Create edges [innerEnd, outerEnd].
Update appropriate fields of edges [innerEnd, innerStart].
Corner check, i.e. check whether outerEnd is left of next inner edge (directed edge [innerEnd, innerNext]); if so, then we need edges [innerEnd, outerNext], so that the next polygon we bite out of the lens is convex.
Find out which of overlappedCurrentVertex, inputEnd closer to inputStart, create new vertex if appropriate.  
Split off incoming input edge, attach to currentVertex.
Delete edges [inputStart, inputEnd] from input polygon, leaving the identical edge of current figure in place.
Clear exterior field and set client data of current outline edge left in place
Merge the last common vertices before input polygon veers into exterior of current outline.
Structure Cleaner

Depth First Search.  Assumes we're called with three or more vertices.  Never eliminates an edge pair one of whose elements is an exterior edge.
Record that we've visited v
Recursive calls for adjacencies of v

�ʦ˜š
œ™J™3J™—š
Ïk	˜	Icodeš�œ
˜Kš
œ˜K˜Jš
œ˜Jš
œ˜Jš
œ˜J˜—
head2šœ�œ
�˜!Jš�œ
�œ1˜;Jš�œ˜J˜—Jšœ�œ
�œ
�œ�œ�œ(˜Z˜J˜—š
œ™J˜—šÏnœ�œ
�œ0�œA�œ�œ˜­
J•commentTRUEš
ϼ
™º
Jš
œ3˜3Jšœb�œ
˜sš�œ�œ
�œ˜#Jš
œn˜nJš�œ?˜BJšœÏcO˜R—J˜J™—šžœ�œ
�œ=�œ�œ�œ�œD˜Í
J–TRUEš
œ�™�Jš
Ϫ
™™
Jš
œÑ™ÑJ˜Jš
œ0˜0Jš
œ#˜#Jšœ�œ˜+Jšœ�œ˜5Jš
œ˜Jšœ�œ�œ
˜Jš
œ[˜[Jšœ�œ
˜Jšœ�œ˜%Jš
œA˜AJ˜Jš
œ(™(Jš�œ�œ
�œ
�œ
�œ�œ˜4Jš�œ�œ
�œ
�œ�œ�œ˜4Jš�œ
�œ
�œ!�œ
�œ
�œ�œ
�œ
˜_J˜Jš
ώ
™é
Jš�œ'�œ
�œ6˜fJ˜Jš
œ�™�Jšœ�œ*˜<Jšœ �œ(˜KJšœ�œ'˜FJšœ�œ ˜5J˜Jš
œ‚
™‚
Jšœ�œ)�œ˜FJšœ�œ%�œ˜:Jšœ0�œ[�œ˜”
J˜Jš
Ÿ’
™’
Jš
œD˜DJ˜Jš�œ
�œ�˜Kš�œ�˜˜š�œ�œ�œ˜7Kšœ�œ˜(—˜šœm�œ˜‡
Jš
œ˜Jš
œ˜Jš
œ˜Jšœ�œ
˜Jš
œ˜Jš
œ˜Jšœ�˜—Jš
œ˜J˜š�œ�˜ J˜š
œ˜Jšœ�œ_˜uš�œ�˜š�œ�
œ˜Kš
œ8˜8Jš
œF˜FKšœ�œ7˜YKš�œ�œ�œ˜Kš
œ˜—š�œ˜Kš
œ’
˜’
Kšœ�œ7˜YKš�œ:˜@K˜—Kš�œ
˜Kšœ�œŒ
™£
—Jš
œ˜J˜—š
œ
˜
J™Jš
œ¬
™¬
Kš�œ-�œ˜6Kš�œ7�œ�œ˜YJ˜Jš
œ?™?JšœgŸ&˜�
J˜Jš�œ&˜,Jš
œ˜J˜—˜
Jš
œŒ
˜Œ
Kšœ�œ7˜YJš�œ�œ�œ˜J˜J˜—Jš�œ
˜—Jš
œ˜J˜—š�œ�œ�œ�œ˜EJ˜Jšœ�œ˜*Jš
œ#˜#Jšœ�œ
˜—˜J™+Kšœ1�œO˜ƒ
J™Jš
œN™Nš�œ�˜š�œ˜Kš
œ˜Kš
œ–
˜–
Kš�œ�œ
�œ@˜[Kšœ�œ7˜YJš�œ;˜AJš
œ˜—š�œ˜Kš
œ˜Kš
œ–
˜–
Kš�œ�œ
�œ@˜[Kšœ�œ7˜YJš�œ;˜AJš
œ˜—š�œ˜Jšœ�œI˜\Kš
œ–
˜–
Kš�œ�œ
�œ@˜[Kšœ�œ7˜YJš�œ;˜AJš
œ˜—Kš�œ
˜—J™Jš
œÕ
™Õ
Kšœ<�œU˜”
Kš�œ
�œ�œ
�œ
˜J™Jš
œ2™2šœm�œ˜‡
Jš
œ˜Jš
œ˜Jš
œ˜Jšœ�œ
˜Jš
œ˜Jš
œ˜Jšœ�˜—Jš
œ˜J˜š�œ�˜ J˜š
œ˜Kš
œ˜
˜˜
Kš�œ�œ
�œ@˜[Kšœ�œ7˜YJš�œ;˜AJš
œ˜J˜—š
œ
˜
Jšœ�œ
˜J˜Jš
œÿ™ÿJšœ�œ+˜HKšœ�œ˜>Kš�œG˜JJ˜Jš
œ 
™ 
Kš�œ)�œ˜2Kš�œ3�œ�œ˜_J™Jš
œE™EJš
œ^˜^Jš�œ%Ÿ:˜eJš
œ˜——˜Jš�œ�˜—Jš
œ˜J˜—š�œ�œ�œ˜;Jšœ�œ#�œŸi˜°
š�œ �˜&Jšœ�˜—š
�˜Jšœ0�œ[�œ˜”
—K˜K˜—š�œ�œ
˜K˜—Kš�œ
˜—K˜Kš
œ�
™�
Kš�œ-�œ˜6Jš�œ(˜.J˜J˜—š
žœ�œ
�œF�œA�œ˜°
J–TRUEš
œ¨™¨Jš
œ�
™�
Jš
Ϝ
™ú
Jšœ'�œ
˜+Jš
œ&˜&Jš
œ"˜"Jš
œ"˜"Jšœ�œ˜%Jšœ	�œ�œ
˜J˜š�œ�œ
�œ˜JšœO�œ�œ˜xJ˜—J˜Jšœ�œ˜8Jšœ�œ˜6Jš
œL˜LJ™Jš
œD™DKš�œ6�œ˜?J˜Jš
œ½™½š�œ�˜ Jšœ�œ!˜3Jšœ�œ˜<š�œ
�œ
�œ�˜)š�œ
�œ�˜Jš
œN˜N——Jš�œ
˜—J˜J˜—J™š
œ™J™—šžœ�œ
�œF�œ�œ%�œ9˜Ö
Jš
œ*˜*Jšœ�œ�œ
˜*Jš
œ1˜1Jšœ�œ
˜J˜š�œ
�œ�˜(K˜Kš
œ³
˜³
—˜š�œ
�œ�˜'š�œ�˜Jš
œ5˜5Jšœ¾
�œ
˜Ï
J˜
—š
�˜Jšœ¾
�œ
˜Ï
—J˜—š�œ
�œ�˜'Jšœ�œ"�œ˜E—J˜Jš�œ
˜J˜—Jšœ�œ#˜<J˜Jš�œCŸ
˜JJ˜J˜J˜—š
žœ�œ
�œu�œ�œ'˜Ë
Jšœ�œ˜ Jšœ�œ˜(Jšœ�œ˜Jšœ!�œH�œ˜rJšœ%�œ[�œ˜‰
Jš�œ&�œ�œ�œ�œ�œ�œ�œ�œŸ4˜�
Jš
�œ�œ
�œM�œ�œ˜–
Jšœ�œU˜kš�œ�œ
�˜(Jšœ�œ'˜:Jš�œ�œŸ/˜SJšœ�œ%˜8Jš�œ�œŸ-˜PJšœ�œ"�œ˜EJš�œ&�œ�œ�œ�œ�œ�œ�œ�œŸ/˜Œ
Jš
�œ�œ
�œM�œ�œ˜–
Jšœ�œU˜kJš�œ
˜—Jš�œ˜!J˜J˜—šžœ�œ
�œ^�œ˜‰
Jšœ�œ˜+Jš
œ(˜(Jšœ�œ˜(Jšœ�œ˜Jšœ�œ˜%Jšœ�œ�œ
˜*Jšœ@Ÿ
˜JJ˜Jš
œ™Jšœ�œ%˜BJšœ�œ˜4J˜Jš
œ)™)Jšœ,�œN�œ˜„
J˜Jš
œ™Jš
œ˜Jš
œ˜Jšœ�œ-˜<Jšœ�œU˜kš�œ�
œ
�˜'Jš
œ˜Jš
œ˜Jšœ�œ-˜<Jšœ�œU˜kJš�œ
˜—J™Jš
œÙ
™Ù
Jš�œG˜JJš
�œ�œ
�œM�œ�œ˜•
Jšœ�œU˜kš�œ�œ
�˜(Jš
œ˜Jšœ�œ"�œŸ;˜€
Jš�œG˜JJš
�œ�œ
�œM�œ�œ˜•
Jšœ�œU˜kJš�œ
˜—J˜Jš
œ™Jšœ—
�œ�œŸ�ŸÐ
˜™Jš�œ
�œ�œ
�œ
˜.J˜J˜—J˜š
œ'™'J™—šžœ�œ
�œY�œ�œ�œ�œ�œD�œ˜–Kšœ	�œ
˜Jš
œ ˜ Jšœ"�œ˜,Jš
œ˜Jšœ�œ˜%š
žœ�œ�œ�œ
�œ˜-Jš
�œ�œ�œ
�œ
�œ˜ Jš
�œ�œ�œ
�œ
�œ˜Jš�œ
�œ˜Jš
œ˜—Kšœ�œ
˜$Kš
œ˜Jšœ%�œ*˜QJš�œ	�œ
�œ�˜4˜Jš
œm™mJšœ�œ>˜QJšœ�œP˜eš�œ
�œ1�˜>š
œ˜Kšœ�œP˜_Kš
œ˜Kš
œ˜Kš
œ,˜,J˜—š
œ˜Kšœ�œ+Ÿ9˜yKšœ+Ÿ
˜,K˜—š
œ˜Kšœ�œS˜bKš
œ˜Kšœ�œ)˜>J˜—Jš�œ
˜J˜—Jš
ŸP™Pš�œ
�œ"�œ˜-Jšœ
�œ#˜2Jš�œ*˜,J˜—J˜Jš
Ÿn™nKš�œ˜J˜Jš
œ@™@Jšœ�œ1˜OJš�œ�œ˜$Jš
�œ�œ
�œ`�œ�œ˜³
J˜Jšœ4Ÿ"˜VJšœ$Ÿ}˜¡
Jš
œ>˜>Jš	�œ
�œA�œ
�œŸ˜hJšœ%�œ/Ÿ6˜Œ
Jš�œ
˜—Jš�œ�œ
�œ
�œ˜1J˜Jš
œ>™>Jš�œ*˜,J˜Jš
œ«™«Jšœ�œ7˜NJšœ�œ1˜OJšœ�œ˜5š�œ
�œ�˜Jšœ�œ3˜J—Jš�œ
�œI˜UJ˜J˜—šžœ�œ
�œK�œ�œ�œ�œ�œ�œE˜¤Jšœ�œ�œ
˜Jšœ�œ�œ
˜Jš
œ5˜5JšœX�œ˜eJš
œ˜Jšœ�œ˜8Jšœ�œ˜(Jšœ�œ˜.Jšœ�œ
˜J˜šžœ�œ�œ˜&JšŸœŸ¯
œŸð
™ÐJš
Ÿâ™âJšœ/�œ%˜VJš�œ'�œ˜1Jš�œ9˜<Jš�œ
�œ�œ
�œ9˜Wš�œ�œ˜%Jš�œ%�œ˜.Jš
�œ�œ
�œ^�œ�œ˜¥
J˜—K˜—J˜Jš
œ
™
J˜$Jšœ/�œ'˜XJšœ�œ*Ÿ5˜sJšœ�œ4˜CJšœ�œ3˜BJ™Jš
Ÿ+™+š�œŸ˜J˜Jš
œ2™2Jšœ�œ\˜zš�œ�œ
�˜0Jšœ0�œ2˜eJšœ�œ\˜zJš�œ
˜—J™Jšœ�œ>˜TKš�œ�˜˜š
œ˜Kšœ�œB˜PKš
œ˜Kš�œ
�œ-˜9K˜K˜—š
œ˜Kš
œ˜š�œ�œ
Ÿ˜;Kš�œ
�œ,˜7—š
�˜Kš�œ
�œ-˜9—K˜K˜—š
œ˜Kšœ�œk˜|Kšœ�œ9˜GKšœ�œ8˜GKš
œ˜Kš�œ
�œ,˜8K˜K˜—š
œ˜Kšœ�œ@˜OKš
œ˜Kš�œ
�œ-˜9K˜K˜—š
œ
˜
J˜Jš
œ"™"Jš�œDŸ2˜yJš
�œ�œ
�œP�œ�œ˜–
J˜Jš
Ÿ:™:š
œ˜J˜—Jš
ϯ
™Ø
Jšœ�œR˜hš�œ�
œ
�œ˜(Jš
œ˜Jšœ�œ5Ÿ<˜Œ
Jš�œD˜GJš
�œ�œ
�œ]�œ�œ˜£
J˜—J˜Jš
œ˜Jšœ�œ2˜MJ˜J˜J˜—Kš�œ�œ
ŸN˜_K˜—Jš�œ
˜—J˜J˜—šžœ�œ
�œE�œ˜mKšœ	�œ
˜Jš
œ3˜3Jšœ"�œ˜,Jš
œ/˜/Jšœ�œ˜%Jšœ�œ˜%Jšœ�œ
˜Jšœ�œ'˜FJšœ�œ˜4J˜Jšœ%�œ*˜QJš�œ	�˜˜Jš
œm™mJšœ�œ>˜QJšœ�œP˜eš�œ
�œ1�˜>š
œ˜Kšœ�œP˜_Kš
œ˜Kš
œ˜Kš
œ,˜,J˜—š
œ˜Kšœ�œ+Ÿ9˜yKšœ+Ÿ
˜,K˜—š
œ˜Kšœ�œS˜bKš
œ˜Kšœ�œ)˜>J˜—Jš�œ
˜J˜—JšŸ0œŸ
™7š�œ
�œ"�œ˜-Jšœ
�œ#˜2Jš�œ*˜,J˜—J˜Jš
Ÿn™nKš�œ˜J˜Jš
œN™NJšœ�œ1˜OJš�œ�œ˜'Jš�œ0˜3Jš
�œ�œ
�œT�œ�œ˜§
J˜Jšœ4Ÿ"˜VJšœ$Ÿ}˜¡
Jšœ%�œ*˜QJ˜Jš�œ
˜—J˜Jš
œ[™[Jš�œ*˜,J˜˜J˜—K˜—˜K˜—™J™—šž
œ�œ
�œO�œ˜qJ–TRUEš
œ�
™�
Jšœ�œ
˜J˜šžœ�œ�œ;�œ˜xJšœ
�œ
�œ˜Jš
œ˜Jšœ�œ˜J˜Jš
œ™JšœŸ(˜BJ˜Jš
œ$™$Jšœ�œ˜%š�œ
�œ
�˜Jš
œ˜š�œ#�˜)Jš
œH˜H—š�œ˜š�œ
�œ�œ
�œ�œ
�œ"�œŸ�
˜í
Jšœ�œ ˜7Jš
�œ
�œ
�œ�œ
�œ
�œŸ˜fš
�œ
�œ�œ�œ�œ˜_Jšœ�œ&˜1Jš�œ˜Jš�œŸ˜=š�œ
�œ�œ�œ˜,Jš
�œ�œ
�œE�œ�œ˜„
J˜
—š�œŸ˜Jš�œ�œ�œ�œ.˜†
Jš�œ�œ�œ�œ.˜†
J˜—J˜—J˜—J˜Jš
œ˜—Jš�œ
˜—Jš
œ˜—J˜Jš
�œ�œ
�œ�œ
�œ
�œŸ˜[Jš
œ"˜"Jšœ�œ-Ÿ˜dJ˜J˜—J˜Jš�œ
˜˜J™——…—ix£¾