1 | # quadtree-ts
|
2 |
|
3 | * [Docs and examples](#docs-and-examples)
|
4 | * [Install](#install)
|
5 | * [Use](#use)
|
6 | * [Shapes](#shapes)
|
7 | * [Custom data](#custom-data)
|
8 | * [Custom integration](#custom-integration)
|
9 | * [Typescript](#typescript)
|
10 | * [browser-support](#browser-support)
|
11 | * [Development scripts](#development-scripts)
|
12 | * [Migration from quadtree-js](#migration-from-quadtree-js)
|
13 |
|
14 | This library can store and retrieve *Rectangles, Circles and Lines* in a recursive 2D quadtree. Every node can hold a maximum number of objects before it splits into four subnodes. Objects are only stored on leaf nodes (the lowest level). If an object overlaps into multiple leaf nodes, a reference to the object is stored in each node.
|
15 |
|
16 | This is a fork of [@timohausmann/quadtree-js](https://github.com/timohausmann/quadtree-js) using Typescript and supporting primitives and overall better extensibility.
|
17 |
|
18 | ## Docs and examples
|
19 |
|
20 | * [Homepage](https://timohausmann.github.io/quadtree-ts/)
|
21 | * [Examples](https://timohausmann.github.io/quadtree-ts/examples/simple/)
|
22 | * [Docs](https://timohausmann.github.io/quadtree-ts/documentation/)
|
23 |
|
24 | ## Install
|
25 |
|
26 | Install this module via [npm](https://www.npmjs.com/package/@timohausmann/quadtree-ts) and import or require it:
|
27 |
|
28 | ```bash
|
29 | npm install --save-dev @timohausmann/quadtree-ts
|
30 | ```
|
31 |
|
32 | ```javascript
|
33 | // ES6
|
34 | import { Quadtree } from '@timohausmann/quadtree-ts';
|
35 | // CommonJS
|
36 | const { Quadtree } = require('@timohausmann/quadtree-ts');
|
37 | ```
|
38 |
|
39 | Alternatively, [download the source](https://github.com/timohausmann/quadtree-ts/archive/master.zip) and include it the old-fashioned way, or use an awesome CDN like [jsdelivr](https://www.jsdelivr.com/package/npm/@timohausmann/quadtree-ts) or [unpkg](https://unpkg.com/browse/@timohausmann/quadtree-ts@latest/). (If you only need Rectangles and want to save some bytes, use `quadtree.umd.basic.js` instead):
|
40 |
|
41 | ```html
|
42 | <!-- self-hosted -->
|
43 | <script src="quadtree.umd.full.js"></script>
|
44 | <!-- CDN jsdelivr -->
|
45 | <script src="https://cdn.jsdelivr.net/npm/@timohausmann/quadtree-ts/dist/quadtree.umd.full.js"></script>
|
46 | <!-- CDN unpkg -->
|
47 | <script src="https://unpkg.com/@timohausmann/quadtree-ts/dist/quadtree.umd.full.js"></script>
|
48 | ```
|
49 |
|
50 |
|
51 | ## Use
|
52 |
|
53 | Create a new Quadtree:
|
54 |
|
55 | ```javascript
|
56 | import { Quadtree } from '@timohausmann/quadtree-ts';
|
57 |
|
58 | const myTree = new Quadtree({
|
59 | width: 800,
|
60 | height: 600,
|
61 | x: 0, // optional, default: 0
|
62 | y: 0, // optional, default: 0
|
63 | maxObjects: 10, // optional, default: 10
|
64 | maxLevels: 4 // optional, default: 4
|
65 | });
|
66 | ```
|
67 |
|
68 | The tree and each node may have four subnodes that are arranged like this:
|
69 |
|
70 | | II | I |
|
71 | |-------|-------|
|
72 | | III | IV |
|
73 |
|
74 | Optional properties:
|
75 | * `maxObjects` – defines how many objects a node can hold before it splits
|
76 | * `maxLevels` – defines the deepest level subnode
|
77 | * `x` and `y` – coordinate offset
|
78 |
|
79 | I recommend using low values for `maxLevels` because each level will quadruple the possible amount of nodes. Using lower values for `maxLevels` increases performance but may return more candidates. Finetuning these values depends on your 2D space, the amount and size of the objects and your retrieving areas.
|
80 |
|
81 | Insert elements in the Quadtree:
|
82 | ```javascript
|
83 | import { Rectangle, Circle, Line } from '@timohausmann/quadtree-ts';
|
84 |
|
85 | const rectangle = new Rectangle({
|
86 | x: 100,
|
87 | y: 100,
|
88 | width: 100,
|
89 | height: 100
|
90 | });
|
91 | myTree.insert(rectangle);
|
92 |
|
93 | const line = new Line({
|
94 | x1: 25,
|
95 | y1: 25,
|
96 | x2: 75,
|
97 | y2: 25
|
98 | })
|
99 | myTree.insert(line);
|
100 |
|
101 | const circle = new Circle({
|
102 | x: 100,
|
103 | y: 100,
|
104 | r: 50
|
105 | })
|
106 | myTree.insert(circle);
|
107 | ```
|
108 |
|
109 | Retrieve elements from nodes that intersect with the given shape:
|
110 | ```javascript
|
111 | const area = new Rectangle({
|
112 | x: 150,
|
113 | y: 150,
|
114 | width: 100,
|
115 | height: 100
|
116 | })
|
117 | const elements = myTree.retrieve(area);
|
118 | ```
|
119 |
|
120 | Reset the Quadtree:
|
121 | ```javascript
|
122 | myTree.clear();
|
123 | ```
|
124 |
|
125 | ### Shapes
|
126 |
|
127 | The supported built-in primitive shapes are `Rectangle`, `Circle` and `Line`.
|
128 | All shapes can be inserted or used for retrieval.
|
129 | Each shape requires properties specific to their geometry.
|
130 |
|
131 | | Shape | Required Properties |
|
132 | |-----------|---------------------|
|
133 | | Rectangle | x, y, width, height |
|
134 | | Circle | x, y, r |
|
135 | | Line | x1, y1, x2, y2 |
|
136 |
|
137 | You can use these classes directly, extend them or integrate them in your own objects (see below).
|
138 |
|
139 | Note: if you are using the **UMD bundles**, the classes are available as `Quadtree.Rectangle`, `Quadtree.Circle` and `Quadtree.Line`.
|
140 |
|
141 | ```javascript
|
142 | // Class usage as-is
|
143 | const player = new Rectangle({
|
144 | x: 67,
|
145 | y: 67,
|
146 | width: 100,
|
147 | height: 100
|
148 | });
|
149 | myTree.insert(player);
|
150 |
|
151 | // Class extension
|
152 | class Explosion extends Circle {
|
153 |
|
154 | constructor(props) {
|
155 | super(props);
|
156 | }
|
157 |
|
158 | explode() {
|
159 | console.log('boom!');
|
160 | }
|
161 | }
|
162 | const explosion = new Explosion({ x: 100, y: 100, r: 100 });
|
163 | const affectedObjects = myTree.retrieve(explosion);
|
164 | ```
|
165 |
|
166 | ### Custom data
|
167 |
|
168 | All shapes support an optional data property that you can use however you like.
|
169 |
|
170 | ```javascript
|
171 | const rectangle = new Rectangle({
|
172 | x: 24,
|
173 | y: 24,
|
174 | width: 100,
|
175 | height: 100,
|
176 | data: 'custom data here'
|
177 | });
|
178 | const circle = new Circle({
|
179 | x: 128,
|
180 | y: 128,
|
181 | r: 50,
|
182 | data: {
|
183 | name: 'Stanley',
|
184 | health: 100
|
185 | }
|
186 | });
|
187 | ```
|
188 |
|
189 | ### Custom integration
|
190 |
|
191 | Under the hood all shape classes implement a `qtIndex` method that is crucial for determining in which quadrant a shape belongs. You can think of it as a shape identifier. An alternative to using the class constructors is to supply your own `qtIndex` function for objects you want the Quadtree to interact with.
|
192 |
|
193 | This is also helpful if your existing object properties don't match the required shape properties and you have to map them.
|
194 |
|
195 | ```javascript
|
196 | // Custom integration without mapping properties
|
197 | // In this case the custom object has all the
|
198 | // expected shape properties (x1, y1, x2, y2)
|
199 | // So we can simply reference the qtIndex method
|
200 | const redLaser = {
|
201 | color: 'red',
|
202 | brightness: 10,
|
203 | x1: 67,
|
204 | y1: 67,
|
205 | x2: 128,
|
206 | y2: 128,
|
207 | qtIndex: Line.prototype.qtIndex
|
208 | }
|
209 | myTree.insert(redLaser);
|
210 |
|
211 | // Custom integration with mapping properties
|
212 | // In this case the coordinates are arrays so they need to be mapped
|
213 | const greenLaser = {
|
214 | color: 'green',
|
215 | brightness: 10,
|
216 | startPoint: [50, 50],
|
217 | endPoint: [100, 50],
|
218 | qtIndex: function(node) {
|
219 | return Line.prototype.qtIndex.call({
|
220 | x1: this.startPoint[0],
|
221 | y1: this.startPoint[1],
|
222 | x2: this.endPoint[0],
|
223 | y2: this.endPoint[1],
|
224 | }, node);
|
225 | }
|
226 | };
|
227 | myTree.insert(greenLaser);
|
228 |
|
229 | // Custom integration with mapping in a class
|
230 | // If you have many instances of the same thing,
|
231 | // I recommend adding the qtIndex to your class/prototype
|
232 | class Bomb {
|
233 |
|
234 | constructor() {
|
235 | this.position = [50, 50];
|
236 | this.radius = 100;
|
237 | }
|
238 |
|
239 | qtIndex(node) {
|
240 | return Circle.prototype.qtIndex.call({
|
241 | x: this.position[0],
|
242 | y: this.position[1],
|
243 | r: this.radius,
|
244 | }, node);
|
245 | }
|
246 | }
|
247 | const bombOmb = new Bomb();
|
248 | myTree.insert(bombOmb);
|
249 |
|
250 | ```
|
251 |
|
252 | Check out the examples for more information.
|
253 |
|
254 |
|
255 | ## Typescript
|
256 |
|
257 | All types can be imported and are documented in the [API docs](https://timohausmann.github.io/quadtree-ts/documentation/).
|
258 |
|
259 | The Quadtree class accepts an optional type argument `<ObjectsType>` for all inserted/retrieved objects:
|
260 |
|
261 | ```typescript
|
262 | class GameEntity extends Rectangle {
|
263 | ...
|
264 | }
|
265 | const myTree = new Quadtree<GameEntity>({
|
266 | width: 800,
|
267 | height: 600
|
268 | });
|
269 | const rocket = new Rocket(...); // extends GameEntity
|
270 | myTree.insert(rocket);
|
271 | const results = myTree.retrieve(...); // GameEntity[]
|
272 | ```
|
273 |
|
274 | The shape classes accept an optional type argument `<CustomDataType>` for the custom data:
|
275 |
|
276 | ```typescript
|
277 | interface PlayerData {
|
278 | name: string
|
279 | health: number
|
280 | }
|
281 | const hero = new Rectangle<PlayerData>({
|
282 | x: 100,
|
283 | y: 100,
|
284 | width: 24,
|
285 | height: 48,
|
286 | data: {
|
287 | name: 'Shiffman',
|
288 | health: 100,
|
289 | }
|
290 | });
|
291 | ```
|
292 |
|
293 | ## Browser Support
|
294 |
|
295 | As of 2.0.0 the UMD bundles use ES6 features (e.g. classes) that are not supported by IE11 and below.
|
296 | For legacy browser support, please polyfill the code on your own or use [quadtree-js](https://github.com/timohausmann/quadtree-js).
|
297 |
|
298 |
|
299 | ## Development scripts
|
300 |
|
301 | * `npm run dev` to watch and build the source
|
302 | * `npm run build` execute rollup, docs, dts
|
303 | * `npm run rollup` to build the source only
|
304 | * `npm run test` to run the test suite
|
305 | * `npm run lint` to run eslint
|
306 | * `npm run docs` to create docs
|
307 | * `npm run dts` to create definition files
|
308 | * `npx jest -i './test/Quadtree/Quadtree.remove.test.ts' -t 'removes objects from subnodes'` run a single test
|
309 |
|
310 | Folder structure
|
311 |
|
312 | * `/dist` auto-generated by `npm run build`
|
313 | * `/docs` github pages
|
314 | * `/docs/documentation` auto-generated by `npm run docs`
|
315 | * `/docs/examples` the demo examples
|
316 | * `/src` source code
|
317 | * `/test` jest test suite
|
318 | * `/types` Auto-generated by `npm run dts`
|
319 |
|
320 |
|
321 |
|
322 | ## Migration from quadtree-js
|
323 |
|
324 | * Named exports only
|
325 | * Change import to `import { Quadtree } from ...`
|
326 | * Quadtree constructor
|
327 | * `maxObjects` and `maxLevels` are now named properties.
|
328 | * Also, `x` and `y` are now optional.
|
329 | * Change `new Quadtree({x: 0, y: 0, width: 100, height: 100}, 5, 2);` to `new Quadtree({width: 100, height: 100, maxObjects: 5, maxLevels: 2});`
|
330 | * Objects interacting with the Quadtree need to be a shape class or implement a `qtIndex` method (see above)
|
331 | * Bundle filename has changed: `quadtree.umd.full.js`
|
332 | * Typescript: Use `Rectangle` instead of `Rect` |
\ | No newline at end of file |