<> <> <> 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.