G2dQuadtree.mesa
Copyright Ó 1990, 1992 by Xerox Corporation. All rights reserved.
Bloomenthal, July 1, 1992 7:03 pm PDT
DIRECTORY G2dBasic, IO, Rope;
G2dQuadtree: CEDAR DEFINITIONS
~ BEGIN
ROPE:  TYPE ~ Rope.ROPE;
Pair:  TYPE ~ G2dBasic.Pair;
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),
Edge:      TYPE ~ {l, r, b, t};
Quadrant:    TYPE ~ MACHINE DEPENDENT {lt(0), lb(1), rt(2), rb(3)};
The Quadtree
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
];
Squares, Sequences, and Stacks
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
];
Crossing a Surface
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.
Corners
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;
Miscellany
TwoQuadrants:   TYPE ~ RECORD [q0, q1: Quadrant];
TwoCorners:    TYPE ~ RECORD [c0, c1: Corner];
CallBacks
SquareProc:    TYPE ~ PROC [s: Square] RETURNS [continue: BOOL ¬ TRUE];
         Procedure for operating on a square and its descendents.
Allocation
NewSquare: PROC [size: REAL, center: Pair ¬ [0, 0]] RETURNS [Square];
Create a new square; its quadrant defaults to lbn and its level is 0.
Modification
AddSquare: PROC [square: Square, edge: Edge] RETURNS [root: Square];
If the edge neighbor of square doesn't exist, allocate it, creating any required parents.
Callback
ApplyToTerminal: PROC [square: Square, squareProc: SquareProc];
Apply squareProc to all terminal descendents of square.
Directions
OppositeQuadrant: PROC [q: Quadrant] RETURNS [Quadrant];
Return the diametrically opposite quadrant.
EdgeQuadrants: PROC [edge: Edge] RETURNS [TwoQuadrants];
Return the two quadrants connected by edge.
DirectionFromQuadrants: PROC [quadrant0, quadrant1: Quadrant] RETURNS [Edge];
Return the direction which takes quadrant0 to quadrant1.
NextCWEdge: PROC [edge: Edge] RETURNS [Edge];
Return the next edge clockwise around face; no checking that edge and face agree.
EdgeCorners: PROC [square: Square, edge: Edge] RETURNS [TwoCorners];
Return the two corners at square's edge.
In the TwoCorners record, l precedes r, b precedes t, and n precedes f.
Neighbors
EdgeNeighbor: PROC [square: Square, edge: Edge] RETURNS [Square];
Return the neighbor next to square's edge; return NIL if no such neighbor.
Stack Support
StackOverflow: ERROR;
StackUnderflow: ERROR;
NewStack: PROC [length: NAT] RETURNS [Stack];
Create a new stack of squares capable of storing length squares
WriteBottomOfStack: PROC [square: Square, stack: Stack];
Add square to the bottom of the stack; may raise ERROR StackOverflow.
ReadTopOfStack: PROC [stack: Stack] RETURNS [Square];
Read a square from the top of the stack; may raise ERROR StackUnderflow.
END.