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 ANYNIL]
Interim procedure.
END.