UNPKG

8.61 kBTypeScriptView Raw
1// Type definitions for D3JS d3-quadtree module 3.0
2// Project: https://github.com/d3/d3-quadtree/, https://d3js.org/d3-quadtree
3// Definitions by: Tom Wanzek <https://github.com/tomwanzek>
4// Alex Ford <https://github.com/gustavderdrache>
5// Boris Yankov <https://github.com/borisyankov>
6// denisname <https://github.com/denisname>
7// Nathan Bierema <https://github.com/Methuselah96>
8// Definitions: https://github.com/DefinitelyTyped/DefinitelyTyped
9
10// Last module patch version validated against: 3.0.1
11
12/**
13 * Leaf node of the quadtree.
14 */
15export interface QuadtreeLeaf<T> {
16 /**
17 * The data associated with this point, as passed to quadtree.add.
18 */
19 data: T;
20
21 /**
22 * The next datum in this leaf, if any.
23 */
24 next?: QuadtreeLeaf<T> | undefined;
25
26 /**
27 * The length property may be used to distinguish leaf nodes from internal nodes: it is undefined for leaf nodes, and 4 for internal nodes.
28 */
29 length?: undefined;
30}
31
32/**
33 * Internal nodes of the quadtree are represented as four-element arrays in left-to-right, top-to-bottom order:
34 *
35 * 0 - the top-left quadrant, if any.
36 * 1 - the top-right quadrant, if any.
37 * 2 - the bottom-left quadrant, if any.
38 * 3 - the bottom-right quadrant, if any.
39 *
40 * A child quadrant may be undefined if it is empty.
41 */
42export interface QuadtreeInternalNode<T> extends Array<QuadtreeInternalNode<T> | QuadtreeLeaf<T> | undefined> {
43 /**
44 * The length property may be used to distinguish leaf nodes from internal nodes: it is undefined for leaf nodes, and 4 for internal nodes.
45 */
46 length: 4;
47}
48
49export interface Quadtree<T> {
50 /**
51 * Returns the current x-accessor, which defaults to: `x(d) => d[0]`.
52 */
53 x(): (d: T) => number;
54 /**
55 * Sets the current x-coordinate accessor and returns the quadtree.
56 * The x-accessors must be consistent, returning the same value given the same input.
57 *
58 * @param x The x-coordinate accessor.
59 */
60 x(x: (d: T) => number): this;
61
62 /**
63 * Returns the current y-accessor, which defaults to: `y(d) => d[1]`.
64 */
65 y(): (d: T) => number;
66 /**
67 * Sets the current y-coordinate accessor and returns the quadtree.
68 * The y-accessors must be consistent, returning the same value given the same input.
69 *
70 * @param y The y-coordinate accessor.
71 */
72 y(y: (d: T) => number): this;
73
74 /**
75 * Returns the quadtree's current extent `[[x0, y0], [x1, y1]]`,
76 * where `x0` and `y0` are the inclusive lower bounds and `x1` and `y1` are the inclusive upper bounds,
77 * or `undefined` if the quadtree has no extent.
78 */
79 extent(): [[number, number], [number, number]] | undefined;
80 /**
81 * Expands the quadtree to cover the specified points `[[x0, y0], [x1, y1]]` and returns the quadtree.
82 * The extent may also be expanded by calling `quadtree.cover` or `quadtree.add`.
83 *
84 * @param extend The specified points to cover.
85 */
86 extent(extend: [[number, number], [number, number]]): this;
87
88 /**
89 * Expands the quadtree to cover the specified point ⟨x,y⟩, and returns the quadtree.
90 * * If the quadtree’s extent already covers the specified point, this method does nothing.
91 * * If the quadtree has an extent, the extent is repeatedly doubled to cover the specified point, wrapping the root node as necessary.
92 * * If the quadtree is empty, the extent is initialized to the extent `[[⌊x⌋, ⌊y⌋], [⌈x⌉, ⌈y⌉]]`.
93 * Rounding is necessary such that if the extent is later doubled, the boundaries of existing quadrants do not change due to floating point error.
94 *
95 * @param x The x-coordinate for the specified point to cover.
96 * @param y The y-coordinate for the specified point to cover.
97 */
98 cover(x: number, y: number): this;
99
100 /**
101 * Adds the specified datum to the quadtree, deriving its coordinates ⟨x,y⟩ using the current x- and y-accessors, and returns the quadtree.
102 * If the new point is outside the current extent of the quadtree, the quadtree is automatically expanded to cover the new point.
103 *
104 * @param datum The specified datum to add.
105 */
106 add(datum: T): this;
107
108 /**
109 * Adds the specified array of data to the quadtree, deriving each element’s coordinates ⟨x,y⟩ using the current x- and y-accessors, and return this quadtree.
110 * This is approximately equivalent to calling quadtree.add repeatedly.
111 * However, this method results in a more compact quadtree because the extent of the data is computed first before adding the data.
112 *
113 * @param data The specified array of data to add.
114 */
115 addAll(data: T[]): this;
116
117 /**
118 * Removes the specified datum to the quadtree, deriving its coordinates ⟨x,y⟩ using the current x- and y-accessors, and returns the quadtree.
119 * If the specified datum does not exist in this quadtree, this method does nothing.
120 *
121 * @param datum The specified datum to remove.
122 */
123 remove(datum: T): this;
124
125 /**
126 * Removes the specified data to the quadtree, deriving their coordinates ⟨x,y⟩ using the current x- and y-accessors, and returns the quadtree.
127 * If a specified datum does not exist in this quadtree, it is ignored.
128 *
129 * @param data The specified array of data to remove.
130 */
131 removeAll(data: T[]): this;
132
133 /**
134 * Returns a copy of the quadtree. All nodes in the returned quadtree are identical copies of the corresponding node in the quadtree;
135 * however, any data in the quadtree is shared by reference and not copied.
136 */
137 copy(): Quadtree<T>;
138
139 /**
140 * Returns the root node of the quadtree.
141 */
142 root(): QuadtreeInternalNode<T> | QuadtreeLeaf<T>;
143
144 /**
145 * Returns an array of all data in the quadtree.
146 */
147 data(): T[];
148
149 /**
150 * Returns the total number of data in the quadtree.
151 */
152 size(): number;
153
154 /**
155 * Returns the datum closest to the position ⟨x,y⟩ with the given search radius. If radius is not specified, it defaults to infinity.
156 * If there is no datum within the search area, returns undefined.
157 *
158 * @param x The x-coordinate for the search position.
159 * @param y The y-coordinate for the search position.
160 * @param radius The optional search radius.
161 */
162 find(x: number, y: number, radius?: number): T | undefined;
163
164 /**
165 * Visits each node in the quadtree in pre-order traversal, invoking the specified callback with arguments `node`, `x0`, `y0`, `x1`, `y1` for each node,
166 * where `node` is the node being visited, ⟨x0, y0⟩ are the lower bounds of the node, and ⟨x1, y1⟩ are the upper bounds, and returns the quadtree.
167 *
168 * If the callback returns true for a given node, then the children of that node are not visited; otherwise, all child nodes are visited.
169 * This can be used to quickly visit only parts of the tree.
170 * Note, however, that child quadrants are always visited in sibling order: top-left, top-right, bottom-left, bottom-right.
171 * In cases such as search, visiting siblings in a specific order may be faster.
172 *
173 * @param callback The callback invoked for each node.
174 */
175 visit(callback: (node: QuadtreeInternalNode<T> | QuadtreeLeaf<T>, x0: number, y0: number, x1: number, y1: number) => void | boolean): this;
176
177 /**
178 * Visits each node in the quadtree in post-order traversal, invoking the specified callback with arguments `node`, `x0`, `y0`, `x1`, `y1` for each node,
179 * where `node` is the node being visited, ⟨x0, y0⟩ are the lower bounds of the node, and ⟨x1, y1⟩ are the upper bounds, and returns the quadtree.
180 *
181 * @param callback The callback invoked for each node.
182 */
183 visitAfter(callback: (node: QuadtreeInternalNode<T> | QuadtreeLeaf<T>, x0: number, y0: number, x1: number, y1: number) => void): this;
184}
185
186/**
187 * Creates a new, empty quadtree with an empty extent and the default x- and y-accessors.
188 * If data is specified, adds the specified array of data to the quadtree.
189 */
190export function quadtree<T = [number, number]>(data?: T[]): Quadtree<T>;
191/**
192 * Creates a new, empty quadtree with an empty extent and the default x- and y-accessors.
193 * Adds the specified array of data to the quadtree.
194 * Sets the x- and y- accessors to the specified functions before adding the specified array of data to the quadtree.
195 */
196export function quadtree<T = [number, number]>(data: T[], x: (d: T) => number, y: (d: T) => number): Quadtree<T>;