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