SXQuadTree.mesa: Spinifex flavour of Quad Trees
Copyright c 1985 by Xerox Corporation. All rights reserved.
Written by Beretta, June 3, 1985 2:54:18 pm PDT
Last Edited by: Beretta, June 29, 1985 7:49:05 pm PDT
DIRECTORY
CD USING [Number, Rect],
CDBasics USING [empty]
;
SXQuadTree: CEDAR DEFINITIONS = BEGIN
Rectangle:
TYPE =
RECORD [
interestBound: CD.Rect, -- Bounding box of region which Rectangle influences.
dimDecr: RectDelta, -- Decrement to be applied to interestBound give actual dimension.
nodeInformation: REF ANY -- CircuitNode for conductive primitive rects, cell application for cells.
];
Rectangles: TYPE = LIST OF REF Rectangle ← NIL;
RectDelta:
TYPE =
RECORD [
-- A space saving Hack. Allows interest bloats of no more than 255/Lambda. Also requires strict containment of Rectangle's dimension in its InterestBoundary.
dx1, dy1, dx2, dy2: [0..256)
];
AreaSplit: TYPE = {north, south, east, west};
QuadTreeRoot:
TYPE =
RECORD [
size: CD.Rect ← CDBasics.empty,
geometry: REF QuadTree ← NIL,
private: Rectangles ← NIL -- hack for internal use
];
QuadTree:
TYPE =
RECORD [
boxes: Rectangles,
midX, midY: CD.Number ← 0,
subTrees: ARRAY AreaSplit OF REF QuadTree ← ALL[NIL] -- Note SubTrees overlap! North or South is prefered over East or West distribution.
];
Dimension:
PROCEDURE [r:
REF Rectangle]
RETURNS [
CD.Rect] =
INLINE {
RETURN [[x1: r.interestBound.x1+r.dimDecr.dx1,
y1: r.interestBound.y1+r.dimDecr.dy1,
x2: r.interestBound.x2-r.dimDecr.dx2,
y2: r.interestBound.y2-r.dimDecr.dy2]];
};
PerRectProc: TYPE = PROCEDURE [r: REF Rectangle, data: REF ANY];
Create:
PROCEDURE [quadTree: QuadTreeRoot]
RETURNS [newQuadTree: QuadTreeRoot];
Hack. When all rectangles are known, also the bounding box of their union is known, and the Quad Tree can be created a least.
Store:
PROCEDURE [quadTree: QuadTreeRoot, rect:
REF Rectangle]
RETURNS [newQuadTree: QuadTreeRoot];
Stores a rectangle for subsequent insertion into a Quad Tree.
Enumerate:
PROCEDURE [quadTree: QuadTreeRoot, clipRect:
CD.Rect, PerRect: PerRectProc, data:
REF
ANY ←
NIL]
Interim procedure.
END.