SweepStraightImpl.mesa
Copyright © 1985 by Xerox Corporation. All rights reserved.
Greene, August 20, 1986 4:47:05 pm PDT
DIRECTORY
RealFns,
Sweep;
SweepStraightImpl: CEDAR PROGRAM IMPORTS RealFns, Sweep EXPORTS Sweep =
BEGIN OPEN Sweep;
tolerance: REAL ← 1.5;
passes: INTEGER ← 2;
StraightRegion: TYPE = REF StraightRegionRec;
StraightRegionRec:
TYPE =
RECORD [
leftPivot: Point, leftNextPivot: Point ← NIL,
leftLimit: Point ← NIL,
leftSwingingInTo: Point ← NIL,
rightPivot: Point, rightNextPivot: Point ← NIL,
rightLimit: Point ← NIL,
rightSwingingInTo: Point ← NIL,
next: StraightRegion
];
StraightenLines: PUBLIC PROC [in: Graph] RETURNS [out: Graph] ~ {
freeSR: StraightRegion;
NewSR:
PROC [leftPivot, leftNextPivot, leftLimit, leftSwingingInTo, rightPivot: Point ← NIL]
RETURNS [alive: StraightRegion] ~ INLINE {
IF freeSR = NIL THEN RETURN[NEW[StraightRegionRec ← [leftPivot: leftPivot, leftNextPivot: leftNextPivot, leftLimit: leftLimit, leftSwingingInTo: leftSwingingInTo, rightPivot: rightPivot]] ];
alive ← freeSR; freeSR ← alive.next;
alive.leftPivot ← leftPivot; alive.leftNextPivot ← leftNextPivot; alive.leftLimit ← leftLimit; alive.leftSwingingInTo ← leftSwingingInTo; alive.rightPivot ← rightPivot;
alive.rightNextPivot ← alive.rightLimit ← alive.rightSwingingInTo ← NIL;
};
StraightStart: StartRegionProc ~ {
regionCenter ← NewSR[leftPivot: lineLeft.above, rightPivot: lineLeft.above];
};
StraightStop: StopRegionProc ~ {
rC: StraightRegion ← NARROW[regionCenter];
IF lineRight.above # rC.leftPivot THEN CompressLeft[lineLeft, rC];
IF lineLeft.above # rC.rightPivot THEN CompressRight[rC, lineRight];
rC.next ← freeSR; freeSR ← rC;
};
CompressLeft: PROC [lL: Line, rC: StraightRegion] ~ {
older: Line;
IF rC.leftSwingingInTo #
NIL
THEN {
IF rC.leftSwingingInTo # lL.below THEN ERROR;
older ← lL.above.incoming;
IF older = NIL THEN GOTO Abort;
IF older.above # rC.leftPivot THEN GOTO Abort;
RemoveLineFromPointAbove[lL];
lL.above ← older.above;
RemoveLineFromEndPoints[older];
InsertLineInPointAbove[lL];
rC.leftSwingingInTo ← NIL;
};
EXITS
Abort => {rC.leftSwingingInTo ← NIL; rC.leftPivot ← lL.below; rC.leftLimit ← NIL};
};
CompressRight: PROC [rC: StraightRegion, lR: Line] ~ {
older: Line;
IF rC.rightSwingingInTo #
NIL
THEN {
IF rC.rightSwingingInTo # lR.below THEN ERROR;
older ← lR.above.incoming;
IF older = NIL THEN GOTO Abort;
IF older.above # rC.rightPivot THEN GOTO Abort;
RemoveLineFromPointAbove[lR];
lR.above ← older.above;
RemoveLineFromEndPoints[older];
InsertLineInPointAbove[lR];
rC.rightSwingingInTo ← NIL;
};
EXITS
Abort => {rC.rightSwingingInTo ← NIL; rC.rightPivot ← lR.below; rC.rightLimit ← NIL};
};
DegreeTwoBentSlightly: PROC [p: Point, side: LeftOrRight] RETURNS [BOOLEAN] ~ {
lineAbove, lineBelow: Line; cross, length:
INT;
IF p.incoming = NIL OR p.outgoing = NIL THEN RETURN[FALSE];
lineAbove ← p.incoming;
IF lineAbove.clockwiseAroundBelow # NIL THEN RETURN[FALSE];
lineBelow ← p.outgoing;
IF lineBelow.clockwiseAroundAbove # NIL THEN RETURN[FALSE];
cross ← (p.x - lineAbove.above.x) * (lineBelow.below.y - lineAbove.above.y) - (lineBelow.below.x - lineAbove.above.x) * (p.y - lineAbove.above.y);
IF side = right
THEN {
IF cross >= 0 THEN RETURN[FALSE];
cross ← - cross
}
ELSE {
-- side = left
IF cross < 0 THEN RETURN[FALSE];
};
length ← (lineAbove.above.x - lineBelow.below.x)*(lineAbove.above.x - lineBelow.below.x) + (lineAbove.above.y - lineBelow.below.y)*(lineAbove.above.y - lineBelow.below.y);
IF cross / RealFns.SqRt[length] > tolerance THEN RETURN[FALSE];
RETURN[TRUE];
};
StraightLineChange: LineChangeRegionProc ~ {
rC: StraightRegion ← NARROW[regionCenter];
p: Point ← lineNew.above;
IF side = left
THEN {
AdjustRightLimit[p, rC];
CompressLeft[lineOld, rC];
IF rC.leftPivot # p THEN { -- No abort in CompressLeft
IF DegreeTwoBentSlightly[p, left]
AND Clockwise[rC.leftPivot, rC.leftLimit, lineNew.below]
THEN {
rC.leftSwingingInTo ← lineNew.below;
rC.leftNextPivot ← p;
}
ELSE {
rC.leftPivot ← p; rC.leftLimit ← NIL;
};
};
}
ELSE {
-- side = right
AdjustLeftLimit[rC, p];
CompressRight[rC, lineOld];
IF rC.rightPivot # p THEN {
IF DegreeTwoBentSlightly[p, right]
AND CounterClockwise[rC.rightPivot, rC.rightLimit, lineNew.below]
THEN {
rC.rightSwingingInTo ← lineNew.below;
rC.rightNextPivot ← p;
}
ELSE {
rC.rightPivot ← p; rC.rightLimit ← NIL;
};
};
};
};
Clockwise:
PROC [pivot, p1, p2: Point]
RETURNS [
BOOLEAN] ~ {
IF pivot = NIL THEN RETURN[FALSE];
IF p1 = NIL THEN RETURN[TRUE];
RETURN[ (p1.x - pivot.x) * (p2.y - pivot.y) < (p2.x - pivot.x) * (p1.y - pivot.y) ];
};
AdjustLeftLimit:
PROC [rC: StraightRegion, pR: Point] ~ {
IF Clockwise[rC.leftPivot, rC.leftLimit, pR]
THEN {
rC.leftLimit ← pR;
IF rC.leftSwingingInTo #
NIL
AND
NOT CounterClockwise[rC.leftPivot, rC.leftSwingingInTo, pR]
THEN {
rC.leftSwingingInTo ← NIL;
rC.leftPivot ← rC.leftNextPivot;
};
};
};
CounterClockwise:
PROC [pivot, p1, p2: Point]
RETURNS [
BOOLEAN] ~ {
IF pivot = NIL THEN RETURN[FALSE];
IF p1 = NIL THEN RETURN[TRUE];
RETURN[ (p1.x - pivot.x) * (p2.y - pivot.y) > (p2.x - pivot.x) * (p1.y - pivot.y) ];
};
AdjustRightLimit:
PROC [pL: Point, rC: StraightRegion] ~ {
IF CounterClockwise[rC.rightPivot, rC.rightLimit, pL]
THEN {
rC.rightLimit ← pL;
IF rC.rightSwingingInTo #
NIL
AND
NOT Clockwise[rC.rightPivot, rC.rightSwingingInTo, pL]
THEN {
rC.rightSwingingInTo ← NIL;
rC.rightPivot ← rC.rightNextPivot;
};
};
};
StraightSplit: SplitRegionProc ~ {
rR: StraightRegion ← NARROW[regionRight];
rL: StraightRegion ← NewSR[leftPivot: rR.leftPivot, leftNextPivot: rR.leftNextPivot, leftLimit: rR.leftLimit, leftSwingingInTo: rR.leftSwingingInTo];
p: Point ← lineLeft.above;
AdjustLeftLimit[rL, p];
rR.leftPivot ← p; rR.leftLimit ← NIL; rR.leftSwingingInTo ← NIL;
AdjustRightLimit[p, rR];
rL.rightPivot ← p; -- other fields NIL by allocation
RETURN[rL];
};
StraightMerge: MergeRegionProc ~ {
rL: StraightRegion ← NARROW[regionLeft];
rR: StraightRegion ← NARROW[regionRight];
CompressLeft[lineRight, rR]; CompressRight[rL, lineLeft];
AdjustLeftLimit[rL, lineLeft.below]; AdjustRightLimit[lineRight.below, rR];
rL.rightPivot ← rR.rightPivot; rL.rightNextPivot ← rR.rightNextPivot;
rL.rightLimit ← rR.rightLimit; rL.rightSwingingInTo ← rR.rightSwingingInTo;
rR.next ← freeSR; freeSR ← rR;
RETURN[rL];
};
out ← in;
FOR i: INTEGER IN [1..passes]
DO
out ← Sweep[out, NEW[StraightRegionRec ← [leftPivot: NIL, rightPivot: NIL]], StraightStart, StraightStop, StraightSplit, StraightMerge, StraightLineChange];
ENDLOOP;
};
END.