1 | /**
|
2 | * quadtree-js
|
3 | * @version 1.2.6
|
4 | * @license MIT
|
5 | * @author Timo Hausmann
|
6 | */
|
7 |
|
8 | /* https://github.com/timohausmann/quadtree-js.git v1.2.6 */
|
9 |
|
10 | /*
|
11 | Copyright © 2012-2023 Timo Hausmann
|
12 |
|
13 | Permission is hereby granted, free of charge, to any person obtaining
|
14 | a copy of this software and associated documentation files (the
|
15 | "Software"), to deal in the Software without restriction, including
|
16 | without limitation the rights to use, copy, modify, merge, publish,
|
17 | distribute, sublicense, and/or sell copies of the Software, and to
|
18 | permit persons to whom the Software is furnished to do so, subject to
|
19 | the following conditions:
|
20 |
|
21 | The above copyright notice and this permission notice shall be
|
22 | included in all copies or substantial portions of the Software.
|
23 |
|
24 | THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
|
25 | EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
|
26 | MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
|
27 | NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
|
28 | LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
|
29 | OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
|
30 | WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
|
31 | */
|
32 |
|
33 | ;(function() {
|
34 |
|
35 | /**
|
36 | * The Quadtree uses rectangle objects for all areas ("Rect").
|
37 | * All rectangles require the properties x, y, width, height
|
38 | * @typedef {Object} Rect
|
39 | * @property {number} x X-Position
|
40 | * @property {number} y Y-Position
|
41 | * @property {number} width Width
|
42 | * @property {number} height Height
|
43 | */
|
44 |
|
45 | /**
|
46 | * Quadtree Constructor
|
47 | * @class Quadtree
|
48 | * @param {Rect} bounds bounds of the node ({ x, y, width, height })
|
49 | * @param {number} [max_objects=10] (optional) max objects a node can hold before splitting into 4 subnodes (default: 10)
|
50 | * @param {number} [max_levels=4] (optional) total max levels inside root Quadtree (default: 4)
|
51 | * @param {number} [level=0] (optional) depth level, required for subnodes (default: 0)
|
52 | */
|
53 | function Quadtree(bounds, max_objects, max_levels, level) {
|
54 |
|
55 | this.max_objects = max_objects || 10;
|
56 | this.max_levels = max_levels || 4;
|
57 |
|
58 | this.level = level || 0;
|
59 | this.bounds = bounds;
|
60 |
|
61 | this.objects = [];
|
62 | this.nodes = [];
|
63 | };
|
64 |
|
65 |
|
66 | /**
|
67 | * Split the node into 4 subnodes
|
68 | * @memberof Quadtree
|
69 | */
|
70 | Quadtree.prototype.split = function() {
|
71 |
|
72 | var nextLevel = this.level + 1,
|
73 | subWidth = this.bounds.width/2,
|
74 | subHeight = this.bounds.height/2,
|
75 | x = this.bounds.x,
|
76 | y = this.bounds.y;
|
77 |
|
78 | //top right node
|
79 | this.nodes[0] = new Quadtree({
|
80 | x : x + subWidth,
|
81 | y : y,
|
82 | width : subWidth,
|
83 | height : subHeight
|
84 | }, this.max_objects, this.max_levels, nextLevel);
|
85 |
|
86 | //top left node
|
87 | this.nodes[1] = new Quadtree({
|
88 | x : x,
|
89 | y : y,
|
90 | width : subWidth,
|
91 | height : subHeight
|
92 | }, this.max_objects, this.max_levels, nextLevel);
|
93 |
|
94 | //bottom left node
|
95 | this.nodes[2] = new Quadtree({
|
96 | x : x,
|
97 | y : y + subHeight,
|
98 | width : subWidth,
|
99 | height : subHeight
|
100 | }, this.max_objects, this.max_levels, nextLevel);
|
101 |
|
102 | //bottom right node
|
103 | this.nodes[3] = new Quadtree({
|
104 | x : x + subWidth,
|
105 | y : y + subHeight,
|
106 | width : subWidth,
|
107 | height : subHeight
|
108 | }, this.max_objects, this.max_levels, nextLevel);
|
109 | };
|
110 |
|
111 |
|
112 | /**
|
113 | * Determine which node the object belongs to
|
114 | * @param {Rect} pRect bounds of the area to be checked ({ x, y, width, height })
|
115 | * @return {number[]} an array of indexes of the intersecting subnodes (0-3 = top-right, top-left, bottom-left, bottom-right / ne, nw, sw, se)
|
116 | * @memberof Quadtree
|
117 | */
|
118 | Quadtree.prototype.getIndex = function(pRect) {
|
119 |
|
120 | var indexes = [],
|
121 | verticalMidpoint = this.bounds.x + (this.bounds.width/2),
|
122 | horizontalMidpoint = this.bounds.y + (this.bounds.height/2);
|
123 |
|
124 | var startIsNorth = pRect.y < horizontalMidpoint,
|
125 | startIsWest = pRect.x < verticalMidpoint,
|
126 | endIsEast = pRect.x + pRect.width > verticalMidpoint,
|
127 | endIsSouth = pRect.y + pRect.height > horizontalMidpoint;
|
128 |
|
129 | //top-right quad
|
130 | if(startIsNorth && endIsEast) {
|
131 | indexes.push(0);
|
132 | }
|
133 |
|
134 | //top-left quad
|
135 | if(startIsWest && startIsNorth) {
|
136 | indexes.push(1);
|
137 | }
|
138 |
|
139 | //bottom-left quad
|
140 | if(startIsWest && endIsSouth) {
|
141 | indexes.push(2);
|
142 | }
|
143 |
|
144 | //bottom-right quad
|
145 | if(endIsEast && endIsSouth) {
|
146 | indexes.push(3);
|
147 | }
|
148 |
|
149 | return indexes;
|
150 | };
|
151 |
|
152 |
|
153 | /**
|
154 | * Insert the object into the node. If the node
|
155 | * exceeds the capacity, it will split and add all
|
156 | * objects to their corresponding subnodes.
|
157 | * @param {Rect} pRect bounds of the object to be added ({ x, y, width, height })
|
158 | * @memberof Quadtree
|
159 | */
|
160 | Quadtree.prototype.insert = function(pRect) {
|
161 |
|
162 | var i = 0,
|
163 | indexes;
|
164 |
|
165 | //if we have subnodes, call insert on matching subnodes
|
166 | if(this.nodes.length) {
|
167 | indexes = this.getIndex(pRect);
|
168 |
|
169 | for(i=0; i<indexes.length; i++) {
|
170 | this.nodes[indexes[i]].insert(pRect);
|
171 | }
|
172 | return;
|
173 | }
|
174 |
|
175 | //otherwise, store object here
|
176 | this.objects.push(pRect);
|
177 |
|
178 | //max_objects reached
|
179 | if(this.objects.length > this.max_objects && this.level < this.max_levels) {
|
180 |
|
181 | //split if we don't already have subnodes
|
182 | if(!this.nodes.length) {
|
183 | this.split();
|
184 | }
|
185 |
|
186 | //add all objects to their corresponding subnode
|
187 | for(i=0; i<this.objects.length; i++) {
|
188 | indexes = this.getIndex(this.objects[i]);
|
189 | for(var k=0; k<indexes.length; k++) {
|
190 | this.nodes[indexes[k]].insert(this.objects[i]);
|
191 | }
|
192 | }
|
193 |
|
194 | //clean up this node
|
195 | this.objects = [];
|
196 | }
|
197 | };
|
198 |
|
199 |
|
200 | /**
|
201 | * Return all objects that could collide with the given object
|
202 | * @param {Rect} pRect bounds of the object to be checked ({ x, y, width, height })
|
203 | * @return {Rect[]} array with all detected objects
|
204 | * @memberof Quadtree
|
205 | */
|
206 | Quadtree.prototype.retrieve = function(pRect) {
|
207 |
|
208 | var indexes = this.getIndex(pRect),
|
209 | returnObjects = this.objects;
|
210 |
|
211 | //if we have subnodes, retrieve their objects
|
212 | if(this.nodes.length) {
|
213 | for(var i=0; i<indexes.length; i++) {
|
214 | returnObjects = returnObjects.concat(this.nodes[indexes[i]].retrieve(pRect));
|
215 | }
|
216 | }
|
217 |
|
218 | //remove duplicates
|
219 | if(this.level === 0) {
|
220 | return Array.from(new Set(returnObjects));
|
221 | }
|
222 |
|
223 | return returnObjects;
|
224 | };
|
225 |
|
226 |
|
227 | /**
|
228 | * Clear the quadtree
|
229 | * @memberof Quadtree
|
230 | */
|
231 | Quadtree.prototype.clear = function() {
|
232 |
|
233 | this.objects = [];
|
234 |
|
235 | for(var i=0; i < this.nodes.length; i++) {
|
236 | if(this.nodes.length) {
|
237 | this.nodes[i].clear();
|
238 | }
|
239 | }
|
240 |
|
241 | this.nodes = [];
|
242 | };
|
243 |
|
244 | //export for commonJS or browser
|
245 | if(typeof module !== 'undefined' && typeof module.exports !== 'undefined') {
|
246 | module.exports = Quadtree;
|
247 | } else {
|
248 | window.Quadtree = Quadtree;
|
249 | }
|
250 |
|
251 | })(); |
\ | No newline at end of file |