<> <> <> DIRECTORY Sweep; SweepStructureImpl: CEDAR PROGRAM IMPORTS Sweep EXPORTS Sweep = BEGIN OPEN Sweep; InsertLineInPointAbove: PUBLIC PROC [l: Line] ~ { p: Point _ l.above; prev, next: Line; prev _ NIL; next _ p.outgoing; UNTIL next = NIL DO IF CompareSlopes[l, next] = greater THEN EXIT; prev _ next; next _ prev.clockwiseAroundAbove; ENDLOOP; IF prev = NIL THEN p.outgoing _ l ELSE prev.clockwiseAroundAbove _ l; l.clockwiseAroundAbove _ next }; InsertLineInPointBelow: PUBLIC PROC [l: Line] ~ { p: Point _ l.below; prev, next: Line; prev _ NIL; next _ p.incoming; UNTIL next = NIL DO IF CompareSlopes[l, next] = greater THEN EXIT; prev _ next; next _ prev.clockwiseAroundBelow; ENDLOOP; IF prev = NIL THEN p.incoming _ l ELSE prev.clockwiseAroundBelow _ l; l.clockwiseAroundBelow _ next }; RemoveLineFromPointAbove: PUBLIC PROC [l: Line] ~ { p: Point _ l.above; prev, next: Line; prev _ NIL; next _ p.outgoing; UNTIL next = l DO prev _ next; next _ prev.clockwiseAroundAbove; ENDLOOP; IF prev = NIL THEN p.outgoing _ next.clockwiseAroundAbove ELSE prev.clockwiseAroundAbove _ next.clockwiseAroundAbove; l.clockwiseAroundAbove _ NIL; }; RemoveLineFromPointBelow: PUBLIC PROC [l: Line] ~ { p: Point _ l.below; prev, next: Line; prev _ NIL; next _ p.incoming; UNTIL next = l DO prev _ next; next _ prev.clockwiseAroundBelow; ENDLOOP; IF prev = NIL THEN p.incoming _ next.clockwiseAroundBelow ELSE prev.clockwiseAroundBelow _ next.clockwiseAroundBelow; l.clockwiseAroundBelow _ NIL; }; MergePoints: PUBLIC PROC [p1, p2: Point] ~ { MergeIncoming[p2.incoming, p1]; p2.incoming _ NIL; MergeOutgoing[p2.outgoing, p1]; p2.outgoing _ NIL; }; MergeOutgoing: PROC [l: Line, p: Point] ~ { nextLine: Line; UNTIL l = NIL DO nextLine _ l.clockwiseAroundAbove; l.above _ p; InsertLineInPointAbove[l]; l _ nextLine; ENDLOOP; }; MergeIncoming: PROC [l: Line, p: Point] ~ { nextLine: Line; UNTIL l = NIL DO nextLine _ l.clockwiseAroundBelow; l.below _ p; InsertLineInPointBelow[l]; l _ nextLine; ENDLOOP; }; NewGraph: PUBLIC PROC [sizeHint: CARDINAL _ 32] RETURNS [out: Graph] ~ { out _ NEW[GraphRec _ [status: raw, points: NEW[PointSeq[PowerOf2[sizeHint]]]]]; }; NewPoint: PUBLIC PROC [in: Graph, x, y: INT] RETURNS [out: Graph] ~ { OPEN in.points; out _ in; in.status _ raw; ExpandIfNecessary[in]; data[size] _ NEW[PointRec _ [x: x, y: y]]; size _ size + 1; }; LineTo: PUBLIC PROC [in: Graph, x, y: INT, state: REF ANY _ NIL, Flip: FlipLineProc _ NilFlip] RETURNS [out: Graph] ~ { OPEN in.points; l: Line; a, b: Point; r: Relation; out _ in; in.status _ raw; IF size = 0 THEN ERROR; ExpandIfNecessary[in]; a _ data[size-1]; b _ data[size] _ NEW[PointRec _ [x: x, y: y]]; size _ size + 1; BoundsCheck[a]; BoundsCheck[b]; r _ ComparePoints[a, b]; IF r = equal THEN {size _ size - 1; RETURN}; --Skip lines of zero length IF r = less THEN {state _ Flip[state]; b _ a; a _ data[size - 1]}; l _ NEW[LineRec _ [above: a, below: b, state: state]]; InsertLineInEndPoints[l]; }; LastLine: PUBLIC PROC [in: Graph] RETURNS [l: Line] ~ { OPEN in.points; p: Point; IF size = 0 THEN ERROR; p _ data[size - 1]; IF p.incoming = NIL THEN RETURN[p.outgoing] ELSE RETURN[p.incoming]; }; ExpandIfNecessary: PROC [in: Graph] ~ INLINE { OPEN in.points; IF size = max THEN { newPoints: REF PointSeq _ NEW[PointSeq[IF max < 16000 THEN max*2 ELSE max*2 - 10]]; FOR i: CARDINAL IN [0..size) DO newPoints.data[i] _ data[i] ENDLOOP; newPoints.size _ size; in.points _ newPoints; }; }; CopyGraph: PUBLIC PROC [in: Graph, Copy: CopyLineProc _ NilCopy] RETURNS [out: Graph] ~ { OPEN in.points; scan, next, prev: Line; np, p: Point; out _ NEW[GraphRec]; out.status _ in.status; out.points _ NEW[PointSeq[max]]; out.points.size _ size; FOR i: CARDINAL IN [0..size) DO p _ data[i]; out.points.data[i] _ np _ NEW[PointRec _ [x: p.x, y: p.y]]; scan _ p.outgoing; prev _ NIL; WHILE scan # NIL DO IF ISTYPE[scan.state, Line] AND scan.state # NIL THEN { --Line already copied next _ NARROW[scan.state, Line]; next.above _ np; scan.state _ next.state; next.state _ Copy[scan.state]; } ELSE { next _ NEW[LineRec _ [above: np, below: NIL, state: scan.state]]; scan.state _ next; }; IF prev = NIL THEN np.outgoing _ next ELSE prev.clockwiseAroundAbove _ next; prev _ next; scan _ scan.clockwiseAroundAbove; ENDLOOP; scan _ p.incoming; prev _ NIL; WHILE scan # NIL DO IF ISTYPE[scan.state, Line] AND scan.state # NIL THEN { --Line already copied next _ NARROW[scan.state, Line]; next.below _ np; scan.state _ next.state; next.state _ Copy[scan.state]; } ELSE { next _ NEW[LineRec _ [above: NIL, below: np, state: scan.state]]; scan.state _ next; }; IF prev = NIL THEN np.incoming _ next ELSE prev.clockwiseAroundBelow _ next; prev _ next; scan _ scan.clockwiseAroundBelow; ENDLOOP; ENDLOOP; }; DestroyGraph: PUBLIC PROC [in: Graph] ~ { l: Line; p: Point; IF in = NIL THEN RETURN; IF in.status = invalid THEN RETURN; in.status _ invalid; FOR i: CARDINAL IN [0..in.points.size) DO p _ in.points.data[i]; l _ p.outgoing; UNTIL l = NIL DO l.above _ l.below _ NIL; l.clockwiseAroundBelow _ NIL; l _ l.clockwiseAroundAbove; ENDLOOP; p.incoming _ p.outgoing _ NIL; ENDLOOP; }; MergeGraphs: PUBLIC PROC [in1, in2: Graph] RETURNS [out: Graph] ~ { required, displacement: CARDINAL; out _ NEW[GraphRec]; out.status _ raw; IF in1 = NIL THEN { IF in2 = NIL THEN RETURN[NIL] ELSE { out.points _ in2.points; out.status _ in2.status; in2.status _ invalid; RETURN} }; IF in2 = NIL THEN { out.points _ in1.points; out.status _ in1.status; in1.status _ invalid; RETURN}; in1.status _ in2.status _ invalid; required _ in1.points.size + in2.points.size; IF required > in1.points.max THEN { IF required > in2.points.max THEN { out.points _ NEW[PointSeq[PowerOf2[required]]]; out.points.size _ in1.points.size; FOR i: CARDINAL IN [0..in1.points.size) DO out.points.data[i] _ in1.points.data[i]; ENDLOOP; } ELSE {out.points _ in2.points; in2 _ in1} } ELSE {out.points _ in1.points}; displacement _ out.points.size; FOR i: CARDINAL IN [displacement..required) DO out.points.data[i] _ in2.points.data[i-displacement]; ENDLOOP; out.points.size _ required; }; RemoveOrphanPoints: PUBLIC PROC [in: Graph] RETURNS [out: 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; out _ in; }; PowerOf2: PROC [in: CARDINAL] RETURNS [out: CARDINAL _ 32] ~ { UNTIL out >= in DO out _ out * 2; ENDLOOP; IF out > 30000 THEN out _ out - 10; }; EnumerateLines: PUBLIC PROC [in: Graph, LineAction: LineActionProc] RETURNS [quit: BOOL _ FALSE] ~ { l: Line; p: Point; IF in = NIL THEN RETURN; FOR i: CARDINAL IN [0..in.points.size) DO p _ in.points.data[i]; l _ p.outgoing; UNTIL l = NIL DO IF LineAction[l] THEN RETURN[TRUE]; l _ l.clockwiseAroundAbove; ENDLOOP; ENDLOOP; }; Verify: PUBLIC PROC [in: Graph] ~ { OuterAction: PROC [l: Line] RETURNS [quit: BOOL _ FALSE] ~ { global: Line _ l; InnerAction: PROC [l: Line] RETURNS [quit: BOOL _ FALSE] ~ { p: Point; s: LineRelation; s1, s2: EndPointRelation; IF l = global THEN RETURN[TRUE]; [p, s, s1, s2] _ PairIntersection[l, global]; SELECT s FROM intersect => {SELECT s1 FROM above => IF p # l.above THEN ERROR; below => IF p # l.below THEN ERROR; interior, exterior => ERROR; ENDCASE; SELECT s2 FROM above => IF p # global.above THEN ERROR; below => IF p # global.below THEN ERROR; interior, exterior => ERROR; ENDCASE; }; colinear => ERROR; ENDCASE }; IF NOT EnumerateLines[in, InnerAction] THEN ERROR }; [] _ EnumerateLines[in, OuterAction]; }; END.