Sweep.mesa
Copyright © 1985 by Xerox Corporation. All rights reserved.

DIRECTORY

Sweep: CEDAR DEFINITIONS =

BEGIN

Point: TYPE = REF PointRec;

PointRec: TYPE = RECORD[
x, y: INT,
incoming, outgoing: Line ← NIL

];

Line: TYPE = REF LineRec;

LineRec: TYPE = RECORD[

];

The meaning of the state field is supplied by the client.

GraphStatus: TYPE = {raw, planar, invalid};

Graph: TYPE = REF GraphRec;

GraphRec: TYPE = RECORD[

];

PointSeq: TYPE = RECORD[size: CARDINAL ← 0, data: SEQUENCE max: CARDINAL OF Point];

*** Callback procedures for Intersect ***

CopyLineProc: TYPE = PROC [stateIn: REF ANY] RETURNS [stateOut: REF ANY];

When Intersect breaks a line in two pieces Copy is called to get a new state. Copy usually just returns its stateIn pointer (if line states are immutable), or generates a new identical copy of its original state.

NilCopy: CopyLineProc;

CombineLineProc: TYPE = PROC [state1, state2: REF ANY] RETURNS [state: REF ANY];

When lines are coincident, or become coincident because of slight movements during intersection Combine is called to generate one line state from two.

NilCombine: CombineLineProc;

FlipLineProc: TYPE = PROC [stateIn: REF ANY] RETURNS [stateOut: REF ANY];

When lines are input upside down, or when they flip due to intersections (rarely), the Flip procedure is called.

NilFlip: FlipLineProc;

Intersect: PROC [in: Graph, Copy: CopyLineProc ← NilCopy, Combine: CombineLineProc ← NilCombine, Flip: FlipLineProc ← NilFlip] RETURNS [out: Graph];

Intersect takes a raw graph where lines may intersect, touch, or coincide, and produces a graph where all such interactions are explicit in the graph. That is, no lines intersect without sharing a point at the intersection. Intersect destroys its input, and produces output that is suitable for Sweep below.

*** Callback procedures for Sweep ***

Except as noted below these Callbacks should not delete lines from the data structure, and they should only insert new lines that are interior to the region, and above the point being processed. Since the data structure has already been processed with Intersect, these procedures can trust the topology.

StartRegionProc: TYPE = PROC [lineLeft, lineRight: Line, regionPrevious: REF ANY] RETURNS [regionCenter: REF ANY];

The client can derive a state for the new regionCenter by using lineRight, and it's right neighbor regionPrevious. The order of region processing guarantees that regionPrevious is already Started.

NilStart: StartRegionProc;

StopRegionProc: TYPE = PROC [lineLeft: Line, regionCenter: REF ANY, lineRight: Line];

The Stop Callback can remove lineLeft.

NilStop: StopRegionProc;

SplitRegionProc: TYPE = PROC [lineLeft, lineRight: Line, regionRight: REF ANY, regionPrevious: REF ANY ← NIL] RETURNS [regionLeft: REF ANY];

The central region, regionCenter, will be used for the right region, the client must produce and return the left region. regionPrevious is the immediate right neighbor of lineLeft. Together with StartRegionProc's regionRight, the regionPrevious pointer gives the client an opportunity to set the state of each line with respect to its neighbor regions.

NilSplit: SplitRegionProc;

MergeRegionProc: TYPE = PROC [regionLeft: REF ANY, lineLeft, lineRight: Line, regionRight: REF ANY] RETURNS [regionCenter: REF ANY];

The Merge Callback can remove lineRight (lineLeft may have been deleted by an earlier StopRegionProc, so watch for NIL fields.)

NilMerge: MergeRegionProc;

LeftOrRight: TYPE = {left, right};

LineChangeRegionProc: TYPE = PROC [lineOld, lineNew: Line, side: LeftOrRight, regionCenter: REF ANY, regionPrevious: REF ANY ← NIL];

The side variable indicates which side of the region has the changing lines (Read line change on right/left of region.)

If side = left then it is ok to delete lineOld, and regionPrevious will be NIL.

If side = right then lineOld may have been deleted already, and regionPrevious will be the right neighbor of lineNew (this is included for symmetry with the SplitRegionProc).

NilLineChange: LineChangeRegionProc;

