DIRECTORY Basics USING [Comparison]; 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[ above, below: Point, clockwiseAroundAbove: Line _ NIL, clockwiseAroundBelow: Line _ NIL, state: REF ANY _ NIL ]; GraphStatus: TYPE = {raw, planar, invalid}; Graph: TYPE = REF GraphRec; GraphRec: TYPE = RECORD[ status: GraphStatus, points: REF PointSeq ]; PointSeq: TYPE = RECORD[size: CARDINAL _ 0, data: SEQUENCE max: CARDINAL OF Point]; CopyLineProc: TYPE = PROC [stateIn: REF ANY] RETURNS [stateOut: REF ANY]; NilCopy: CopyLineProc; CombineLineProc: TYPE = PROC [state1, state2: REF ANY] RETURNS [state: REF ANY]; NilCombine: CombineLineProc; FlipLineProc: TYPE = PROC [stateIn: REF ANY] RETURNS [stateOut: REF ANY]; NilFlip: FlipLineProc; Intersect: PROC [in: Graph, Copy: CopyLineProc _ NilCopy, Combine: CombineLineProc _ NilCombine, Flip: FlipLineProc _ NilFlip] RETURNS [out: Graph]; StartRegionProc: TYPE = PROC [lineLeft, lineRight: Line, regionPrevious: REF ANY] RETURNS [regionCenter: REF ANY]; NilStart: StartRegionProc; StopRegionProc: TYPE = PROC [lineLeft: Line, regionCenter: REF ANY, lineRight: Line]; NilStop: StopRegionProc; SplitRegionProc: TYPE = PROC [lineLeft, lineRight: Line, regionRight: REF ANY, regionPrevious: REF ANY _ NIL] RETURNS [regionLeft: REF ANY]; NilSplit: SplitRegionProc; MergeRegionProc: TYPE = PROC [regionLeft: REF ANY, lineLeft, lineRight: Line, regionRight: REF ANY] RETURNS [regionCenter: REF ANY]; NilMerge: MergeRegionProc; LeftOrRight: TYPE = {left, right}; LineChangeRegionProc: TYPE = PROC [lineOld, lineNew: Line, side: LeftOrRight, regionCenter: REF ANY, regionPrevious: REF ANY _ NIL]; 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]; InsertLineInPointAbove: PROC [l: Line]; InsertLineInPointBelow: PROC [l: Line]; InsertLineInEndPoints: PROC [l: Line] ~ INLINE { InsertLineInPointAbove[l]; InsertLineInPointBelow[l] }; RemoveLineFromPointAbove: PROC [l: Line]; RemoveLineFromPointBelow: PROC [l: Line]; RemoveLineFromEndPoints: PROC [l: Line] ~ INLINE { RemoveLineFromPointAbove[l]; RemoveLineFromPointBelow[l] }; MergePoints: PROC [p1, p2: Point]; 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]; LastLine: PROC [in: Graph] RETURNS [l: Line]; NewGraph: PROC [sizeHint: CARDINAL _ 32] RETURNS [out: Graph]; CopyGraph: PROC [in: Graph, Copy: CopyLineProc _ NilCopy] RETURNS [out: Graph]; DestroyGraph: PROC [in: Graph]; MergeGraphs: PROC [in1, in2: Graph] RETURNS [out: Graph]; RemoveOrphanPoints: PROC [in: Graph] RETURNS [out: Graph]; Verify: PROC [in: Graph]; LineActionProc: TYPE = PROC [l: Line] RETURNS [quit: BOOL _ FALSE]; EnumerateLines: PROC [in: Graph, LineAction: LineActionProc] RETURNS [quit: BOOL _ FALSE]; StraightenLines: PROC [in: Graph] RETURNS [out: Graph]; InputOutOfRange: ERROR; BoundsCheck: PUBLIC PROC [p: Point]; Relation: TYPE = Basics.Comparison; ComparePoints: PROC [p1, p2: Point] RETURNS [Relation]; CompareSlopes: PROC [l1, l2: Line] RETURNS [Relation]; ComparePointLine: PUBLIC PROC [p: Point, l: Line] RETURNS [Relation]; CompareLinesAtY: PROC [l1, l2: Line, p: Point] RETURNS [Relation]; 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]; END. œSweep.mesa Copyright c 1985 by Xerox Corporation. All rights reserved. Greene, September 11, 1986 11:00:16 pm PDT The meaning of the state field is supplied by the client. *** Callback procedures for Intersect *** 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. When lines are coincident, or become coincident because of slight movements during intersection Combine is called to generate one line state from two. When lines are input upside down, or when they flip due to intersections (rarely), the Flip procedure is called. 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. 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. The Stop Callback can remove lineLeft. 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. The Merge Callback can remove lineRight (lineLeft may have been deleted by an earlier StopRegionProc, so watch for NIL fields.) 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). 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 * Add l to the outgoing list of l.above Remove l from the outgoing list of l.above The lines around p2 are added to p1. * operations on Graphs * Add a new point, and a line connecting the new point with the most recently entered point. Returns the most recent LineTo. 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.) Smash all pointers in a collection of points and lines (otherwise circularities will foul up garbage collection.) An n^2 verification that the lines of ll only intersect explicitly. (For testing only.) Apply LineAction to all the lines in the graph. (Points can be enumerated directly from the ''points" sequence in the GraphRec.) All degree two points that do not bend the line more than 1 unit off course are removed. *** Basic Arithmetic Implemented in SweepArithImpl.mesa *** Checks that the coordinates of p are within the range of the current SweepArithImpl, raises InputOutOfRange if not. Compares points using y coordinates primary, x coordinates secondary. Compares (minus inverse) slopes -DeltaX/DeltaY. Horizontal lines are negative infinity Compares p with l horizontally at the y coordinate of p. Compares lines at the y coordinate of p. CompareSlopes is used for tie breaking. Intersect two lines. Ê«˜šœÏmœ1™GIcode™*—J˜šÏk ˜ Kšœžœ˜—K˜KšÏnœžœž œ˜J˜Jšž˜J˜Jšœžœžœ ˜Jšœ žœžœžœž˜BJ˜J˜J˜Jšœžœžœ ˜šœ žœžœ˜Jšœ˜Jšœžœ˜!Jšœžœ˜!Jšœžœžœž˜—J˜Jšœ9™9J˜J˜Jšœ žœ˜+J˜Jšœžœžœ ˜šœ žœžœ˜J˜Jšœžœ ˜—J˜Jš œ žœžœžœ žœžœžœ˜SJ˜J˜J˜Jšœ)™)J˜Jšœžœžœ žœžœžœ žœžœ˜IJ™ÔJ˜KšŸœ˜J˜Jšœžœžœžœžœžœ žœžœ˜PJ™–J˜KšŸ œ˜K˜Jšœžœžœ žœžœžœ žœžœ˜IJ™pJ˜KšŸœ˜J˜Kš Ÿ œžœ ŸœŸœ Ÿœžœ˜”Kšœµ™µK™K˜Kšœ%™%K™K™±K˜Kšœžœžœ-žœžœžœžœžœ˜rK™ÅK˜KšŸœ˜K˜Kš œžœžœ žœžœ˜UK™&K˜KšŸœ˜K˜Kšœžœžœ*žœžœžœžœžœžœžœžœ˜ŒK™ãK˜KšŸœ˜K˜Kšœžœžœžœžœ*žœžœžœžœžœ˜„K™K˜KšŸœ˜K˜Kšœ žœ˜"K˜Kšœžœžœ;žœžœžœžœžœ˜„K™wK™OK™®K˜KšŸ œ˜$K˜KšŸœžœžœžœžœŸœŸœŸœŸœŸ œ(žœ˜‡™¤K™K™—KšœP™PK˜K™"K˜KšŸœžœ ˜'Kšœ%™%K˜KšŸœžœ ˜'K˜šŸœžœžœ˜1Kšœ8˜8—K˜KšŸœžœ ˜)Kšœ*™*K˜KšŸœžœ ˜)K˜šŸœžœ žœ˜2Kšœ;˜;—K˜KšŸ œžœ˜"K™$K˜K™K˜KšŸœžœžœžœ˜