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 | */
|
15 | export 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 | */
|
42 | export 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 |
|
49 | export 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 | */
|
190 | export 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 | */
|
196 | export function quadtree<T = [number, number]>(data: T[], x: (d: T) => number, y: (d: T) => number): Quadtree<T>;
|