<<>> <> <> <> DIRECTORY G2dBasic, IO, Rope; G2dQuadtree: CEDAR DEFINITIONS ~ BEGIN ROPE: TYPE ~ Rope.ROPE; Pair: TYPE ~ G2dBasic.Pair; <> <> <> <<>> Edge: TYPE ~ {l, r, b, t}; Quadrant: TYPE ~ MACHINE DEPENDENT {lt(0), lb(1), rt(2), rb(3)}; <> Quadtree: TYPE ~ REF QuadtreeRep; QuadtreeRep: TYPE ~ RECORD [ root: Square ¬ NIL, -- the Quadtree root name: ROPE ¬ NIL, -- name of Octree radius, terminalRadius: REAL ¬ 0.0, -- half edge length of root, leaf diameter, terminalDiameter: REAL ¬ 0.0, -- edge length of root, leaf nSquares, nTerminalSquares: CARD ¬ 0, -- # squares and terminal squares refAny: REF ANY ¬ NIL -- a potentially useful pointer ]; <> Square: TYPE ~ REF SquareRep; SquareRep: TYPE ~ RECORD [ parent: Square ¬ NIL, -- parent square quadrant: Quadrant ¬ lb, -- relation to parent square terminal: BOOL ¬ FALSE, -- if true, leaf node corners: Corners ¬ ALL[NIL], -- corner locations and info kids: Kids ¬ ALL[NIL], -- subdivided square refAny: REF ANY ¬ NIL -- a potentially useful pointer ]; Kids: TYPE ~ ARRAY Quadrant OF Square; Stack: TYPE ~ REF StackRep; StackRep: TYPE ~ RECORD [ top: NAT ¬ 0, bottom: NAT ¬ 0, size: NAT ¬ 0, maxSize: NAT ¬ 0, element: SEQUENCE maxLength: NAT OF Square ]; <> Cross: TYPE ~ REF CrossRep; CrossRep: TYPE ~ RECORD [ id: INTEGER ¬ -1, -- vertex id value: REAL ¬ 0.0, -- spatial value point: Pair ¬ [0, 0] -- location of surface vertex ]; CrossedEdge: TYPE ~ RECORD [ -- a surface-crossedEdge edge cIn, cOut: Corner ¬ NIL, -- inside and outside corners oIn, oOut: Quadrant -- and their quadrants ]; CrossedEdges: TYPE ~ ARRAY Edge OF CrossedEdge; -- possible edge-surface inter. <> Corner: TYPE ~ REF CornerRep; CornerRep: TYPE ~ RECORD [ point: Pair ¬ [0, 0], -- location of corner valueSet: BOOL ¬ FALSE, -- true if value computed value: REAL ¬ 0.0, -- surface value at corner inside: BOOL ¬ FALSE, -- if valueSet & value > 0 lCross: Cross ¬ NIL, -- leftward surface intersection bCross: Cross ¬ NIL -- bottomward surface intersection ]; Corners: TYPE ~ ARRAY Quadrant OF Corner; <> TwoQuadrants: TYPE ~ RECORD [q0, q1: Quadrant]; TwoCorners: TYPE ~ RECORD [c0, c1: Corner]; <> SquareProc: TYPE ~ PROC [s: Square] RETURNS [continue: BOOL ¬ TRUE]; << Procedure for operating on a square and its descendents.>> <> NewSquare: PROC [size: REAL, center: Pair ¬ [0, 0]] RETURNS [Square]; <> <> AddSquare: PROC [square: Square, edge: Edge] RETURNS [root: Square]; <> <> ApplyToTerminal: PROC [square: Square, squareProc: SquareProc]; <> <> OppositeQuadrant: PROC [q: Quadrant] RETURNS [Quadrant]; <> <<>> EdgeQuadrants: PROC [edge: Edge] RETURNS [TwoQuadrants]; <> <<>> DirectionFromQuadrants: PROC [quadrant0, quadrant1: Quadrant] RETURNS [Edge]; <> <<>> NextCWEdge: PROC [edge: Edge] RETURNS [Edge]; <> EdgeCorners: PROC [square: Square, edge: Edge] RETURNS [TwoCorners]; <> <> <> EdgeNeighbor: PROC [square: Square, edge: Edge] RETURNS [Square]; <> <> StackOverflow: ERROR; StackUnderflow: ERROR; NewStack: PROC [length: NAT] RETURNS [Stack]; <> WriteBottomOfStack: PROC [square: Square, stack: Stack]; <> ReadTopOfStack: PROC [stack: Stack] RETURNS [Square]; <> END.