SweepImpl.mesa
Copyright © 1985 by Xerox Corporation. All rights reserved.
Greene, March 28, 1986 2:20:15 pm PST

DIRECTORY
Sweep;
SweepImpl: CEDAR PROGRAM IMPORTS Sweep EXPORTS Sweep =
BEGIN OPEN Sweep;
LineCarrier: TYPE = REF LineCarrierRec;
LineCarrierRec: TYPE = RECORD[
carried: Line,
lineLeft, lineRight: LineCarrier ← NIL
];
NilCopy: PUBLIC PROC [stateIn: REF ANY] RETURNS [stateOut: REF ANY] ~ {
RETURN[stateIn]
};
NilCombine: PUBLIC PROC [state1, state2: REF ANY] RETURNS [state: REF ANY] ~ {
RETURN[NIL]
};
NilFlip: PUBLIC PROC [stateIn: REF ANY] RETURNS [stateOut: REF ANY] ~ {
RETURN[NIL]
};
PowerOf2: PROC [in: CARDINAL] RETURNS [out: CARDINAL ← 32] ~ {
UNTIL out >= in DO
out ← out * 2;
ENDLOOP;
};
ExpandIfNecessary: PROC [in: REF PointSeq] RETURNS [out: REF PointSeq] ~ INLINE {
OPEN in;
IF size = max THEN {
out ← NEW[PointSeq[max*2]];
FOR i: CARDINAL IN [0..size) DO out.data[i] ← data[i] ENDLOOP;
out.size ← size;
}
ELSE out ← in;
};
Intersect: PUBLIC PROC [in: Graph, Copy: CopyLineProc ← NilCopy, Combine: CombineLineProc ← NilCombine, Flip: FlipLineProc ← NilFlip] RETURNS [out: Graph] ~ {
pointCount: CARDINAL ← 0; i: CARDINAL ← 0;
changed: BOOLEAN;
FlipLine: PROC [line: Line] ~ {
OPEN line;
temp: Point ← above; above ← below; below ← temp;
state ← Flip[state];
};
freeLC: LineCarrier ← NIL;
NewLC: PROC [carried: Line, lineLeft, lineRight: LineCarrier ← NIL] RETURNS [alive: LineCarrier] ~ {
IF freeLC = NIL THEN RETURN[NEW[LineCarrierRec← [carried: carried, lineLeft: lineLeft, lineRight: lineRight]]] ELSE {
alive ← freeLC; freeLC ← alive.lineRight;
alive.carried ← carried; alive.lineLeft ← lineLeft; alive.lineRight ← lineRight;
}
};
TrashFreeLC: PROC [] ~ {
UNTIL freeLC = NIL DO
freeLC.lineLeft ← NIL; freeLC ← freeLC.lineRight;
ENDLOOP;
};
sortedIn: REF PointSeq ← NEW[PointSeq[in.points.max]];
indexIn: CARDINAL ← 0;
sortedOut: REF PointSeq ← NEW[PointSeq[in.points.max]];
switch: REF PointSeq;
heap: REF PointSeq ← in.points;
Heapify: PROC [] ~ {
OPEN heap;
limit: CARDINAL ← size;
size ← 1;
FOR i: CARDINAL IN [1..limit) DO
data[size] ← data[i];
size ← size + 1;
BubbleUp[size - 1];
ENDLOOP;
};
QueueInsert: PROC [p: Point] ~ {
heap ← ExpandIfNecessary[heap];
heap.data[heap.size] ← p; heap.size ← heap.size + 1;
BubbleUp[heap.size - 1];
};
BubbleUp: PROC [pos: CARDINAL] ~ {
pL: Point; r: Relation;
pos ← pos + 1; -- shift for convience
pL ← heap.data[pos - 1];
UNTIL pos = 1 DO
pH: Point ← heap.data[pos/2 - 1];
r ← ComparePoints[pL, pH];
IF r # greater THEN {
heap.data[pos - 1] ← pL;
RETURN;
}
ELSE {
heap.data[pos - 1] ← pH;
pos ← pos / 2;
};
ENDLOOP;
heap.data[0] ← pL;
};
HoleDown: PROC [pos: CARDINAL] ~ {
OPEN heap;
lower: CARDINAL; r: Relation;
pos ← pos + 1;
lower ← pos * 2;
UNTIL lower >= size DO
r ← ComparePoints[data[lower-1], data[lower]];
IF r = less THEN {
data[pos - 1] ← data[lower];
pos ← lower + 1;
}
ELSE {
data[pos - 1] ← data[lower - 1];
pos ← lower;
};
lower ← pos*2;
ENDLOOP;
IF lower = size THEN {data[pos - 1] ← data[lower - 1]; size ← size - 1}
ELSE {
size ← size - 1;
IF pos - 1 # size THEN {
data[pos - 1] ← data[size];
BubbleUp[pos - 1];
};
};
};
EmptyQueue: PROC [] RETURNS [BOOLEAN] ~ {
RETURN [(indexIn = sortedIn.size) AND (heap.size = 0)]
};
NextEvent: PROC [] RETURNS [p: Point] ~ {
OPEN heap;
IF size = 0 THEN { -- heap is empty
IF indexIn = sortedIn.size THEN ERROR ELSE {
p ← sortedIn.data[indexIn];
indexIn ← indexIn + 1;
}
}
ELSE { -- heap is full
WHILE size >= 3 AND ComparePoints[data[0], data[2]] = equal DO --remove duplicates right tree
MergePoints[data[0], data[2]];
HoleDown[2];
ENDLOOP;
WHILE size >= 2 AND ComparePoints[data[0], data[1]] = equal DO --remove duplicates left tree
MergePoints[data[0], data[1]];
HoleDown[1];
ENDLOOP;
IF indexIn = sortedIn.size THEN {
p ← data[0];
HoleDown[0];
}
ELSE {
r: Relation ← ComparePoints[ data[0], sortedIn.data[indexIn] ];
IF r = less THEN {
p ← sortedIn.data[indexIn];
indexIn ← indexIn + 1;
}
ELSE {
IF r = greater THEN {
p ← data[0];
HoleDown[0]
}
ELSE {
p ← data[0];
MergePoints[p, sortedIn.data[indexIn]];
indexIn ← indexIn + 1;
HoleDown[0];
};
};
};
};
sortedOut ← ExpandIfNecessary[sortedOut];
sortedOut.data[sortedOut.size] ← p;
sortedOut.size ← sortedOut.size + 1;
};
xOrder, neighborRight, leftMostInserted: LineCarrier ← NIL;
OrderRemoveLines: PROC [p: Point] RETURNS [rightNeighbor: LineCarrier] ~ {
orderScan: LineCarrier ← xOrder;
leftNeighbor: LineCarrier;
lineScan: Line ← p.incoming;
oldLineScan: Line; count: INT;
AdvanceLineCarrier: PROC [] ~ {
rightNeighbor ← orderScan.lineRight;
orderScan.lineRight ← freeLC; freeLC ← orderScan;
orderScan ← rightNeighbor;
};
IF p.incoming = NIL THEN RETURN[NIL];
UNTIL lineScan = orderScan.carried DO --bounds fault indicates algorithmic failure
orderScan ← orderScan.lineLeft;
ENDLOOP;
leftNeighbor ← orderScan.lineLeft;
WHILE leftNeighbor # NIL DO
IF leftNeighbor.carried.below # p THEN EXIT;
orderScan ← orderScan.lineLeft;
leftNeighbor ← orderScan.lineLeft;
ENDLOOP;
UNTIL lineScan = NIL DO
IF lineScan # orderScan.carried THEN
{--Out of order acceptable up to slope inequality
count ← 0;
WHILE orderScan # NIL DO
IF (CompareSlopes[lineScan, orderScan.carried] # equal) OR (orderScan.carried.below # p) THEN EXIT;
AdvanceLineCarrier[];
count ← count + 1;
ENDLOOP;
oldLineScan ← lineScan; lineScan ← lineScan.clockwiseAroundBelow;
count ← count - 1;
WHILE lineScan # NIL DO
IF CompareSlopes[lineScan, oldLineScan] # equal THEN EXIT;
lineScan ← lineScan.clockwiseAroundBelow;
count ← count - 1;
ENDLOOP;
IF count # 0 THEN ERROR;
}
ELSE {
lineScan ← lineScan.clockwiseAroundBelow;
AdvanceLineCarrier[];
};
ENDLOOP;
IF leftNeighbor # NIL THEN leftNeighbor.lineRight ← rightNeighbor;
IF rightNeighbor # NIL THEN rightNeighbor.lineLeft ← leftNeighbor ELSE xOrder ← leftNeighbor;
};
OrderInsertLines: PROC [p: Point, rightNeighborIn: LineCarrier] RETURNS [leftMostInserted, rightNeighbor: LineCarrier] ~ {
r: Relation;
lineScan, garbage, topHalf, bottomHalf: Line;
lc, broken, leftNeighbor: LineCarrier;
firstTime: BOOLEAN;
rightNeighbor ← rightNeighborIn;
IF p.outgoing = NIL THEN RETURN[NIL, rightNeighbor];
leftNeighbor ← IF rightNeighbor = NIL THEN xOrder ELSE rightNeighbor.lineLeft;
UNTIL leftNeighbor = NIL DO
r ← ComparePointLine[p, leftNeighbor.carried];
IF r = greater THEN EXIT;
IF r = equal THEN {
broken ← leftNeighbor;
leftNeighbor ← leftNeighbor.lineLeft;
topHalf ← broken.carried;
broken.carried ← NIL; broken.lineLeft ← broken.lineRight ← NIL;
bottomHalf ← NEW[LineRec ← [above: p, below: topHalf.below, state: Copy[topHalf.state]]];
RemoveLineFromPointBelow[topHalf];
InsertLineInPointBelow[bottomHalf];
InsertLineInPointAbove[bottomHalf];
IF p.incoming # NIL THEN ERROR;
topHalf.below ← p;
InsertLineInPointBelow[topHalf];
EXIT;
};
rightNeighbor ← leftNeighbor;
leftNeighbor ← leftNeighbor.lineLeft;
ENDLOOP;
leftMostInserted ← rightNeighbor;
lineScan ← p.outgoing;
firstTime ← TRUE;
UNTIL lineScan = NIL DO
IF (NOT firstTime) AND (CompareSlopes[leftMostInserted.carried, lineScan] = equal) THEN
{r ← ComparePoints[leftMostInserted.carried.below, lineScan.below];
garbage ← lineScan;
lineScan ← lineScan.clockwiseAroundAbove;
IF r = equal THEN {
leftMostInserted.carried.state ← Combine[leftMostInserted.carried.state, garbage.state];
RemoveLineFromPointAbove[garbage]; RemoveLineFromPointBelow[garbage];
}
ELSE {
IF r = greater THEN {topHalf ← leftMostInserted.carried; bottomHalf ← garbage}
ELSE {topHalf ← garbage; bottomHalf ← leftMostInserted.carried; leftMostInserted.carried ← topHalf};
topHalf.state ← Combine[topHalf.state, bottomHalf.state];
RemoveLineFromPointAbove[bottomHalf];
bottomHalf.above ← topHalf.below;
InsertLineInPointAbove[bottomHalf]
};
}
ELSE
{ lc ← NewLC[carried: lineScan, lineRight: leftMostInserted];
IF leftMostInserted # NIL THEN leftMostInserted.lineLeft ← lc ELSE xOrder ← lc;
leftMostInserted ← lc;
firstTime ← FALSE;
lineScan ← lineScan.clockwiseAroundAbove};
ENDLOOP;
leftMostInserted.lineLeft ← leftNeighbor;
IF leftNeighbor # NIL THEN leftNeighbor.lineRight ← leftMostInserted;
};
CompareLineLeft: PROC [lc: LineCarrier] ~ {
newLc: LineCarrier;
p: Point; s: LineRelation; s1, s2: EndPointRelation;
ll, lr, topHalf, bottomHalf: Line;
propagate: BOOLEAN ← FALSE;
insertInQueue: BOOLEAN ← TRUE;
r: Relation;
BreakALine: PROC [l: Line] ~ {
propagate ← TRUE;
changed ← TRUE;
topHalf ← l;
bottomHalf ← NEW[LineRec ← [above: p, below: l.below, state: Copy[topHalf.state]]];
RemoveLineFromPointAbove[topHalf];
RemoveLineFromPointBelow[topHalf];
topHalf.below ← p;
InsertLineInPointAbove[topHalf];
InsertLineInPointBelow[topHalf];
r ← ComparePoints[bottomHalf.above, bottomHalf.below];
IF r = equal THEN {
IF bottomHalf.above = bottomHalf.below THEN insertInQueue ← FALSE
}
ELSE {
IF r = less THEN FlipLine[bottomHalf];
InsertLineInPointAbove[bottomHalf];
InsertLineInPointBelow[bottomHalf]
};
};
IF lc = NIL THEN RETURN;
lr ← lc.carried;
IF lc.lineLeft = NIL THEN RETURN;
ll ← lc.lineLeft.carried;
[p, s, s1, s2] ← PairIntersection[ll, lr];
IF s = colinear THEN {
s1 ← s2 ← interior;
IF ComparePoints[ll.below, lr.below] = less THEN {
p ← lr.below;
s2 ← below;
}
ELSE {
p ← ll.below;
s1 ← below;
};
};
IF (s = intersect) OR (s = colinear) THEN {
IF ComparePoints[p, currentPoint] = less THEN {
IF s2 = interior THEN BreakALine[lr]
ELSE {
insertInQueue ← FALSE;
IF s2 # below THEN ERROR; --Remove after debug
};
IF s1 = interior THEN BreakALine[ll]
ELSE {
insertInQueue ← FALSE;
IF s1 # below THEN ERROR; --Remove after debug
};
IF insertInQueue THEN QueueInsert[p];
};
};
IF s = colinear THEN {
r ← ComparePoints[ll.above, lr.above];
IF r = greater THEN {
Break LL
RemoveLineFromPointBelow[ll];
lr.state ← Combine[lr.state, ll.state];
ll.below ← lr.above;
InsertLineInPointBelow[ll];
lc.lineLeft.carried ← lr
}
ELSE IF r = less THEN {
Break LR
RemoveLineFromPointBelow[lr];
ll.state ← Combine[ll.state, lr.state];
lr.below ← ll.above;
InsertLineInPointBelow[lr];
}
ELSE
{ll.state ← Combine[ll.state, lr.state];
RemoveLineFromPointBelow[lr];
RemoveLineFromPointAbove[lr];
};
newLc ← lc.lineLeft;
newLc.lineRight ← lc.lineRight;
IF lc.lineRight # NIL THEN lc.lineRight.lineLeft ← newLc ELSE xOrder ← newLc;
lc.carried ← NIL; lc.lineLeft ← lc.lineRight ← NIL;
CompareLineLeft[newLc];
CompareLineLeft[newLc.lineRight];
}
ELSE {
IF CompareLinesAtY[ll, lr, currentPoint] = greater THEN
{lc.carried ← ll;
lc.lineLeft.carried ← lr;
propagate ← TRUE};
IF propagate THEN
{CompareLineLeft[lc.lineLeft];
CompareLineLeft[lc.lineRight]};
};
};
currentPoint: Point;
IF in.status = invalid THEN ERROR;
IF in.status = planar THEN RETURN[in];
Load the points into a priority queue
Heapify[];
Process the points in the priority queue
changed ← TRUE;
WHILE changed DO
changed ← FALSE;
xOrder ← NIL;
UNTIL EmptyQueue[] DO
currentPoint ← NextEvent[];
neighborRight ← OrderRemoveLines[currentPoint];
[leftMostInserted, neighborRight] ← OrderInsertLines[currentPoint, neighborRight];
CompareLineLeft[neighborRight];
CompareLineLeft[leftMostInserted];
ENDLOOP;
switch ← sortedIn; sortedIn ← sortedOut; sortedOut ← switch;
indexIn ← 0; sortedOut.size ← 0;
ENDLOOP;
out ← NEW[GraphRec ← [status: planar, points: sortedIn]];
in.status ← invalid;
TrashFreeLC[];
};
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;
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]];
RemoveOrphanPoints[out];
in.status ← invalid;
TrashFreeELC[];
};
RemoveOrphanPoints: PROC [in: Graph] ~ {
OPEN in.points;
limit: CARDINAL ← size; size ← 0;
FOR i: CARDINAL IN [0..limit) DO
IF data[i].incoming # NIL OR data[i].outgoing # NIL THEN {
data[size] ← data[i];
size ← size + 1;
};
ENDLOOP;
};
END.