SweepImpl.mesa
Copyright © 1985 by Xerox Corporation. All rights reserved.
Greene, October 3, 1986 5:19:24 pm PDT
DIRECTORY
Sweep;
SweepImpl: CEDAR PROGRAM IMPORTS Sweep EXPORTS Sweep =
BEGIN OPEN Sweep;
NilStart: PUBLIC PROC [lineLeft, lineRight: Line, regionPrevious: REF ANY] RETURNS [regionCenter: REF ANY] ~ {
RETURN[NIL]
};
NilStop: PUBLIC PROC [lineLeft: Line, regionCenter: REF ANY, lineRight: Line] ~ {
RETURN;
};
NilSplit: PUBLIC PROC [lineLeft, lineRight: Line, regionRight: REF ANY, regionPrevious: REF ANY ← NIL] RETURNS [regionLeft: REF ANY] ~ {
RETURN[regionRight];
};
NilMerge: PUBLIC PROC [regionLeft: REF ANY, lineLeft, lineRight: Line, regionRight: REF ANY] RETURNS [regionCenter: REF ANY] ~ {
RETURN[regionRight];
};
NilLineChange: PUBLIC PROC [lineOld, lineNew: Line, side: LeftOrRight, regionCenter: REF ANY, regionPrevious: REF ANY ← NIL] ~ {
RETURN;
};
ExpandedLineCarrier: TYPE = REF ExpandedLineCarrierRec;
ExpandedLineCarrierRec: TYPE = RECORD[
carried: Line,
regionLeft: REF ANY ← NIL,
lineLeft, lineRight: ExpandedLineCarrier ← NIL
];
Sweep: PUBLIC PROC [in: Graph, infinityRegion: REF ANY ← NIL, Start: StartRegionProc ← NilStart, Stop: StopRegionProc ← NilStop, Split: SplitRegionProc ← NilSplit, Merge: MergeRegionProc ← NilMerge, LineChange: LineChangeRegionProc ← NilLineChange] RETURNS [out: Graph] ~ {
xOrder, orderScan, temporaryELC, rightNeighbor, leftNeighbor: ExpandedLineCarrier;
holdRegionLeft, temporaryRegion: REF ANY ← NIL;
holdLineLeft, lineScan, prevLineScan: Line;
currentPoint: Point;
freeELC: ExpandedLineCarrier ← NIL;
CleanELC: PROC [dead: ExpandedLineCarrier] ~ {
OPEN dead;
lineRight ← freeELC;
freeELC ← dead;
};
NewELC:
PROC [carried: Line, regionLeft:
REF
ANY ←
NIL, lineLeft, lineRight: ExpandedLineCarrier ←
NIL]
RETURNS [alive: ExpandedLineCarrier] ~ {
IF freeELC =
NIL
THEN
RETURN[
NEW[ExpandedLineCarrierRec← [carried: carried, regionLeft: regionLeft, lineLeft: lineLeft, lineRight: lineRight]]]
ELSE {
alive ← freeELC; freeELC ← alive.lineRight;
alive.carried ← carried; alive.regionLeft ← regionLeft; alive.lineLeft ← lineLeft; alive.lineRight ← lineRight;
}
};
TrashFreeELC:
PROC [] ~ {
UNTIL freeELC =
NIL
DO
freeELC.lineLeft ← NIL; freeELC ← freeELC.lineRight;
ENDLOOP;
};
IF in = NIL THEN RETURN[NIL];
IF in.status # planar THEN ERROR;
FOR i:
CARDINAL
IN [0..in.points.size)
DO
currentPoint ← in.points.data[i];
lineScan ← currentPoint.incoming;
IF lineScan =
NIL
THEN {
leftNeighbor ← xOrder;
rightNeighbor ← NIL;
UNTIL leftNeighbor =
NIL
DO
IF ComparePointLine[currentPoint, leftNeighbor.carried] = greater THEN EXIT;
rightNeighbor ← leftNeighbor;
leftNeighbor ← leftNeighbor.lineLeft;
ENDLOOP;
holdLineLeft ← NIL;
holdRegionLeft ← IF rightNeighbor # NIL THEN rightNeighbor.regionLeft ELSE infinityRegion;
}
ELSE {
orderScan ← xOrder;
UNTIL lineScan = orderScan.carried
DO
--bounds fault indicates algorithmic failure
orderScan ← orderScan.lineLeft;
ENDLOOP;
leftNeighbor ← orderScan.lineLeft;
holdRegionLeft ← orderScan.regionLeft;
holdLineLeft ← lineScan;
DO
prevLineScan ← lineScan;
lineScan ← lineScan.clockwiseAroundBelow;
rightNeighbor ← orderScan.lineRight;
IF lineScan = NIL THEN EXIT;
Stop[prevLineScan, rightNeighbor.regionLeft, lineScan];
CleanELC[orderScan];
orderScan ← rightNeighbor;
IF lineScan # orderScan.carried THEN ERROR;
ENDLOOP;
};
lineScan ← currentPoint.outgoing;
IF lineScan =
NIL
THEN {
IF holdLineLeft #
NIL
THEN {
temporaryRegion ← Merge[holdRegionLeft, holdLineLeft, prevLineScan, IF rightNeighbor = NIL THEN infinityRegion ELSE rightNeighbor.regionLeft];
CleanELC[orderScan];
IF rightNeighbor #
NIL
THEN {
rightNeighbor.regionLeft ← temporaryRegion;
rightNeighbor.lineLeft ← leftNeighbor }
ELSE {xOrder ← leftNeighbor; infinityRegion ← temporaryRegion};
IF leftNeighbor # NIL THEN leftNeighbor.lineRight ← rightNeighbor;
};
}
ELSE {
IF holdLineLeft #
NIL
THEN {
LineChange[prevLineScan, lineScan, left, IF rightNeighbor = NIL THEN infinityRegion ELSE rightNeighbor.regionLeft];
CleanELC[orderScan];
};
DO
prevLineScan ← lineScan;
lineScan ← lineScan.clockwiseAroundAbove;
IF lineScan = NIL THEN EXIT;
temporaryELC ← NewELC[
carried: prevLineScan,
regionLeft: Start[lineScan, prevLineScan, IF rightNeighbor = NIL THEN infinityRegion ELSE rightNeighbor.regionLeft],
lineRight: rightNeighbor ];
IF rightNeighbor # NIL THEN rightNeighbor.lineLeft ← temporaryELC ELSE xOrder ← temporaryELC;
rightNeighbor ← temporaryELC;
ENDLOOP;
temporaryELC ← NewELC[
carried: prevLineScan,
regionLeft: holdRegionLeft,
lineRight: rightNeighbor, lineLeft: leftNeighbor];
IF leftNeighbor # NIL THEN leftNeighbor.lineRight ← temporaryELC;
IF rightNeighbor # NIL THEN rightNeighbor.lineLeft ← temporaryELC ELSE xOrder ← temporaryELC;
IF holdLineLeft #
NIL
THEN {
LineChange[holdLineLeft, prevLineScan, right, holdRegionLeft, IF rightNeighbor = NIL THEN infinityRegion ELSE rightNeighbor.regionLeft];
}
ELSE
temporaryELC.regionLeft ← Split[prevLineScan, currentPoint.outgoing, holdRegionLeft, IF rightNeighbor = NIL THEN infinityRegion ELSE rightNeighbor.regionLeft];
};
ENDLOOP;
out ← NEW[GraphRec ← [status: planar, points: in.points]];
out ← RemoveOrphanPoints[out];
in.status ← invalid;
TrashFreeELC[];
};
END.