SweepStructureImpl.mesa
Copyright © 1985 by Xerox Corporation. All rights reserved.
Greene, September 11, 1986 9:58:29 pm PDT
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.