Sweep: PROC [in: Graph, infinityRegion: REF ANY ← NIL, Start: StartRegionProc ← NilStart, Stop: StopRegionProc ← NilStop, Split: SplitRegionProc ← NilSplit, Merge: MergeRegionProc ← NilMerge, LineChange: LineChangeRegionProc ← NilLineChange] RETURNS [out: Graph];

At each Point in order, the Callbacks are applied in clockwise order. so that the region to the left of the current point is processed last. The "in" graph must be Intersected before it can be Swept, and Sweeping the graph destroys "in" ("out", however, can be used for subsequent sweeps).

*** Basic Line and Point Manipulation implemented in SweepStructureImpl.mesa ***

* operations on Lines and Points *

InsertLineInPointAbove: PROC [l: Line];

Add l to the outgoing list of l.above

InsertLineInPointBelow: PROC [l: Line];

InsertLineInEndPoints: PROC [l: Line] ~ INLINE {

RemoveLineFromPointAbove: PROC [l: Line];

Remove l from the outgoing list of l.above

RemoveLineFromPointBelow: PROC [l: Line];

RemoveLineFromEndPoints: PROC [l: Line] ~ INLINE {

MergePoints: PROC [p1, p2: Point];

The lines around p2 are added to p1.

* operations on Graphs *

NewPoint: PROC [in: Graph, x, y: INT] RETURNS [out: Graph];

LineTo: PROC [in: Graph, x, y: INT, state: REF ANY ← NIL, Flip: FlipLineProc ← NilFlip] RETURNS [out: Graph];

Add a new point, and a line connecting the new point with the most recently entered point.

LastLine: PROC [in: Graph] RETURNS [l: Line];

Returns the most recent LineTo.

NewGraph: PROC [sizeHint: CARDINAL ← 32] RETURNS [out: Graph];

CopyGraph: PROC [in: Graph, Copy: CopyLineProc ← NilCopy] RETURNS [out: Graph];

CopyGraph depends on the client having never used a direct pointer to a line for a line state. (If you really want to have line states point to other lines, then use an enclosing record to change the type.)

DestroyGraph: PROC [in: Graph];

Smash all pointers in a collection of points and lines (otherwise circularities will foul up garbage collection.)

MergeGraphs: PROC [in1, in2: Graph] RETURNS [out: Graph];

RemoveOrphanPoints: PROC [in: Graph] RETURNS [out: Graph];

Verify: PROC [in: Graph];

An n^2 verification that the lines of ll only intersect explicitly. (For testing only.)

LineActionProc: TYPE = PROC [l: Line] RETURNS [quit: BOOL ← FALSE];

EnumerateLines: PROC [in: Graph, LineAction: LineActionProc] RETURNS [quit: BOOL ← FALSE];

Apply LineAction to all the lines in the graph. (Points can be enumerated directly from the ''points" sequence in the GraphRec.)

StraightenLines: PROC [in: Graph] RETURNS [out: Graph];

All degree two points that do not bend the line more than 1 unit off course are removed.

*** Basic Arithmetic Implemented in SweepArithImpl.mesa ***

InputOutOfRange: ERROR;

BoundsCheck: PUBLIC PROC [p: Point];

Checks that the coordinates of p are within the range of the current SweepArithImpl, raises InputOutOfRange if not.

Relation: TYPE = Basics.Comparison;

ComparePoints: PROC [p1, p2: Point] RETURNS [Relation];

Compares points using y coordinates primary, x coordinates secondary.

CompareSlopes: PROC [l1, l2: Line] RETURNS [Relation];

Compares (minus inverse) slopes -DeltaX/DeltaY. Horizontal lines are negative infinity

ComparePointLine: PUBLIC PROC [p: Point, l: Line] RETURNS [Relation];

Compares p with l horizontally at the y coordinate of p.

CompareLinesAtY: PROC [l1, l2: Line, p: Point] RETURNS [Relation];

Compares lines at the y coordinate of p. CompareSlopes is used for tie breaking.

LineRelation: TYPE = {parallel, colinear, intersect, other};

EndPointRelation: TYPE = {exterior, above, interior, below};

PairIntersection: PROC [l1: Line, l2: Line] RETURNS [p: Point← NIL, s: LineRelation, s1, s2: EndPointRelation ← exterior];

Intersect two lines.

END.