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]; 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. 8 G2dQuadtree.mesa Copyright Σ 1990, 1992 by Xerox Corporation. All rights reserved. Bloomenthal, July 1, 1992 7:03 pm PDT Topology There are four basic directions: l: left (lesser in x), r: right (greater in x), b: bottom (lesser in y), t: top (greater in y), The Quadtree Squares, Sequences, and Stacks Crossing a Surface Corners Miscellany CallBacks Procedure for operating on a square and its descendents. Allocation Create a new square; its quadrant defaults to lbn and its level is 0. Modification If the edge neighbor of square doesn't exist, allocate it, creating any required parents. Callback Apply squareProc to all terminal descendents of square. Directions Return the diametrically opposite quadrant. Return the two quadrants connected by edge. Return the direction which takes quadrant0 to quadrant1. Return the next edge clockwise around face; no checking that edge and face agree. Return the two corners at square's edge. In the TwoCorners record, l precedes r, b precedes t, and n precedes f. Neighbors Return the neighbor next to square's edge; return NIL if no such neighbor. Stack Support Create a new stack of squares capable of storing length squares Add square to the bottom of the stack; may raise ERROR StackOverflow. Read a square from the top of the stack; may raise ERROR StackUnderflow. ΚZ•NewlineDelimiter –"cedarcode" style™šœ™Jšœ Οeœ7™BJ™%J˜JšΟk œ˜J˜—šΠbl œžœž ˜Jšž˜J˜Jšžœžœžœ˜Jšœžœ˜—headšΟl™™ J™_J™—Jšœ žœ˜J˜Jšœ žœžœž œ˜C—š  ™ Jšœ žœžœ ˜%šœžœžœ˜JšœžœΟc˜2Jšœ žœžœ‘˜.Jšœžœ ‘!˜KJšœžœ ‘˜HJšœžœ ‘!˜KJšœžœžœžœ‘˜>J˜——š ™Jšœ žœžœ ˜!šœ žœžœ˜Jšœžœ‘˜/Jšœ"‘˜>Jšœžœžœ‘˜6Jšœžœžœ‘˜@Jšœžœžœ‘˜4Jšœžœžœžœ‘˜>J˜J˜—šœ žœžœ žœ˜+J˜—Jšœžœžœ ˜ šœ žœžœ˜Jšœ žœ˜Jšœžœ˜Jšœ žœ˜Jšœžœ˜Jšœžœ žœžœ˜0J˜——š ™Jšœ žœžœ ˜ šœžœžœ˜Jšœ žœ ‘ ˜)Jšœžœ ‘˜.Jšœ ‘˜=J˜J˜—šœžœžœ‘˜CJšœžœ‘˜@Jšœ‘˜6J˜J˜—Jšœžœžœžœ‘˜Q—š ™Jšœ žœžœ ˜!šœžœžœ˜Jšœ!‘˜6Jšœžœžœ‘˜:Jšœžœ ‘˜8Jšœžœžœ‘˜9Jšœžœ‘ ˜?Jšœžœ‘"˜@J˜J˜—Jšœ žœžœ žœ˜-—š  ™ Jšœ žœžœ˜1Jšœžœžœ˜.—š  ™ š œžœžœ žœ žœžœ˜GJ™A——š  ™ šΟn œžœžœžœ ˜EJ™E——š  ™ š’ œžœžœ˜DJšœY™Y——š ™š’œžœ*˜?J™7——š  ™ š’œžœžœ ˜8J™+J™—š’ œžœžœ˜8J™+J™—š’œžœ"žœ˜MJ™8J™—š’ œžœžœ˜-J™QJ˜—š’ œžœžœ˜DJ™(J™G——š  ™ š’ œžœžœ ˜AJšœ2Οsœ™J——š  ™ Jšœžœ˜Jšœžœ˜J˜š’œžœ žœžœ ˜-J™?J˜—š’œžœ ˜8Jšœ1£œ™EJ˜—š’œžœžœ ˜5Jšœ3£œ™H——J˜Jšžœ˜J˜—…— Κ\