new object $rtree: $frob; var $root created_on = 843361817; var $root flags = ['variables, 'methods, 'code, 'core]; var $root inited = 1; var $root managed = [$rtree]; var $root manager = $rtree; var $rtree max_length = 4; public method ._delete() { arg self, key, point; var i, trees, boxes, ret, l, b, mod, box; if ((self.length()) == 1) { if (self == key) return [0, 1, 0]; else return [self, 0, 0]; } trees = self[2]; boxes = self[1]; l = []; b = []; mod = 0; for i in [1 .. boxes.length()] { if ($rect.inside(point, boxes[i])) { ret = ._delete(trees[i], key, point); if ((ret[1]) == 0) { mod = 1; continue; } l += [ret[1]]; mod = mod || (ret[2]); b += [(ret[3]) ? (ret[3]) : (boxes[i])]; } else { l += [trees[i]]; b += [boxes[i]]; } } if (!l) return [0, 1]; if (mod) { box = b[1]; for i in (b.subrange(2)) box = box.union(i); return [[b, l], 1, box]; } return [self, 0, 0]; }; public method ._insert() { arg tree, box, obj; var u, ret, xret, boxes, trees; trees = tree[2]; boxes = tree[1]; if (((trees[1]).length()) == 1) { // add leaf node to boxes and trees if ((trees.length()) < max_length) { return [[boxes + [box], trees + [obj]]]; } else { // return two nodes: return ._split(boxes + [box], trees + [obj]); } } else { u = ._insert_where(boxes, box); ret = ._insert(trees[u], box, obj); if ((ret.length()) == 1) return [[boxes.replace(u, $rect.union(box, boxes[u])), trees.replace(u, ret[1])]]; else if ((trees.length()) < max_length) return [[(boxes.delete(u)) + (ret.slice(3)), (trees.delete(u)) + [[(ret[1])[1], (ret[1])[2]], [(ret[2])[1], (ret[2])[2]]]]]; else return ._split((boxes.delete(u)) + (ret.slice(3)), (trees.delete(u)) + [[(ret[1])[1], (ret[1])[2]], [(ret[2])[1], (ret[2])[2]]]); } }; public method ._insert_where() { arg rlist, new; var i, u, min, t; u = 0; min = 1e+27; for i in [1 .. rlist.length()] { if ((t = $rect.rect_size($rect.union(rlist[i], new))) < min) { min = t; u = i; } } return u; }; public method ._split() { arg rlist, nlist; var i, j, m1, m2, r1, r2, l1, l2, n1, n2, len, min, seed1, seed2, min1, box; // First find the two rects that unioned create the greatest size... len = rlist.length(); min = 1e+27; for i in [1 .. len - 1] { for j in [i + 1 .. len] { if (min > (min1 = $rect.rect_size($rect.union(rlist[i], rlist[j])))) { min = min1; seed1 = i; seed2 = j; } } } l1 = [(r1 = rlist[seed1])]; l2 = [(r2 = rlist[seed2])]; n1 = [nlist[seed1]]; n2 = [nlist[seed2]]; rlist = rlist.delete(seed2); rlist = rlist.delete(seed1); nlist = nlist.delete(seed2); nlist = nlist.delete(seed1); // Now add to the list that shows lower increase in size // l1,l2 are rectangle lists, n1,n2 are node lists, and r1, r2 are // current bounding rectangles for i in [1 .. rlist.length()] { box = rlist[i]; m1 = $rect.union(r1, box); m2 = $rect.union(r2, box); if (($rect.rect_size(m1)) < ($rect.rect_size(m2))) { r1 = m1; l1 += [box]; n1 += [nlist[i]]; } else { r2 = m2; l2 += [box]; n2 += [nlist[i]]; } } return [[l1, n1, r1], [l2, n2, r2]]; }; public method .delete() { arg self, point, box; var ret; ret = ._delete(self, point, box); return (ret[1]) ? (<this(), (ret[1])>) : (.empty()); }; public method .insert() { arg self, box, obj; var ret; if (!(self[1])) return (<$rtree, [[box], [obj]]>); ret = ._insert(self, box, obj); if ((ret.length()) == 1) return (<$rtree, (ret[1])>); else return (<$rtree, [ret.slice(3), [[(ret[1])[1], (ret[1])[2]], [(ret[2])[1], (ret[2])[2]]]]>); }; public method .new() { return (<$rtree, [[], []]>); }; public method .search() { arg self, point; var boxes, trees, i, l; if ((self.length()) == 1) return self; boxes = self[1]; trees = self[2]; l = []; for i in [1 .. boxes.length()] { if ($rect.inside(point, boxes[i])) l += .search(trees[i], point); } return l; };