1/* 2(c) 2013, Vladimir Agafonkin 3RBush, a JavaScript library for high-performance 2D spatial indexing of points and rectangles. 4https://github.com/mourner/rbush 5*/ 6 7(function () { 'use strict'; 8 9function rbush(maxEntries, format) { 10 11 // jshint newcap: false, validthis: true 12 if (!(this instanceof rbush)) { return new rbush(maxEntries, format); } 13 14 this._maxEntries = Math.max(4, maxEntries || 9); 15 this._minEntries = Math.max(2, Math.ceil(this._maxEntries * 0.4)); 16 17 this._initFormat(format); 18 19 this.clear(); 20} 21 22rbush.prototype = { 23 24 search: function (bbox) { 25 26 var node = this.data, 27 result = []; 28 29 if (!this._intersects(bbox, node.bbox)) { return result; } 30 31 var nodesToSearch = [], 32 i, len, child, childBBox; 33 34 while (node) { 35 for (i = 0, len = node.children.length; i < len; i++) { 36 child = node.children[i]; 37 childBBox = node.leaf ? this._toBBox(child) : child.bbox; 38 39 if (this._intersects(bbox, childBBox)) { 40 (node.leaf ? result : nodesToSearch).push(child); 41 } 42 } 43 44 node = nodesToSearch.pop(); 45 } 46 47 return result; 48 }, 49 50 load: function (data) { 51 if (!(data && data.length)) { return this; } 52 53 if (data.length < this._minEntries) { 54 for (var i = 0, len = data.length; i < len; i++) { 55 this.insert(data[i]); 56 } 57 return this; 58 } 59 60 // recursively build the tree with the given data from stratch using OMT algorithm 61 var node = this._build(data.slice(), 0); 62 63 if (!this.data.children.length) { 64 // save as is if tree is empty 65 this.data = node; 66 67 } else if (this.data.height === node.height) { 68 // split root if trees have the same height 69 this._splitRoot(this.data, node); 70 71 } else { 72 if (this.data.height < node.height) { 73 // swap trees if inserted one is bigger 74 var tmpNode = this.data; 75 this.data = node; 76 node = tmpNode; 77 } 78 79 // insert the small tree into the large tree at appropriate level 80 this._insert(node, this.data.height - node.height - 1, true); 81 } 82 83 return this; 84 }, 85 86 insert: function (item) { 87 if (item) { 88 this._insert(item, this.data.height - 1); 89 } 90 return this; 91 }, 92 93 clear: function () { 94 this.data = { 95 children: [], 96 leaf: true, 97 bbox: this._empty(), 98 height: 1 99 }; 100 return this; 101 }, 102 103 remove: function (item) { 104 if (!item) { return this; } 105 106 var node = this.data, 107 bbox = this._toBBox(item), 108 path = [], 109 indexes = [], 110 i, parent, index, goingUp; 111 112 // depth-first iterative tree traversal 113 while (node || path.length) { 114 115 if (!node) { // go up 116 node = path.pop(); 117 parent = path[path.length - 1]; 118 i = indexes.pop(); 119 goingUp = true; 120 } 121 122 if (node.leaf) { // check current node 123 index = node.children.indexOf(item); 124 125 if (index !== -1) { 126 // item found, remove the item and condense tree upwards 127 node.children.splice(index, 1); 128 path.push(node); 129 this._condense(path); 130 return this; 131 } 132 } 133 134 if (!goingUp && !node.leaf && this._intersects(bbox, node.bbox)) { // go down 135 path.push(node); 136 indexes.push(i); 137 i = 0; 138 parent = node; 139 node = node.children[0]; 140 141 } else if (parent) { // go right 142 i++; 143 node = parent.children[i]; 144 goingUp = false; 145 146 } else { // nothing found 147 node = null; 148 } 149 } 150 151 return this; 152 }, 153 154 toJSON: function () { return this.data; }, 155 156 fromJSON: function (data) { 157 this.data = data; 158 return this; 159 }, 160 161 _build: function (items, level, height) { 162 163 var N = items.length, 164 M = this._maxEntries, 165 node; 166 167 if (N <= M) { 168 node = { 169 children: items, 170 leaf: true, 171 height: 1 172 }; 173 this._calcBBox(node); 174 return node; 175 } 176 177 if (!level) { 178 // target height of the bulk-loaded tree
179 height = Math.ceil(Math.log(N) / Math.log(M)); 180 181 // target number of root entries to maximize storage utilization 182 M = Math.ceil(N / Math.pow(M, height - 1)); 183 184 items.sort(this._compareMinX); 185 } 186 187 // TODO eliminate recursion? 188 189 node = { 190 children: [], 191 height: height 192 }; 193 194 var N1 = Math.ceil(N / M) * Math.ceil(Math.sqrt(M)), 195 N2 = Math.ceil(N / M), 196 compare = level % 2 === 1 ? this._compareMinX : this._compareMinY, 197 i, j, slice, sliceLen, childNode; 198 199 // split the items into M mostly square tiles 200 for (i = 0; i < N; i += N1) { 201 slice = items.slice(i, i + N1).sort(compare); 202 203 for (j = 0, sliceLen = slice.length; j < sliceLen; j += N2) { 204 // pack each entry recursively 205 childNode = this._build(slice.slice(j, j + N2), level + 1, height - 1); 206 node.children.push(childNode); 207 } 208 } 209 210 this._calcBBox(node); 211 212 return node; 213 }, 214 215 _chooseSubtree: function (bbox, node, level, path) { 216 217 var i, len, child, targetNode, area, enlargement, minArea, minEnlargement; 218 219 while (true) { 220 path.push(node); 221 222 if (node.leaf || path.length - 1 === level) { break; } 223 224 minArea = minEnlargement = Infinity; 225 226 for (i = 0, len = node.children.length; i < len; i++) { 227 child = node.children[i]; 228 area = this._area(child.bbox); 229 enlargement = this._enlargedArea(bbox, child.bbox) - area; 230 231 // choose entry with the least area enlargement 232 if (enlargement < minEnlargement) { 233 minEnlargement = enlargement; 234 minArea = area < minArea ? area : minArea; 235 targetNode = child; 236 237 } else if (enlargement === minEnlargement) { 238 // otherwise choose one with the smallest area 239 if (area < minArea) { 240 minArea = area; 241 targetNode = child; 242 } 243 } 244 } 245 246 node = targetNode; 247 } 248 249 return node; 250 }, 251 252 _insert: function (item, level, isNode, root) { 253 254 var bbox = isNode ? item.bbox : this._toBBox(item), 255 insertPath = []; 256 257 // find the best node for accommodating the item, saving all nodes along the path too 258 var node = this._chooseSubtree(bbox, root || this.data, level, insertPath), 259 splitOccured; 260 261 // put the item into the node 262 node.children.push(item); 263 this._extend(node.bbox, bbox); 264 265 // split on node overflow; propagate upwards if necessary 266 do { 267 splitOccured = false; 268 if (insertPath[level].children.length > this._maxEntries) { 269 this._split(insertPath, level); 270 splitOccured = true; 271 level--; 272 } 273 } while (level >= 0 && splitOccured); 274 275 // adjust bboxes along the insertion path 276 this._adjustParentBBoxes(bbox, insertPath, level); 277 }, 278 279 // split overflowed node into two 280 _split: function (insertPath, level) { 281 282 var node = insertPath[level], 283 M = node.children.length, 284 m = this._minEntries; 285 286 this._chooseSplitAxis(node, m, M); 287 288 var newNode = { 289 children: node.children.splice(this._chooseSplitIndex(node, m, M)), 290 height: node.height 291 }; 292 293 if (node.leaf) { 294 newNode.leaf = true; 295 } 296 297 this._calcBBox(node); 298 this._calcBBox(newNode); 299 300 if (level) { 301 insertPath[level - 1].children.push(newNode); 302 } else { 303 this._splitRoot(node, newNode); 304 } 305 }, 306 307 _splitRoot: function (node, newNode) { 308 // split root node 309 this.data = {};
310 this.data.children = [node, newNode]; 311 this.data.height = node.height + 1; 312 this._calcBBox(this.data); 313 }, 314 315 _chooseSplitIndex: function (node, m, M) { 316 317 var i, bbox1, bbox2, overlap, area, minOverlap, minArea, index; 318 319 minOverlap = minArea = Infinity; 320 321 for (i = m; i <= M - m; i++) { 322 bbox1 = this._distBBox(node, 0, i); 323 bbox2 = this._distBBox(node, i, M); 324 325 overlap = this._intersectionArea(bbox1, bbox2); 326 area = this._area(bbox1) + this._area(bbox2); 327 328 // choose distribution with minimum overlap 329 if (overlap < minOverlap) { 330 minOverlap = overlap; 331 index = i; 332 333 minArea = area < minArea ? area : minArea; 334 335 } else if (overlap === minOverlap) { 336 // otherwise choose distribution with minimum area 337 if (area < minArea) { 338 minArea = area; 339 index = i; 340 } 341 } 342 } 343 344 return index; 345 }, 346 347 // sorts node children by the best axis for split 348 _chooseSplitAxis: function (node, m, M) { 349 350 var compareMinX = node.leaf ? this._compareMinX : this._compareNodeMinX, 351 compareMinY = node.leaf ? this._compareMinY : this._compareNodeMinY, 352 xMargin = this._allDistMargin(node, m, M, compareMinX), 353 yMargin = this._allDistMargin(node, m, M, compareMinY); 354 355 // if total distributions margin value is minimal for x, sort by minX, 356 // otherwise it's already sorted by minY 357 358 if (xMargin < yMargin) { 359 node.children.sort(compareMinX); 360 } 361 }, 362 363 // total margin of all possible split distributions where each node is at least m full 364 _allDistMargin: function (node, m, M, compare) { 365 366 node.children.sort(compare); 367 368 var leftBBox = this._distBBox(node, 0, m), 369 rightBBox = this._distBBox(node, M - m, M), 370 margin = this._margin(leftBBox) + this._margin(rightBBox), 371 i, child; 372 373 for (i = m; i < M - m; i++) { 374 child = node.children[i]; 375 this._extend(leftBBox, node.leaf ? this._toBBox(child) : child.bbox); 376 margin += this._margin(leftBBox); 377 } 378 379 for (i = M - m - 1; i >= 0; i--) { 380 child = node.children[i]; 381 this._extend(rightBBox, node.leaf ? this._toBBox(child) : child.bbox); 382 margin += this._margin(rightBBox); 383 } 384 385 return margin; 386 }, 387 388 // min bounding rectangle of node children from k to p-1 389 _distBBox: function (node, k, p) { 390 var bbox = this._empty(); 391 392 for (var i = k, child; i < p; i++) { 393 child = node.children[i]; 394 this._extend(bbox, node.leaf ? this._toBBox(child) : child.bbox); 395 } 396 397 return bbox; 398 }, 399 400 // calculate node's bbox from bboxes of its children 401 _calcBBox: function (node) { 402 node.bbox = this._empty(); 403 404 for (var i = 0, len = node.children.length, child; i < len; i++) { 405 child = node.children[i]; 406 this._extend(node.bbox, node.leaf ? this._toBBox(child) : child.bbox); 407 } 408 }, 409 410 _adjustParentBBoxes: function (bbox, path, level) { 411 // adjust bboxes along the given tree path 412 for (var i = level; i >= 0; i--) { 413 this._extend(path[i].bbox, bbox); 414 } 415 }, 416 417 _condense: function (path) { 418 // go through the path, removing empty nodes and updating bboxes 419 for (var i = path.length - 1, parent; i >= 0; i--) { 420 if (i > 0 && path[i].children.length === 0) { 421 parent = path[i - 1].children; 422 parent.splice(parent.indexOf(path[i]), 1); 423 } else { 424 this._calcBBox(path[i]); 425 } 426 } 427 }, 428 429 _intersects: function (a, b) { 430 return b[0] <= a[2] && 431 b[1] <= a[3] && 432 b[2] >= a[0] && 433 b[3] >= a[1]; 434 }, 435 436 _extend: function (a, b) { 437 a[0] = Math.min(a[0], b[0]); 438 a[1] = Math.min(a[1], b[1]); 439 a[2] = Math.max(a[2], b[2]); 440 a[3] = Math.max(a[3], b[3]);
441 return a; 442 }, 443 444 _area: function (a) { return (a[2] - a[0]) * (a[3] - a[1]); }, 445 _margin: function (a) { return (a[2] - a[0]) + (a[3] - a[1]); }, 446 447 _enlargedArea: function (a, b) { 448 return (Math.max(b[2], a[2]) - Math.min(b[0], a[0])) * 449 (Math.max(b[3], a[3]) - Math.min(b[1], a[1])); 450 }, 451 452 _intersectionArea: function (a, b) { 453 var minX = Math.max(a[0], b[0]), 454 minY = Math.max(a[1], b[1]), 455 maxX = Math.min(a[2], b[2]), 456 maxY = Math.min(a[3], b[3]); 457 458 return Math.max(0, maxX - minX) * 459 Math.max(0, maxY - minY); 460 }, 461 462 _empty: function () { return [Infinity, Infinity, -Infinity, -Infinity]; }, 463 464 _compareNodeMinX: function (a, b) { return a.bbox[0] - b.bbox[0]; }, 465 _compareNodeMinY: function (a, b) { return a.bbox[1] - b.bbox[1]; }, 466 467 _initFormat: function (format) { 468 // data format (minX, minY, maxX, maxY accessors) 469 format = format || ['[0]', '[1]', '[2]', '[3]']; 470 471 // uses eval-type function compilation instead of just accepting a toBBox function 472 // because the algorithms are very sensitive to sorting functions performance, 473 // so they should be dead simple and without inner calls 474 475 // jshint evil: true 476 477 var compareArr = ['return a', ' - b', ';']; 478 479 this._compareMinX = new Function('a', 'b', compareArr.join(format[0])); 480 this._compareMinY = new Function('a', 'b', compareArr.join(format[1])); 481 482 this._toBBox = new Function('a', 'return [a' + format.join(', a') + '];'); 483 } 484}; 485 486if (typeof define === 'function' && define.amd) { 487 define(function() { 488 return rbush; 489 }); 490} else if (typeof module !== 'undefined') { 491 module.exports = rbush; 492} else { 493 window.rbush = rbush; 494} 495 496})();
Line numbers count LF bytes from the start of the resource, as the search results do. Vendor segments are library code the classifier recognised; they are stored but not indexed. Bytes are shown as Latin1 characters, one per byte.