<> <> 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]; <<*** Callback procedures for Intersect ***>> 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]; <> <<>> <<*** Callback procedures for Sweep ***>> <<>> <> 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]; <> <<>> <<>> <<*** Basic Line and Point Manipulation implemented in SweepStructureImpl.mesa ***>> <<* operations on Lines and Points *>> 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]; <> <<* 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]; <> 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]; <> <<*** Basic Arithmetic Implemented in SweepArithImpl.mesa ***>> 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.