FastIntersectImpl.mesa
Copyright © 1985 by Xerox Corporation. All rights reserved.
Greene, October 3, 1986 5:15:16 pm PDT

DIRECTORY
Sweep;
FastIntersectImpl: 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 [] ~ {
FOR i: CARDINAL IN [1..heap.size) DO
BubbleUp[i];
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] ~ {
workLoad: LIST OF LineCarrier ← LIST[lc];
newLc: LineCarrier;
p: Point; s: LineRelation; s1, s2: EndPointRelation;
ll, lr, topHalf, bottomHalf: Line;
propagate, insertInQueue: BOOLEAN;
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]
};
};
UNTIL workLoad = NIL DO
lc ← workLoad.first; workLoad ← workLoad.rest;
propagate ← FALSE; insertInQueue ← TRUE;
IF lc = NIL THEN LOOP;
lr ← lc.carried;
IF lc.lineLeft = NIL THEN LOOP;
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;
workLoad ← CONS[newLc.lineRight, workLoad];
workLoad ← CONS[newLc, workLoad];
}
ELSE {
IF CompareLinesAtY[ll, lr, currentPoint] = greater THEN
{lc.carried ← ll;
lc.lineLeft.carried ← lr;
propagate ← TRUE};
IF propagate THEN
{workLoad ← CONS[lc.lineRight, workLoad];
workLoad ← CONS[lc.lineLeft, workLoad];
};
};
ENDLOOP;
};
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[];
};
END.