rbush.js 16 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574
  1. (function (global, factory) {
  2. typeof exports === 'object' && typeof module !== 'undefined' ? module.exports = factory() :
  3. typeof define === 'function' && define.amd ? define(factory) :
  4. (global = global || self, global.RBush = factory());
  5. }(this, function () { 'use strict';
  6. function quickselect(arr, k, left, right, compare) {
  7. quickselectStep(arr, k, left || 0, right || (arr.length - 1), compare || defaultCompare);
  8. }
  9. function quickselectStep(arr, k, left, right, compare) {
  10. while (right > left) {
  11. if (right - left > 600) {
  12. var n = right - left + 1;
  13. var m = k - left + 1;
  14. var z = Math.log(n);
  15. var s = 0.5 * Math.exp(2 * z / 3);
  16. var sd = 0.5 * Math.sqrt(z * s * (n - s) / n) * (m - n / 2 < 0 ? -1 : 1);
  17. var newLeft = Math.max(left, Math.floor(k - m * s / n + sd));
  18. var newRight = Math.min(right, Math.floor(k + (n - m) * s / n + sd));
  19. quickselectStep(arr, k, newLeft, newRight, compare);
  20. }
  21. var t = arr[k];
  22. var i = left;
  23. var j = right;
  24. swap(arr, left, k);
  25. if (compare(arr[right], t) > 0) { swap(arr, left, right); }
  26. while (i < j) {
  27. swap(arr, i, j);
  28. i++;
  29. j--;
  30. while (compare(arr[i], t) < 0) { i++; }
  31. while (compare(arr[j], t) > 0) { j--; }
  32. }
  33. if (compare(arr[left], t) === 0) { swap(arr, left, j); }
  34. else {
  35. j++;
  36. swap(arr, j, right);
  37. }
  38. if (j <= k) { left = j + 1; }
  39. if (k <= j) { right = j - 1; }
  40. }
  41. }
  42. function swap(arr, i, j) {
  43. var tmp = arr[i];
  44. arr[i] = arr[j];
  45. arr[j] = tmp;
  46. }
  47. function defaultCompare(a, b) {
  48. return a < b ? -1 : a > b ? 1 : 0;
  49. }
  50. var RBush = function RBush(maxEntries) {
  51. if ( maxEntries === void 0 ) maxEntries = 9;
  52. // max entries in a node is 9 by default; min node fill is 40% for best performance
  53. this._maxEntries = Math.max(4, maxEntries);
  54. this._minEntries = Math.max(2, Math.ceil(this._maxEntries * 0.4));
  55. this.clear();
  56. };
  57. RBush.prototype.all = function all () {
  58. return this._all(this.data, []);
  59. };
  60. RBush.prototype.search = function search (bbox) {
  61. var node = this.data;
  62. var result = [];
  63. if (!intersects(bbox, node)) { return result; }
  64. var toBBox = this.toBBox;
  65. var nodesToSearch = [];
  66. while (node) {
  67. for (var i = 0; i < node.children.length; i++) {
  68. var child = node.children[i];
  69. var childBBox = node.leaf ? toBBox(child) : child;
  70. if (intersects(bbox, childBBox)) {
  71. if (node.leaf) { result.push(child); }
  72. else if (contains(bbox, childBBox)) { this._all(child, result); }
  73. else { nodesToSearch.push(child); }
  74. }
  75. }
  76. node = nodesToSearch.pop();
  77. }
  78. return result;
  79. };
  80. RBush.prototype.collides = function collides (bbox) {
  81. var node = this.data;
  82. if (!intersects(bbox, node)) { return false; }
  83. var nodesToSearch = [];
  84. while (node) {
  85. for (var i = 0; i < node.children.length; i++) {
  86. var child = node.children[i];
  87. var childBBox = node.leaf ? this.toBBox(child) : child;
  88. if (intersects(bbox, childBBox)) {
  89. if (node.leaf || contains(bbox, childBBox)) { return true; }
  90. nodesToSearch.push(child);
  91. }
  92. }
  93. node = nodesToSearch.pop();
  94. }
  95. return false;
  96. };
  97. RBush.prototype.load = function load (data) {
  98. if (!(data && data.length)) { return this; }
  99. if (data.length < this._minEntries) {
  100. for (var i = 0; i < data.length; i++) {
  101. this.insert(data[i]);
  102. }
  103. return this;
  104. }
  105. // recursively build the tree with the given data from scratch using OMT algorithm
  106. var node = this._build(data.slice(), 0, data.length - 1, 0);
  107. if (!this.data.children.length) {
  108. // save as is if tree is empty
  109. this.data = node;
  110. } else if (this.data.height === node.height) {
  111. // split root if trees have the same height
  112. this._splitRoot(this.data, node);
  113. } else {
  114. if (this.data.height < node.height) {
  115. // swap trees if inserted one is bigger
  116. var tmpNode = this.data;
  117. this.data = node;
  118. node = tmpNode;
  119. }
  120. // insert the small tree into the large tree at appropriate level
  121. this._insert(node, this.data.height - node.height - 1, true);
  122. }
  123. return this;
  124. };
  125. RBush.prototype.insert = function insert (item) {
  126. if (item) { this._insert(item, this.data.height - 1); }
  127. return this;
  128. };
  129. RBush.prototype.clear = function clear () {
  130. this.data = createNode([]);
  131. return this;
  132. };
  133. RBush.prototype.remove = function remove (item, equalsFn) {
  134. if (!item) { return this; }
  135. var node = this.data;
  136. var bbox = this.toBBox(item);
  137. var path = [];
  138. var indexes = [];
  139. var i, parent, goingUp;
  140. // depth-first iterative tree traversal
  141. while (node || path.length) {
  142. if (!node) { // go up
  143. node = path.pop();
  144. parent = path[path.length - 1];
  145. i = indexes.pop();
  146. goingUp = true;
  147. }
  148. if (node.leaf) { // check current node
  149. var index = findItem(item, node.children, equalsFn);
  150. if (index !== -1) {
  151. // item found, remove the item and condense tree upwards
  152. node.children.splice(index, 1);
  153. path.push(node);
  154. this._condense(path);
  155. return this;
  156. }
  157. }
  158. if (!goingUp && !node.leaf && contains(node, bbox)) { // go down
  159. path.push(node);
  160. indexes.push(i);
  161. i = 0;
  162. parent = node;
  163. node = node.children[0];
  164. } else if (parent) { // go right
  165. i++;
  166. node = parent.children[i];
  167. goingUp = false;
  168. } else { node = null; } // nothing found
  169. }
  170. return this;
  171. };
  172. RBush.prototype.toBBox = function toBBox (item) { return item; };
  173. RBush.prototype.compareMinX = function compareMinX (a, b) { return a.minX - b.minX; };
  174. RBush.prototype.compareMinY = function compareMinY (a, b) { return a.minY - b.minY; };
  175. RBush.prototype.toJSON = function toJSON () { return this.data; };
  176. RBush.prototype.fromJSON = function fromJSON (data) {
  177. this.data = data;
  178. return this;
  179. };
  180. RBush.prototype._all = function _all (node, result) {
  181. var nodesToSearch = [];
  182. while (node) {
  183. if (node.leaf) { result.push.apply(result, node.children); }
  184. else { nodesToSearch.push.apply(nodesToSearch, node.children); }
  185. node = nodesToSearch.pop();
  186. }
  187. return result;
  188. };
  189. RBush.prototype._build = function _build (items, left, right, height) {
  190. var N = right - left + 1;
  191. var M = this._maxEntries;
  192. var node;
  193. if (N <= M) {
  194. // reached leaf level; return leaf
  195. node = createNode(items.slice(left, right + 1));
  196. calcBBox(node, this.toBBox);
  197. return node;
  198. }
  199. if (!height) {
  200. // target height of the bulk-loaded tree
  201. height = Math.ceil(Math.log(N) / Math.log(M));
  202. // target number of root entries to maximize storage utilization
  203. M = Math.ceil(N / Math.pow(M, height - 1));
  204. }
  205. node = createNode([]);
  206. node.leaf = false;
  207. node.height = height;
  208. // split the items into M mostly square tiles
  209. var N2 = Math.ceil(N / M);
  210. var N1 = N2 * Math.ceil(Math.sqrt(M));
  211. multiSelect(items, left, right, N1, this.compareMinX);
  212. for (var i = left; i <= right; i += N1) {
  213. var right2 = Math.min(i + N1 - 1, right);
  214. multiSelect(items, i, right2, N2, this.compareMinY);
  215. for (var j = i; j <= right2; j += N2) {
  216. var right3 = Math.min(j + N2 - 1, right2);
  217. // pack each entry recursively
  218. node.children.push(this._build(items, j, right3, height - 1));
  219. }
  220. }
  221. calcBBox(node, this.toBBox);
  222. return node;
  223. };
  224. RBush.prototype._chooseSubtree = function _chooseSubtree (bbox, node, level, path) {
  225. while (true) {
  226. path.push(node);
  227. if (node.leaf || path.length - 1 === level) { break; }
  228. var minArea = Infinity;
  229. var minEnlargement = Infinity;
  230. var targetNode = (void 0);
  231. for (var i = 0; i < node.children.length; i++) {
  232. var child = node.children[i];
  233. var area = bboxArea(child);
  234. var enlargement = enlargedArea(bbox, child) - area;
  235. // choose entry with the least area enlargement
  236. if (enlargement < minEnlargement) {
  237. minEnlargement = enlargement;
  238. minArea = area < minArea ? area : minArea;
  239. targetNode = child;
  240. } else if (enlargement === minEnlargement) {
  241. // otherwise choose one with the smallest area
  242. if (area < minArea) {
  243. minArea = area;
  244. targetNode = child;
  245. }
  246. }
  247. }
  248. node = targetNode || node.children[0];
  249. }
  250. return node;
  251. };
  252. RBush.prototype._insert = function _insert (item, level, isNode) {
  253. var bbox = isNode ? item : this.toBBox(item);
  254. var insertPath = [];
  255. // find the best node for accommodating the item, saving all nodes along the path too
  256. var node = this._chooseSubtree(bbox, this.data, level, insertPath);
  257. // put the item into the node
  258. node.children.push(item);
  259. extend(node, bbox);
  260. // split on node overflow; propagate upwards if necessary
  261. while (level >= 0) {
  262. if (insertPath[level].children.length > this._maxEntries) {
  263. this._split(insertPath, level);
  264. level--;
  265. } else { break; }
  266. }
  267. // adjust bboxes along the insertion path
  268. this._adjustParentBBoxes(bbox, insertPath, level);
  269. };
  270. // split overflowed node into two
  271. RBush.prototype._split = function _split (insertPath, level) {
  272. var node = insertPath[level];
  273. var M = node.children.length;
  274. var m = this._minEntries;
  275. this._chooseSplitAxis(node, m, M);
  276. var splitIndex = this._chooseSplitIndex(node, m, M);
  277. var newNode = createNode(node.children.splice(splitIndex, node.children.length - splitIndex));
  278. newNode.height = node.height;
  279. newNode.leaf = node.leaf;
  280. calcBBox(node, this.toBBox);
  281. calcBBox(newNode, this.toBBox);
  282. if (level) { insertPath[level - 1].children.push(newNode); }
  283. else { this._splitRoot(node, newNode); }
  284. };
  285. RBush.prototype._splitRoot = function _splitRoot (node, newNode) {
  286. // split root node
  287. this.data = createNode([node, newNode]);
  288. this.data.height = node.height + 1;
  289. this.data.leaf = false;
  290. calcBBox(this.data, this.toBBox);
  291. };
  292. RBush.prototype._chooseSplitIndex = function _chooseSplitIndex (node, m, M) {
  293. var index;
  294. var minOverlap = Infinity;
  295. var minArea = Infinity;
  296. for (var i = m; i <= M - m; i++) {
  297. var bbox1 = distBBox(node, 0, i, this.toBBox);
  298. var bbox2 = distBBox(node, i, M, this.toBBox);
  299. var overlap = intersectionArea(bbox1, bbox2);
  300. var area = bboxArea(bbox1) + bboxArea(bbox2);
  301. // choose distribution with minimum overlap
  302. if (overlap < minOverlap) {
  303. minOverlap = overlap;
  304. index = i;
  305. minArea = area < minArea ? area : minArea;
  306. } else if (overlap === minOverlap) {
  307. // otherwise choose distribution with minimum area
  308. if (area < minArea) {
  309. minArea = area;
  310. index = i;
  311. }
  312. }
  313. }
  314. return index || M - m;
  315. };
  316. // sorts node children by the best axis for split
  317. RBush.prototype._chooseSplitAxis = function _chooseSplitAxis (node, m, M) {
  318. var compareMinX = node.leaf ? this.compareMinX : compareNodeMinX;
  319. var compareMinY = node.leaf ? this.compareMinY : compareNodeMinY;
  320. var xMargin = this._allDistMargin(node, m, M, compareMinX);
  321. var yMargin = this._allDistMargin(node, m, M, compareMinY);
  322. // if total distributions margin value is minimal for x, sort by minX,
  323. // otherwise it's already sorted by minY
  324. if (xMargin < yMargin) { node.children.sort(compareMinX); }
  325. };
  326. // total margin of all possible split distributions where each node is at least m full
  327. RBush.prototype._allDistMargin = function _allDistMargin (node, m, M, compare) {
  328. node.children.sort(compare);
  329. var toBBox = this.toBBox;
  330. var leftBBox = distBBox(node, 0, m, toBBox);
  331. var rightBBox = distBBox(node, M - m, M, toBBox);
  332. var margin = bboxMargin(leftBBox) + bboxMargin(rightBBox);
  333. for (var i = m; i < M - m; i++) {
  334. var child = node.children[i];
  335. extend(leftBBox, node.leaf ? toBBox(child) : child);
  336. margin += bboxMargin(leftBBox);
  337. }
  338. for (var i$1 = M - m - 1; i$1 >= m; i$1--) {
  339. var child$1 = node.children[i$1];
  340. extend(rightBBox, node.leaf ? toBBox(child$1) : child$1);
  341. margin += bboxMargin(rightBBox);
  342. }
  343. return margin;
  344. };
  345. RBush.prototype._adjustParentBBoxes = function _adjustParentBBoxes (bbox, path, level) {
  346. // adjust bboxes along the given tree path
  347. for (var i = level; i >= 0; i--) {
  348. extend(path[i], bbox);
  349. }
  350. };
  351. RBush.prototype._condense = function _condense (path) {
  352. // go through the path, removing empty nodes and updating bboxes
  353. for (var i = path.length - 1, siblings = (void 0); i >= 0; i--) {
  354. if (path[i].children.length === 0) {
  355. if (i > 0) {
  356. siblings = path[i - 1].children;
  357. siblings.splice(siblings.indexOf(path[i]), 1);
  358. } else { this.clear(); }
  359. } else { calcBBox(path[i], this.toBBox); }
  360. }
  361. };
  362. function findItem(item, items, equalsFn) {
  363. if (!equalsFn) { return items.indexOf(item); }
  364. for (var i = 0; i < items.length; i++) {
  365. if (equalsFn(item, items[i])) { return i; }
  366. }
  367. return -1;
  368. }
  369. // calculate node's bbox from bboxes of its children
  370. function calcBBox(node, toBBox) {
  371. distBBox(node, 0, node.children.length, toBBox, node);
  372. }
  373. // min bounding rectangle of node children from k to p-1
  374. function distBBox(node, k, p, toBBox, destNode) {
  375. if (!destNode) { destNode = createNode(null); }
  376. destNode.minX = Infinity;
  377. destNode.minY = Infinity;
  378. destNode.maxX = -Infinity;
  379. destNode.maxY = -Infinity;
  380. for (var i = k; i < p; i++) {
  381. var child = node.children[i];
  382. extend(destNode, node.leaf ? toBBox(child) : child);
  383. }
  384. return destNode;
  385. }
  386. function extend(a, b) {
  387. a.minX = Math.min(a.minX, b.minX);
  388. a.minY = Math.min(a.minY, b.minY);
  389. a.maxX = Math.max(a.maxX, b.maxX);
  390. a.maxY = Math.max(a.maxY, b.maxY);
  391. return a;
  392. }
  393. function compareNodeMinX(a, b) { return a.minX - b.minX; }
  394. function compareNodeMinY(a, b) { return a.minY - b.minY; }
  395. function bboxArea(a) { return (a.maxX - a.minX) * (a.maxY - a.minY); }
  396. function bboxMargin(a) { return (a.maxX - a.minX) + (a.maxY - a.minY); }
  397. function enlargedArea(a, b) {
  398. return (Math.max(b.maxX, a.maxX) - Math.min(b.minX, a.minX)) *
  399. (Math.max(b.maxY, a.maxY) - Math.min(b.minY, a.minY));
  400. }
  401. function intersectionArea(a, b) {
  402. var minX = Math.max(a.minX, b.minX);
  403. var minY = Math.max(a.minY, b.minY);
  404. var maxX = Math.min(a.maxX, b.maxX);
  405. var maxY = Math.min(a.maxY, b.maxY);
  406. return Math.max(0, maxX - minX) *
  407. Math.max(0, maxY - minY);
  408. }
  409. function contains(a, b) {
  410. return a.minX <= b.minX &&
  411. a.minY <= b.minY &&
  412. b.maxX <= a.maxX &&
  413. b.maxY <= a.maxY;
  414. }
  415. function intersects(a, b) {
  416. return b.minX <= a.maxX &&
  417. b.minY <= a.maxY &&
  418. b.maxX >= a.minX &&
  419. b.maxY >= a.minY;
  420. }
  421. function createNode(children) {
  422. return {
  423. children: children,
  424. height: 1,
  425. leaf: true,
  426. minX: Infinity,
  427. minY: Infinity,
  428. maxX: -Infinity,
  429. maxY: -Infinity
  430. };
  431. }
  432. // sort an array so that items come in groups of n unsorted items, with groups sorted between each other;
  433. // combines selection algorithm with binary divide & conquer approach
  434. function multiSelect(arr, left, right, n, compare) {
  435. var stack = [left, right];
  436. while (stack.length) {
  437. right = stack.pop();
  438. left = stack.pop();
  439. if (right - left <= n) { continue; }
  440. var mid = left + Math.ceil((right - left) / n / 2) * n;
  441. quickselect(arr, mid, left, right, compare);
  442. stack.push(left, mid, mid, right);
  443. }
  444. }
  445. return RBush;
  446. }));