R-Tree
| Space | Time | |||
|---|---|---|---|---|
| Access | Lookup | Insertion | Deletion | |
O(n) | O(log n) | O(log n) | O(n log n) | O(log n) |
Definition
- Short
- Detailed
R-Tree is a spatial index structure used in computer science and geographic information systems to efficiently organize and search spatial objects, facilitating operations like finding nearby locations or detecting overlapping regions.
Simplified
R-Tree is like a smart index for digital maps, organizing locations into boxes for efficient searches. It helps quickly find specific places, like parks or restaurants, by guiding you to relevant areas rather than scanning the entire map. In essence, it's an efficient guide for locating things on a digital map
R-Tree is a spatial indexing data structure used for organizing and efficiently querying multidimensional spatial data. It arranges data in a hierarchical manner, with internal nodes representing bounding rectangles of child nodes and leaves representing actual data objects within rectangles. R-Trees are designed to minimize overlap, optimize space, and enable fast retrieval of spatial information, making them useful in applications like geographic information systems and databases dealing with multidimensional data.
Properties
- Structure Components: Consists of a single root, internal nodes, and leaf nodes
- Root Property: The root contains a pointer to the largest region in the spatial domain
- Parent-Child Relationship: Parent nodes contain pointers to their child nodes, where the region of child nodes completely overlaps the regions of parent nodes
- Leaf Node Information: Leaf nodes contain data about the Minimum Bounding Region (MBR) for the current objects
- MBR Definition: Minimum Bounding Region, refers to the minimal bounding box parameter surrounding the region/object under consideration
Use Cases:
- Indexing multi-dimensional information
- Handling geospatial coordinates
- Implementation of virtual maps
- Handling game data
R*-Tree vs R-tree
| Feature | R*-Tree | R-Tree |
|---|---|---|
| Splitting Strategy | Optimized split strategy (e.g., R*-split) | Basic split strategy (e.g., linear split) |
| Overlapping Nodes | Minimizes overlapping nodes for better performance | May have more overlapping nodes |
| Node Overlap Reduction | Uses delayed reinsertion to reduce overlap | May not have sophisticated overlap reduction |
| Node Overflow Handling | Utilizes quadratic split for overflow nodes | Utilizes basic split (e.g., linear split) for overflow nodes |
| Node Utilization | More efficient space utilization | May have less efficient space utilization |
| Query Performance | Generally better query performance | May have slightly lower query performance |
| Insertion and Deletion | Improved insertion and deletion algorithms | May have simpler but less efficient algorithms |
| Complexity of Implementation | More complex due to advanced strategies | Simpler and easier to implement |
| General Efficiency | Designed for better overall efficiency | Basic design with acceptable efficiency |
Quad-Tree vs R-Tree
| Feature | Quad-Tree | R-Tree |
|---|---|---|
| Tiling Level Optimization | Required | Optional |
| Implementation on B-Tree | Can be implemented on top of an existing B-tree | Follows a different structure from a B-tree |
| Spatial Index Creation Speed | Faster compared to R-Trees | |
| Performance in Nearest Neighbour Queries | Faster than Quad-trees | |
| Performance in Window Queries | Faster than R-Trees |
Practice
- Practice
- Solution
| Aspect | Pseudo Code |
|---|---|
| Calculate Bounding Box | |
| Calculate Expanded Bbox | |
| Point In Bbox | |
| Distance | |
| Bbox Fully Contained | |
| Bbox Intersects Query | |
| Split | |
| Calculate Area Increase | |
| Insertion | |
| Search Recursive | |
| Nearest Neighbors Recursive | |
| Delete Recursive | |
| Update | |
| Range Query | |
| Window Query Recursive | |
| kNN Query | |
| Traverse | |
package main
import (
"math"
)
type RTreeNode struct {
IsLeaf bool
Children []point
BoundingBox *BoundingBox
}
type BoundingBox struct {
MinX, MinY, MaxX, MaxY float64
}
type point struct {
X, Y float64
}
type RTree struct {
Root *RTreeNode
MaxChildren int
}
func NewRTreeNode(isLeaf bool) *RTreeNode {
return &RTreeNode{
IsLeaf: isLeaf,
Children: make([]point, 0),
BoundingBox: nil,
}
}
func NewBoundingBox(minX, minY, maxX, maxY float64) *BoundingBox {
return &BoundingBox{
MinX: minX,
MinY: minY,
MaxX: maxX,
MaxY: maxY,
}
}
func NewRTree(maxChildren int) *RTree {
root := NewRTreeNode(true)
return &RTree{
Root: root,
MaxChildren: maxChildren,
}
}
func (tree *RTree) Insert(point point) {
tree.insertRecursive(tree.Root, point)
}
func (tree *RTree) insertRecursive(node *RTreeNode, point point) {
if node.IsLeaf {
node.Children = append(node.Children, point)
if len(node.Children) > tree.MaxChildren {
tree.split(node)
}
} else {
minIncrease := math.Inf(1)
var bestChild *RTreeNode
for _, child := range node.Children {
childBBox := calculateBoundingBox(child)
expandedBBox := calculateExpandedBoundingBox(childBBox, point)
increase := calculateAreaIncrease(childBBox, expandedBBox)
if increase < minIncrease {
minIncrease = increase
bestChild = &child
}
}
tree.insertRecursive(bestChild, point)
}
}
func calculateAreaIncrease(oldBBox, newBBox *BoundingBox) float64 {
oldArea := (oldBBox.MaxX - oldBBox.MinX) * (oldBBox.MaxY - oldBBox.MinY)
newArea := (newBBox.MaxX - newBBox.MinX) * (newBBox.MaxY - newBBox.MinY)
return newArea - oldArea
}
func calculateExpandedBoundingBox(oldBBox *BoundingBox, point point) *BoundingBox {
newMinX := math.Min(oldBBox.MinX, point.X)
newMinY := math.Min(oldBBox.MinY, point.Y)
newMaxX := math.Max(oldBBox.MaxX, point.X)
newMaxY := math.Max(oldBBox.MaxY, point.Y)
return NewBoundingBox(newMinX, newMinY, newMaxX, newMaxY)
}
func (tree *RTree) split(node *RTreeNode) {
splitPoint := len(node.Children) / 2
newNode := NewRTreeNode(node.IsLeaf)
newNode.Children = append(newNode.Children, node.Children[splitPoint:]...)
node.Children = node.Children[:splitPoint]
node.BoundingBox = calculateBoundingBox(node.Children)
newNode.BoundingBox = calculateBoundingBox(newNode.Children)
if node == tree.Root {
newRoot := NewRTreeNode(false)
newRoot.Children = append(newRoot.Children, node, newNode)
newRoot.BoundingBox = calculateBoundingBox(newRoot.Children)
tree.Root = newRoot
}
}
func (tree *RTree) Delete(point point) {
tree.deleteRecursive(tree.Root, point)
}
func (tree *RTree) deleteRecursive(node *RTreeNode, point point) {
if node.IsLeaf {
var newChildren []point
for _, p := range node.Children {
if p != point {
newChildren = append(newChildren, p)
}
}
node.Children = newChildren
} else {
for _, child := range node.Children {
childBBox := calculateBoundingBox(child)
if pointInBoundingBox(point, childBBox) {
tree.deleteRecursive(&child, point)
break
}
}
node.BoundingBox = calculateBoundingBox(node.Children)
}
}
func (tree *RTree) Search(queryBBox *BoundingBox) []point {
result := make([]point, 0)
tree.searchRecursive(tree.Root, queryBBox, &result)
return result
}
func (tree *RTree) searchRecursive(node *RTreeNode, queryBBox *BoundingBox, result *[]point) {
if node.IsLeaf {
for _, p := range node.Children {
if pointInBoundingBox(p, queryBBox) {
*result = append(*result, p)
}
}
} else {
for _, child := range node.Children {
childBBox := calculateBoundingBox(child)
if bboxIntersectsQuery(childBBox, queryBBox) {
tree.searchRecursive(&child, queryBBox, result)
}
}
}
}
func (tree *RTree) NearestNeighbors(queryPoint point, k int) []point {
result := make([]point, 0)
tree.nearestNeighborsRecursive(tree.Root, queryPoint, k, &result)
return result
}
func (tree *RTree) nearestNeighborsRecursive(node *RTreeNode, queryPoint point, k int, result *[]point) {
if node.IsLeaf {
for _, p := range node.Children {
updateNearestNeighbors(queryPoint, p, k, result)
}
} else {
sortedChildren := make([]RTreeNode, len(node.Children))
copy(sortedChildren, node.Children)
sortChildren(sortedChildren, queryPoint)
for _, child := range sortedChildren {
childBBox := calculateBoundingBox(child)
if distance(queryPoint, childBBox) < result[len(result)-1].X {
tree.nearestNeighborsRecursive(&child, queryPoint, k, result)
}
}
}
}
func updateNearestNeighbors(queryPoint, point point, k int, result *[]point) {
distance := distance(queryPoint, point)
if len(*result) < k {
*result = append(*result, point)
sort.Slice(*result, func(i, j int) bool {
return distance(queryPoint, calculateBoundingBox((*result)[i])) > distance(queryPoint, calculateBoundingBox((*result)[j]))
})
} else if distance < distance(queryPoint, calculateBoundingBox((*result)[0])) {
(*result)[0] = point
sort.Slice(*result, func(i, j int) bool {
return distance(queryPoint, calculateBoundingBox((*result)[i])) > distance(queryPoint, calculateBoundingBox((*result)[j]))
})
}
}
func distance(point point, bbox *BoundingBox) float64 {
return math.Sqrt(math.Pow(point.X-bbox.MinX, 2) + math.Pow(point.Y-bbox.MinY, 2))
}
func (tree *RTree) RangeQuery(queryBBox *BoundingBox) []point {
result := make([]point, 0)
tree.rangeQueryRecursive(tree.Root, queryBBox, &result)
return result
}
func (tree *RTree) rangeQueryRecursive(node *RTreeNode, queryBBox *BoundingBox, result *[]point) {
if node.IsLeaf {
for _, p := range node.Children {
if pointInBoundingBox(p, queryBBox) {
*result = append(*result, p)
}
}
} else {
for _, child := range node.Children {
childBBox := calculateBoundingBox(child)
if bboxIntersectsQuery(childBBox, queryBBox) {
tree.rangeQueryRecursive(&child, queryBBox, result)
}
}
}
}
func (tree *RTree) WindowQuery(queryBBox *BoundingBox) []point {
result := make([]point, 0)
tree.windowQueryRecursive(tree.Root, queryBBox, &result)
return result
}
func (tree *RTree) windowQueryRecursive(node *RTreeNode, queryBBox *BoundingBox, result *[]point) {
if node.IsLeaf {
for _, p := range node.Children {
if pointInBoundingBox(p, queryBBox) {
*result = append(*result, p)
}
}
} else {
for _, child := range node.Children {
childBBox := calculateBoundingBox(child)
if bboxFullyContained(childBBox, queryBBox) {
tree.windowQueryRecursive(&child, queryBBox, result)
}
}
}
}
func (tree *RTree) KNNQuery(queryPoint point, k int) []point {
result := make([]point, 0)
tree.knnSearch(tree.Root, queryPoint, k, &result)
return result
}
func (tree *RTree) knnSearch(node *RTreeNode, queryPoint point, k int, result *[]point) {
if node.IsLeaf {
for _, p := range node.Children {
*result = append(*result, p)
}
} else {
distances := make([]struct {
child *RTreeNode
distance float64
}, len(node.Children))
for i, child := range node.Children {
distances[i] = struct {
child *RTreeNode
distance float64
}{&child, calculateMinDistance(queryPoint, calculateBoundingBox(child))}
}
sort.Slice(distances, func(i, j int) bool {
return distances[i].distance < distances[j].distance
})
for _, d := range distances[:k] {
tree.knnSearch(d.child, queryPoint, k, result)
}
}
}
func calculateMinDistance(point point, boundingBox *BoundingBox) float64 {
minDistance := 0.0
for i := 0; i < 2; i++ {
if point.X < boundingBox.MinX {
minDistance += math.Pow(boundingBox.MinX-point.X, 2)
} else if point.X > boundingBox.MaxX {
minDistance += math.Pow(point.X-boundingBox.MaxX, 2)
}
if point.Y < boundingBox.MinY {
minDistance += math.Pow(boundingBox.MinY-point.Y, 2)
} else if point.Y > boundingBox.MaxY {
minDistance += math.Pow(point.Y-boundingBox.MaxY, 2)
}
}
return math.Sqrt(minDistance)
}
func (tree *RTree) Update(oldPoint, newPoint point) {
tree.recursiveUpdate(tree.Root, oldPoint, newPoint)
}
func (tree *RTree) recursiveUpdate(node *RTreeNode, oldPoint, newPoint point) {
if node.IsLeaf {
for i, p := range node.Children {
if p == oldPoint {
node.Children[i] = newPoint
return
}
}
} else {
for _, child := range node.Children {
if intersects(calculateBoundingBox(child), oldPoint) {
tree.recursiveUpdate(&child, oldPoint, newPoint)
}
}
}
}
func intersects(box1 *BoundingBox, box2 point) bool {
return !(box1.MaxX < box2.X ||
box1.MinX > box2.X ||
box1.MaxY < box2.Y ||
box1.MinY > box2.Y)
}
func (tree *RTree) Traverse(visitFunc func(*RTreeNode)) {
tree.recursiveTraverse(tree.Root, visitFunc)
}
func (tree *RTree) recursiveTraverse(node *RTreeNode, visitFunc func(*RTreeNode)) {
visitFunc(node)
if !node.IsLeaf {
for _, child := range node.Children {
tree.recursiveTraverse(&child, visitFunc)
}
}
}
func printNodeInfo(node *RTreeNode, depth int) {
indentation := " "
if node.IsLeaf {
fmt.Printf("%sLeaf Node Bounding Box: %v\n", indentation, node.BoundingBox)
} else {
fmt.Printf("%sInternal Node Bounding Box: %v\n", indentation, node.BoundingBox)
}
}
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
class RTreeNode {
boolean isLeaf;
List<double[]> children;
double[] boundingBox;
RTreeNode(boolean isLeaf) {
this.isLeaf = isLeaf;
this.children = new ArrayList<>();
this.boundingBox = null;
}
}
public class RTree {
private RTreeNode root;
private int maxChildren;
public RTree(int maxChildren) {
this.root = new RTreeNode(true);
this.maxChildren = maxChildren;
}
public static void printNodeInfo(RTreeNode node, int depth) {
String indentation = " ".repeat(depth);
if (node.isLeaf) {
System.out.println(indentation + "Leaf Node Bounding Box: " + Arrays.toString(node.boundingBox));
} else {
System.out.println(indentation + "Internal Node Bounding Box: " + Arrays.toString(node.boundingBox));
}
}
public void insert(double[] point) {
insertRecursive(root, point);
}
private void insertRecursive(RTreeNode node, double[] point) {
if (node.isLeaf) {
node.children.add(point);
if (node.children.size() > maxChildren) {
split(node);
}
} else {
double minIncrease = Double.POSITIVE_INFINITY;
double[] bestChild = null;
for (double[] child : node.children) {
double[] childBBox = calculateBoundingBox(child);
double[] expandedBBox = calculateExpandedBoundingBox(childBBox, point);
double increase = calculateAreaIncrease(childBBox, expandedBBox);
if (increase < minIncrease) {
minIncrease = increase;
bestChild = child;
}
}
insertRecursive(node, point);
}
}
private double calculateAreaIncrease(double[] oldBBox, double[] newBBox) {
double oldArea = (oldBBox[2] - oldBBox[0]) * (oldBBox[3] - oldBBox[1]);
double newArea = (newBBox[2] - newBBox[0]) * (newBBox[3] - newBBox[1]);
return newArea - oldArea;
}
private double[] calculateExpandedBoundingBox(double[] oldBBox, double[] point) {
double min_x = Math.min(oldBBox[0], point[0]);
double min_y = Math.min(oldBBox[1], point[1]);
double max_x = Math.max(oldBBox[2], point[0]);
double max_y = Math.max(oldBBox[3], point[1]);
return new double[]{min_x, min_y, max_x, max_y};
}
private void split(RTreeNode node) {
int splitPoint = node.children.size() / 2;
RTreeNode newNode = new RTreeNode(node.isLeaf);
newNode.children.addAll(node.children.subList(splitPoint, node.children.size()));
node.children.subList(0, splitPoint).clear();
node.boundingBox = calculateBoundingBox(node.children);
newNode.boundingBox = calculateBoundingBox(newNode.children);
if (node == root) {
RTreeNode newRoot = new RTreeNode(false);
newRoot.children.add(node);
newRoot.children.add(newNode);
newRoot.boundingBox = calculateBoundingBox(newRoot.children);
root = newRoot;
}
}
public void delete(double[] point) {
deleteRecursive(root, point);
}
private void deleteRecursive(RTreeNode node, double[] point) {
if (node.isLeaf) {
node.children.removeIf(p -> Arrays.equals(p, point));
} else {
for (double[] child : node.children) {
double[] childBBox = calculateBoundingBox(child);
if (pointInBoundingBox(point, childBBox)) {
deleteRecursive(child, point);
break;
}
}
node.boundingBox = calculateBoundingBox(node.children);
}
}
public List<double[]> search(double[] queryBBox) {
List<double[]> result = new ArrayList<>();
searchRecursive(root, queryBBox, result);
return result;
}
private void searchRecursive(RTreeNode node, double[] queryBBox, List<double[]> result) {
if (node.isLeaf) {
for (double[] point : node.children) {
if (pointInBoundingBox(point, queryBBox)) {
result.add(point);
}
}
} else {
for (double[] child : node.children) {
double[] childBBox = calculateBoundingBox(child);
if (bboxIntersectsQuery(childBBox, queryBBox)) {
searchRecursive(child, queryBBox, result);
}
}
}
}
public List<double[]> nearestNeighbors(double[] queryPoint, int k) {
List<double[]> result = new ArrayList<>();
nearestNeighborsRecursive(root, queryPoint, k, result);
Collections.sort(result, Comparator.comparingDouble(p -> p[0]));
return result.subList(0, Math.min(k, result.size()));
}
private void nearestNeighborsRecursive(RTreeNode node, double[] queryPoint, int k, List<double[]> result) {
if (node.isLeaf) {
for (double[] point : node.children) {
updateNearestNeighbors(queryPoint, point, k, result);
}
} else {
List<double[]> sortedChildren = new ArrayList<>(node.children);
sortedChildren.sort(Comparator.comparingDouble(child -> distance(queryPoint, calculateBoundingBox(child))));
for (double[] child : sortedChildren) {
double[] childBBox = calculateBoundingBox(child);
if (distance(queryPoint, childBBox) < result.get(result.size() - 1)[0]) {
nearestNeighborsRecursive(child, queryPoint, k, result);
}
}
}
}
private void updateNearestNeighbors(double[] queryPoint, double[] point, int k, List<double[]> result) {
double distance = distance(queryPoint, point);
if (result.size() < k) {
result.add(new double[]{distance, point[0], point[1]});
result.sort(Comparator.comparingDouble(p -> p[0]));
} else if (distance < result.get(result.size() - 1)[0]) {
result.set(result.size() - 1, new double[]{distance, point[0], point[1]});
result.sort(Comparator.comparingDouble(p -> p[0]));
}
}
public List<double[]> rangeQuery(double[] queryBBox) {
List<double[]> result = new ArrayList<>();
rangeQueryRecursive(root, queryBBox, result);
return result;
}
private void rangeQueryRecursive(RTreeNode node, double[] queryBBox, List<double[]> result) {
if (node.isLeaf) {
for (double[] point : node.children) {
if (pointInBoundingBox(point, queryBBox)) {
result.add(point);
}
}
} else {
for (double[] child : node.children) {
double[] childBBox = calculateBoundingBox(child);
if (bboxIntersectsQuery(childBBox, queryBBox)) {
rangeQueryRecursive(child, queryBBox, result);
}
}
}
}
public List<double[]> windowQuery(double[] queryBBox) {
List<double[]> result = new ArrayList<>();
windowQueryRecursive(root, queryBBox, result);
return result;
}
private void windowQueryRecursive(RTreeNode node, double[] queryBBox, List<double[]> result) {
if (node.isLeaf) {
for (double[] point : node.children) {
if (pointInBoundingBox(point, queryBBox)) {
result.add(point);
}
}
} else {
for (double[] child : node.children) {
double[] childBBox = calculateBoundingBox(child);
if (bboxFullyContained(childBBox, queryBBox)) {
windowQueryRecursive(child, queryBBox, result);
}
}
}
}
public List<double[]> knnQuery(double[] queryPoint, int k) {
List<double[]> result = new ArrayList<>();
knnSearch(root, queryPoint, k, result);
Collections.sort(result, Comparator.comparingDouble(p -> p[1]));
return result.subList(0, Math.min(k, result.size()));
}
private void knnSearch(RTreeNode node, double[] queryPoint, int k, List<double[]> result) {
if (node.isLeaf) {
for (double[] child : node.children) {
result.add(new double[]{distance(queryPoint, calculateBoundingBox(child)), child[0], child[1]});
}
} else {
List<double[]> distances = new ArrayList<>();
for (double[] child : node.children) {
double[] childBBox = calculateBoundingBox(child);
distances.add(new double[]{distance(queryPoint, childBBox)});
}
distances.sort(Comparator.comparingDouble(p -> p[1]));
for (double[] distance : distances.subList(0, Math.min(k, distances.size()))) {
knnSearch(node, queryPoint, k, result);
}
}
}
private double distance(double[] point1, double[] point2) {
return Math.sqrt(Math.pow(point1[0] - point2[0], 2) + Math.pow(point1[1] - point2[1], 2));
}
public void update(double[] oldPoint, double[] newPoint) {
recursiveUpdate(root, oldPoint, newPoint);
}
private void recursiveUpdate(RTreeNode node, double[] oldPoint, double[] newPoint) {
if (node.isLeaf) {
for (int i = 0; i < node.children.size(); i++) {
double[] child = node.children.get(i);
if (Arrays.equals(child, oldPoint)) {
node.children.set(i, newPoint);
return;
}
}
} else {
for (RTreeNode child : node.children) {
if (intersects(child.boundingBox, oldPoint)) {
recursiveUpdate(child, oldPoint, newPoint);
}
}
}
}
private boolean intersects(double[] box1, double[] box2) {
return !(box1[2] < box2[0] || box1[0] > box2[2] || box1[3] < box2[1] || box1[1] > box2[3]);
}
public void traverse(VisitFunction visitFunction) {
recursiveTraverse(root, visitFunction);
}
private void recursiveTraverse(RTreeNode node, VisitFunction visitFunction) {
visitFunction.visit(node);
if (!node.isLeaf) {
for (RTreeNode child : node.children) {
recursiveTraverse(child, visitFunction);
}
}
}
public interface VisitFunction {
void visit(RTreeNode node);
}
}
class RTreeNode {
constructor(isLeaf = true) {
this.isLeaf = isLeaf;
this.children = [];
this.boundingBox = null;
}
}
class RTree {
constructor(maxChildren = 4) {
this.root = new RTreeNode();
this.maxChildren = maxChildren;
}
static printNodeInfo(node, depth) {
const indentation = " ".repeat(depth);
if (node.isLeaf) {
console.log(
`${indentation}Leaf Node Bounding Box: [${node.boundingBox.join(
", ",
)}]`,
);
} else {
console.log(
`${indentation}Internal Node Bounding Box: [${node.boundingBox.join(
", ",
)}]`,
);
}
}
insert(point) {
this._insertRecursive(this.root, point);
}
_insertRecursive(node, point) {
if (node.isLeaf) {
node.children.push(point);
if (node.children.length > this.maxChildren) {
this._split(node);
}
} else {
let minIncrease = Infinity;
let bestChild = null;
for (const child of node.children) {
const childBBox = this._calculateBoundingBox(child);
const expandedBBox = this._calculateExpandedBBox(childBBox, point);
const increase = this._calculateAreaIncrease(childBBox, expandedBBox);
if (increase < minIncrease) {
minIncrease = increase;
bestChild = child;
}
}
this._insertRecursive(bestChild, point);
}
}
_calculateAreaIncrease(oldBBox, newBBox) {
const oldArea = (oldBBox[2] - oldBBox[0]) * (oldBBox[3] - oldBBox[1]);
const newArea = (newBBox[2] - newBBox[0]) * (newBBox[3] - newBBox[1]);
return newArea - oldArea;
}
_calculateExpandedBBox(oldBBox, point) {
const [minX, minY, maxX, maxY] = oldBBox;
const newMinX = Math.min(minX, point[0]);
const newMinY = Math.min(minY, point[1]);
const newMaxX = Math.max(maxX, point[0]);
const newMaxY = Math.max(maxY, point[1]);
return [newMinX, newMinY, newMaxX, newMaxY];
}
_split(node) {
const splitPoint = Math.floor(node.children.length / 2);
const newNode = new RTreeNode({ isLeaf: node.isLeaf });
newNode.children = node.children.slice(splitPoint);
node.children = node.children.slice(0, splitPoint);
node.boundingBox = this._calculateBoundingBox(node.children);
newNode.boundingBox = this._calculateBoundingBox(newNode.children);
if (node === this.root) {
const newRoot = new RTreeNode({ isLeaf: false });
newRoot.children = [node, newNode];
newRoot.boundingBox = this._calculateBoundingBox(newRoot.children);
this.root = newRoot;
}
}
_deleteRecursive(node, point) {
if (node.isLeaf) {
node.children = node.children.filter((p) => !this._pointsEqual(p, point));
} else {
for (const child of node.children) {
const childBBox = this._calculateBoundingBox(child);
if (this._pointInBoundingBox(point, childBBox)) {
this._deleteRecursive(child, point);
break;
}
}
node.boundingBox = this._calculateBoundingBox(node.children);
}
}
_searchRecursive(node, queryBBox, result) {
if (node.isLeaf) {
for (const point of node.children) {
if (this._pointInBoundingBox(point, queryBBox)) {
result.push(point);
}
}
} else {
for (const child of node.children) {
const childBBox = this._calculateBoundingBox(child);
if (this._bboxIntersectsQuery(childBBox, queryBBox)) {
this._searchRecursive(child, queryBBox, result);
}
}
}
}
_nearestNeighborsRecursive(node, queryPoint, k, result) {
if (node.isLeaf) {
for (const point of node.children) {
this._updateNearestNeighbors(queryPoint, point, k, result);
}
} else {
const sortedChildren = node.children
.slice()
.sort(
(a, b) =>
this._distance(queryPoint, this._calculateBoundingBox(a)) -
this._distance(queryPoint, this._calculateBoundingBox(b)),
);
for (const child of sortedChildren) {
const childBBox = this._calculateBoundingBox(child);
if (
this._distance(queryPoint, childBBox) < result[result.length - 1][0]
) {
this._nearestNeighborsRecursive(child, queryPoint, k, result);
}
}
}
}
_updateNearestNeighbors(queryPoint, point, k, result) {
const distance = this._distance(queryPoint, point);
if (result.length < k) {
result.push([distance, point]);
result.sort((a, b) => b[0] - a[0]);
} else if (distance < result[0][0]) {
result[0] = [distance, point];
result.sort((a, b) => b[0] - a[0]);
}
}
_distance(point1, point2) {
return Math.sqrt(
Math.pow(point1[0] - point2[0], 2) + Math.pow(point1[1] - point2[1], 2),
);
}
rangeQuery(queryBBox) {
const result = [];
this._rangeQueryRecursive(this.root, queryBBox, result);
return result;
}
_rangeQueryRecursive(node, queryBBox, result) {
if (node.isLeaf) {
for (const point of node.children) {
if (this._pointInBoundingBox(point, queryBBox)) {
result.push(point);
}
}
} else {
for (const child of node.children) {
const childBBox = this._calculateBoundingBox(child);
if (this._bboxIntersectsQuery(childBBox, queryBBox)) {
this._rangeQueryRecursive(child, queryBBox, result);
}
}
}
}
_bboxIntersectsQuery(bbox, queryBBox) {
return !(
bbox[2] < queryBBox[0] ||
bbox[0] > queryBBox[2] ||
bbox[3] < queryBBox[1] ||
bbox[1] > queryBBox[3]
);
}
_windowQueryRecursive(node, queryBBox, result) {
if (node.isLeaf) {
for (const point of node.children) {
if (this._pointInBoundingBox(point, queryBBox)) {
result.push(point);
}
}
} else {
for (const child of node.children) {
const childBBox = this._calculateBoundingBox(child);
if (this._bboxFullyContained(childBBox, queryBBox)) {
this._windowQueryRecursive(child, queryBBox, result);
}
}
}
}
_bboxFullyContained(bbox1, bbox2) {
return (
bbox1[0] >= bbox2[0] &&
bbox1[1] >= bbox2[1] &&
bbox1[2] <= bbox2[2] &&
bbox1[3] <= bbox2[3]
);
}
_pointInBoundingBox(point, bbox) {
return (
point[0] >= bbox[0] &&
point[0] <= bbox[2] &&
point[1] >= bbox[1] &&
point[1] <= bbox[3]
);
}
_calculateBoundingBox(points) {
const minX = Math.min(...points.map((p) => p[0]));
const minY = Math.min(...points.map((p) => p[1]));
const maxX = Math.max(...points.map((p) => p[0]));
const maxY = Math.max(...points.map((p) => p[1]));
return [minX, minY, maxX, maxY];
}
knnQuery(queryPoint, k) {
const result = [];
this._knnSearch(this.root, queryPoint, k, result);
result.sort((a, b) => a[1] - b[1]);
return result.slice(0, k);
}
_knnSearch(node, queryPoint, k, result) {
if (node.isLeaf) {
for (const child of node.children) {
result.push([
child,
this._distance(queryPoint, this._calculateBoundingBox(child)),
]);
}
} else {
const distances = node.children.map((child) => [
child,
this._calculateMinDistance(
queryPoint,
this._calculateBoundingBox(child),
),
]);
distances.sort((a, b) => a[1] - b[1]);
for (const [child, _] of distances.slice(
0,
Math.min(k, distances.length),
)) {
this._knnSearch(child, queryPoint, k, result);
}
}
}
_calculateMinDistance(point, boundingBox) {
let minDistance = 0;
for (let i = 0; i < point.length; i++) {
if (point[i] < boundingBox[i]) {
minDistance += Math.pow(boundingBox[i] - point[i], 2);
} else if (point[i] > boundingBox[i + 2]) {
minDistance += Math.pow(point[i] - boundingBox[i + 2], 2);
}
}
return Math.sqrt(minDistance);
}
update(oldPoint, newPoint) {
this._recursiveUpdate(this.root, oldPoint, newPoint);
}
_recursiveUpdate(node, oldPoint, newPoint) {
if (node.isLeaf) {
for (let i = 0; i < node.children.length; i++) {
const child = node.children[i];
if (this._pointsEqual(child, oldPoint)) {
node.children[i] = newPoint;
return;
}
}
} else {
for (const child of node.children) {
if (this._intersects(child.boundingBox, oldPoint)) {
this._recursiveUpdate(child, oldPoint, newPoint);
}
}
}
}
_intersects(box1, box2) {
return !(
box1[2] < box2[0] ||
box1[0] > box2[2] ||
box1[3] < box2[1] ||
box1[1] > box2[3]
);
}
traverse(visitFunction) {
this._recursiveTraverse(this.root, visitFunction);
}
_recursiveTraverse(node, visitFunction) {
visitFunction.visit(node);
if (!node.isLeaf) {
for (const child of node.children) {
this._recursiveTraverse(child, visitFunction);
}
}
}
}
import kotlin.math.sqrt
data class RTreeNode(val isLeaf: Boolean = true, var children: MutableList<Pair<Double, Double>> = mutableListOf(), var boundingBox: Pair<Double, Double>? = null)
class RTree(private val maxChildren: Int = 4) {
var root = RTreeNode()
private set
fun insert(point: Pair<Double, Double>) {
insertRecursive(root, point)
}
private fun insertRecursive(node: RTreeNode, point: Pair<Double, Double>) {
if (node.isLeaf) {
node.children.add(point)
if (node.children.size > maxChildren) {
split(node)
}
} else {
var minIncrease = Double.POSITIVE_INFINITY
var bestChild: RTreeNode? = null
for (child in node.children) {
val childBBox = calculateBoundingBox(child)
val expandedBBox = calculateExpandedBoundingBox(childBBox, point)
val increase = calculateAreaIncrease(childBBox, expandedBBox)
if (increase < minIncrease) {
minIncrease = increase
bestChild = child
}
}
if (bestChild != null) {
insertRecursive(bestChild, point)
}
}
}
private fun calculateAreaIncrease(oldBBox: Pair<Double, Double>, newBBox: Pair<Double, Double>): Double {
val oldArea = (oldBBox.second - oldBBox.first) * (oldBBox.fourth - oldBBox.third)
val newArea = (newBBox.second - newBBox.first) * (newBBox.fourth - newBBox.third)
return newArea - oldArea
}
private fun calculateExpandedBoundingBox(oldBBox: Pair<Double, Double>, point: Pair<Double, Double>): Pair<Double, Double> {
val (minX, minY, maxX, maxY) = oldBBox
val newMinX = minOf(minX, point.first)
val newMinY = minOf(minY, point.second)
val newMaxX = maxOf(maxX, point.first)
val newMaxY = maxOf(maxY, point.second)
return Pair(newMinX, newMinY, newMaxX, newMaxY)
}
private fun split(node: RTreeNode) {
val splitPoint = node.children.size / 2
val newNode = RTreeNode(isLeaf = node.isLeaf)
newNode.children = node.children.subList(splitPoint, node.children.size).toMutableList()
node.children = node.children.subList(0, splitPoint).toMutableList()
node.boundingBox = calculateBoundingBox(node.children)
newNode.boundingBox = calculateBoundingBox(newNode.children)
if (node == root) {
val newRoot = RTreeNode(isLeaf = false)
newRoot.children = mutableListOf(node, newNode)
newRoot.boundingBox = calculateBoundingBox(newRoot.children)
root = newRoot
}
}
fun delete(point: Pair<Double, Double>) {
deleteRecursive(root, point)
}
private fun deleteRecursive(node: RTreeNode, point: Pair<Double, Double>) {
if (node.isLeaf) {
node.children.removeIf { it == point }
} else {
for (child in node.children) {
val childBBox = calculateBoundingBox(child)
if (pointInBoundingBox(point, childBBox)) {
deleteRecursive(child, point)
break
}
}
node.boundingBox = calculateBoundingBox(node.children)
}
}
fun search(queryBBox: Pair<Double, Double>): List<Pair<Double, Double>> {
val result = mutableListOf<Pair<Double, Double>>()
searchRecursive(root, queryBBox, result)
return result
}
private fun searchRecursive(node: RTreeNode, queryBBox: Pair<Double, Double>, result: MutableList<Pair<Double, Double>>) {
if (node.isLeaf) {
for (point in node.children) {
if (pointInBoundingBox(point, queryBBox)) {
result.add(point)
}
}
} else {
for (child in node.children) {
val childBBox = calculateBoundingBox(child)
if (bboxIntersectsQuery(childBBox, queryBBox)) {
searchRecursive(child, queryBBox, result)
}
}
}
}
fun nearestNeighbors(queryPoint: Pair<Double, Double>, k: Int): List<Pair<Double, Double>> {
val result = mutableListOf<Pair<Double, Double>>()
nearestNeighborsRecursive(root, queryPoint, k, result)
result.sortBy { it.first }
return result.take(k)
}
private fun nearestNeighborsRecursive(node: RTreeNode, queryPoint: Pair<Double, Double>, k: Int, result: MutableList<Pair<Double, Double>>) {
if (node.isLeaf) {
for (point in node.children) {
updateNearestNeighbors(queryPoint, point, k, result)
}
} else {
val sortedChildren = node.children.sortedBy { distance(queryPoint, calculateBoundingBox(it)) }
for (child in sortedChildren) {
val childBBox = calculateBoundingBox(child)
if (distance(queryPoint, childBBox) < result.lastOrNull()?.first ?: Double.POSITIVE_INFINITY) {
nearestNeighborsRecursive(child, queryPoint, k, result)
}
}
}
}
private fun updateNearestNeighbors(queryPoint: Pair<Double, Double>, point: Pair<Double, Double>, k: Int, result: MutableList<Pair<Double, Double>>) {
val distance = distance(queryPoint, point)
if (result.size < k) {
result.add(distance to point)
result.sortByDescending { it.first }
} else if (distance < result.first().first) {
result[0] = distance to point
result.sortByDescending { it.first }
}
}
private fun distance(point1: Pair<Double, Double>, point2: Pair<Double, Double>): Double {
return sqrt((point1.first - point2.first).pow(2) + (point1.second - point2.second).pow(2))
}
fun rangeQuery(queryBBox: Pair<Double, Double>): List<Pair<Double, Double>> {
val result = mutableListOf<Pair<Double, Double>>()
rangeQueryRecursive(root, queryBBox, result)
return result
}
private fun rangeQueryRecursive(node: RTreeNode, queryBBox: Pair<Double, Double>, result: MutableList<Pair<Double, Double>>) {
if (node.isLeaf) {
for (point in node.children) {
if (pointInBoundingBox(point, queryBBox)) {
result.add(point)
}
}
} else {
for (child in node.children) {
val childBBox = calculateBoundingBox(child)
if (bboxIntersectsQuery(childBBox, queryBBox)) {
rangeQueryRecursive(child, queryBBox, result)
}
}
}
}
fun windowQuery(queryBBox: Pair<Double, Double>): List<Pair<Double, Double>> {
val result = mutableListOf<Pair<Double, Double>>()
windowQueryRecursive(root, queryBBox, result)
return result
}
private fun windowQueryRecursive(node: RTreeNode, queryBBox: Pair<Double, Double>, result: MutableList<Pair<Double, Double>>) {
if (node.isLeaf) {
for (point in node.children) {
if (pointInBoundingBox(point, queryBBox)) {
result.add(point)
}
}
} else {
for (child in node.children) {
val childBBox = calculateBoundingBox(child)
if (bboxFullyContained(childBBox, queryBBox)) {
windowQueryRecursive(child, queryBBox, result)
}
}
}
}
private fun bboxFullyContained(bbox1: Pair<Double, Double>, bbox2: Pair<Double, Double>): Boolean {
return bbox1.first >= bbox2.first && bbox1.second >= bbox2.second && bbox1.third <= bbox2.third && bbox1.fourth <= bbox2.fourth
}
private fun pointInBoundingBox(point: Pair<Double, Double>, bbox: Pair<Double, Double>): Boolean {
return bbox.first <= point.first && point.first <= bbox.third && bbox.second <= point.second && point.second <= bbox.fourth
}
private fun calculateBoundingBox(points: List<Pair<Double, Double>>): Pair<Double, Double> {
val minX = points.minOf { it.first }
val minY = points.minOf { it.second }
val maxX = points.maxOf { it.first }
val maxY = points.maxOf { it.second }
return Pair(minX, minY, maxX, maxY)
}
fun knnQuery(queryPoint: Pair<Double, Double>, k: Int): List<Pair<Double, Double>> {
val result = mutableListOf<Pair<Double, Double>>()
knnSearch(root, queryPoint, k, result)
result.sortBy { it.second }
return result.take(k)
}
private fun knnSearch(node: RTreeNode, queryPoint: Pair<Double, Double>, k: Int, result: MutableList<Pair<Double, Double>>) {
if (node.isLeaf) {
for (child in node.children) {
result.add(child to distance(queryPoint, calculateBoundingBox(child)))
}
} else {
val distances = node.children.map { child ->
child to calculateMinDistance(queryPoint, calculateBoundingBox(child))
}
distances.sortedBy { it.second }
for ((child, _) in distances.take(k)) {
knnSearch(child, queryPoint, k, result)
}
}
}
private fun calculateMinDistance(point: Pair<Double, Double>, boundingBox: Pair<Double, Double>): Double {
var minDistance = 0.0
for (i in 0 until point.component1().toInt()) {
if (point.first < boundingBox.first) {
minDistance += (boundingBox.first - point.first).pow(2)
} else if (point.first > boundingBox.third) {
minDistance += (point.first - boundingBox.third).pow(2)
}
}
for (i in 0 until point.component2().toInt()) {
if (point.second < boundingBox.second) {
minDistance += (boundingBox.second - point.second).pow(2)
} else if (point.second > boundingBox.fourth) {
minDistance += (point.second - boundingBox.fourth).pow(2)
}
}
return sqrt(minDistance)
}
fun update(oldPoint: Pair<Double, Double>, newPoint: Pair<Double, Double>) {
recursiveUpdate(root, oldPoint, newPoint)
}
private fun recursiveUpdate(node: RTreeNode, oldPoint: Pair<Double, Double>, newPoint: Pair<Double, Double>) {
if (node.isLeaf) {
for (i in node.children.indices) {
if (node.children[i] == oldPoint) {
node.children[i] = newPoint
return
}
}
} else {
for (child in node.children) {
if (intersects(child, oldPoint)) {
recursiveUpdate(child, oldPoint, newPoint)
}
}
}
}
private fun intersects(box1: Pair<Double, Double>, box2: Pair<Double, Double>): Boolean {
return !(box1.third < box2.first || box1.first > box2.third || box1.fourth < box2.second || box1.second > box2.fourth)
}
fun traverse(visitFunc: (RTreeNode) -> Unit) {
recursiveTraverse(root, visitFunc)
}
private fun recursiveTraverse(node: RTreeNode, visitFunc: (RTreeNode) -> Unit) {
visitFunc(node)
if (!node.isLeaf) {
for (child in node.children) {
recursiveTraverse(child, visitFunc)
}
}
}
fun printNodeInfo(node: RTreeNode, depth: Int) {
val indentation = " ".repeat(depth)
if (node.isLeaf) {
println("${indentation}Leaf Node Bounding Box: ${node.boundingBox}")
} else {
println("${indentation}Internal Node Bounding Box: ${node.boundingBox}")
}
}
}
class RTreeNode:
def __init__(self, is_leaf=True):
self.is_leaf = is_leaf
self.children = []
self.bounding_box = None
class RTree:
def __init__(self, max_children=4):
self.root = RTreeNode()
self.max_children = max_children
def insert(self, point):
self._insert_recursive(self.root, point)
def _insert_recursive(self, node, point):
if node.is_leaf:
node.children.append(point)
if len(node.children) > self.max_children:
self._split(node)
else:
min_increase = float('inf')
best_child = None
for child in node.children:
child_bbox = self._calculate_bounding_box(child)
expanded_bbox = self._calculate_expanded_bbox(child_bbox, point)
increase = self._calculate_area_increase(child_bbox, expanded_bbox)
if increase < min_increase:
min_increase = increase
best_child = child
self._insert_recursive(best_child, point)
def _calculate_area_increase(self, old_bbox, new_bbox):
old_area = (old_bbox[2] - old_bbox[0]) * (old_bbox[3] - old_bbox[1])
new_area = (new_bbox[2] - new_bbox[0]) * (new_bbox[3] - new_bbox[1])
return new_area - old_area
def _calculate_expanded_bbox(self, old_bbox, point):
min_x, min_y, max_x, max_y = old_bbox
new_min_x = min(min_x, point[0])
new_min_y = min(min_y, point[1])
new_max_x = max(max_x, point[0])
new_max_y = max(max_y, point[1])
return (new_min_x, new_min_y, new_max_x, new_max_y)
def _split(self, node):
split_point = len(node.children) // 2
new_node = RTreeNode(is_leaf=node.is_leaf)
new_node.children = node.children[split_point:]
node.children = node.children[:split_point]
node.bounding_box = self._calculate_bounding_box(node.children)
new_node.bounding_box = self._calculate_bounding_box(new_node.children)
if node == self.root:
new_root = RTreeNode(is_leaf=False)
new_root.children = [node, new_node]
new_root.bounding_box = self._calculate_bounding_box(new_root.children)
self.root = new_root
def _delete_recursive(self, node, point):
if node.is_leaf:
node.children = [p for p in node.children if p != point]
else:
for child in node.children:
child_bbox = self._calculate_bounding_box(child)
if self._point_in_bbox(point, child_bbox):
self._delete_recursive(child, point)
break
node.bounding_box = self._calculate_bounding_box(node.children)
def _search_recursive(self, node, query_bbox, result):
if node.is_leaf:
for point in node.children:
if self._point_in_bbox(point, query_bbox):
result.append(point)
else:
for child in node.children:
child_bbox = self._calculate_bounding_box(child)
if self._bbox_intersects_query(child_bbox, query_bbox):
self._search_recursive(child, query_bbox, result)
def _nearest_neighbors_recursive(self, node, query_point, k, result):
if node.is_leaf:
for point in node.children:
self._update_nearest_neighbors(query_point, point, k, result)
else:
sorted_children = sorted(node.children, key=lambda child: self._distance(query_point, self._calculate_bounding_box(child)))
for child in sorted_children:
child_bbox = self._calculate_bounding_box(child)
if self._distance(query_point, child_bbox) < result[-1][0]:
self._nearest_neighbors_recursive(child, query_point, k, result)
def _update_nearest_neighbors(self, query_point, point, k, result):
distance = self._distance(query_point, point)
if len(result) < k:
result.append((distance, point))
result.sort(key=lambda x: x[0], reverse=True)
elif distance < result[0][0]:
result[0] = (distance, point)
result.sort(key=lambda x: x[0], reverse=True)
def _distance(self, point1, point2):
return math.sqrt((point1[0] - point2[0]) ** 2 + (point1[1] - point2[1]) ** 2)
def range_query(self, query_bbox):
result = []
self._range_query_recursive(self.root, query_bbox, result)
return result
def _range_query_recursive(self, node, query_bbox, result):
if node.is_leaf:
for point in node.children:
if self._point_in_bbox(point, query_bbox):
result.append(point)
else:
for child in node.children:
child_bbox = self._calculate_bounding_box(child)
if self._bbox_intersects_query(child_bbox, query_bbox):
self._range_query_recursive(child, query_bbox, result)
def _bbox_intersects_query(self, bbox, query_bbox):
return not (bbox[2] < query_bbox[0] or
bbox[0] > query_bbox[2] or
bbox[3] < query_bbox[1] or
bbox[1] > query_bbox[3])
def _window_query_recursive(self, node, query_bbox, result):
if node.is_leaf:
for point in node.children:
if self._point_in_bbox(point, query_bbox):
result.append(point)
else:
for child in node.children:
child_bbox = self._calculate_bounding_box(child)
if self._bbox_fully_contained(child_bbox, query_bbox):
self._window_query_recursive(child, query_bbox, result)
def _bbox_fully_contained(self, bbox1, bbox2):
return bbox1[0] >= bbox2[0] and bbox1[1] >= bbox2[1] and bbox1[2] <= bbox2[2] and bbox1[3] <= bbox2[3]
def _point_in_bbox(self, point, bbox):
return bbox[0] <= point[0] <= bbox[2] and bbox[1] <= point[1] <= bbox[3]
def _calculate_bounding_box(self, points):
min_x = min(p[0] for p in points)
min_y = min(p[1] for p in points)
max_x = max(p[0] for p in points)
max_y = max(p[1] for p in points)
return (min_x, min_y, max_x, max_y)
def knn_query(self, query_point, k):
result = []
_knn_search(self.root, query_point, k)
result.sort(key=lambda x: x[1])
return result[:k]
def _knn_search(node, query_point, k):
if node.is_leaf:
for child in node.children:
result.append((child, _distance(query_point, child.bounding_box)))
else:
distances = [(child, self.calculate_min_distance(query_point, child.bounding_box)) for child in node.children]
distances.sort(key=lambda x: x[1])
for child, _ in distances[:k]:
knn_search(child, query_point, k)
def calculate_min_distance(self, point, bounding_box):
min_distance = 0
for i in range(len(point)):
if point[i] < bounding_box[i]:
min_distance += (bounding_box[i] - point[i])**2
elif point[i] > bounding_box[i + 2]:
min_distance += (point[i] - bounding_box[i + 2])**2
return math.sqrt(min_distance)
def update(self, old_point, new_point):
recursive_update(self.root, old_point, new_point)
def recursive_update(node, old_point, new_point):
if node.is_leaf:
for i, child in enumerate(node.children):
if child.bounding_box == old_point:
node.children[i].bounding_box = new_point
return
else:
for child in node.children:
if self._intersects(child.bounding_box, old_point):
recursive_update(child, old_point, new_point)
def _intersects(self, box1, box2):
return not (box1[2] < box2[0] or
box1[0] > box2[2] or
box1[3] < box2[1] or
box1[1] > box2[3])
def traverse(self, visit_func):
recursive_traverse(self.root, visit_func)
def recursive_traverse(node, visit_func):
visit_func(node)
if not node.is_leaf:
for child in node.children:
recursive_traverse(child, visit_func)
def print_node_info(node, depth):
indentation = " " * depth
if node.is_leaf:
print(f"{indentation}Leaf Node Bounding Box:", node.bounding_box)
else:
print(f"{indentation}Internal Node Bounding Box:", node.bounding_box)
use std::cmp::{max, min};
#[derive(Debug)]
struct RTreeNode {
is_leaf: bool,
children: Vec<(f64, f64)>,
bounding_box: Option<(f64, f64, f64, f64)>,
}
impl RTreeNode {
fn new(is_leaf: bool) -> Self {
RTreeNode {
is_leaf,
children: Vec::new(),
bounding_box: None,
}
}
}
#[derive(Debug)]
struct RTree {
root: RTreeNode,
max_children: usize,
}
impl RTree {
fn new(max_children: usize) -> Self {
let root = RTreeNode::new(true);
RTree { root, max_children }
}
fn insert(&mut self, point: (f64, f64)) {
self.insert_recursive(&mut self.root, point);
}
fn insert_recursive(&mut self, node: &mut RTreeNode, point: (f64, f64)) {
if node.is_leaf {
node.children.push(point);
if node.children.len() > self.max_children {
self.split(node);
}
} else {
let mut min_increase = f64::INFINITY;
let mut best_child = None;
for child in &node.children {
let child_bbox = self.calculate_bounding_box(child);
let expanded_bbox = self.calculate_expanded_bbox(child_bbox, point);
let increase = self.calculate_area_increase(&child_bbox, &expanded_bbox);
if increase < min_increase {
min_increase = increase;
best_child = Some(child);
}
}
if let Some(best_child) = best_child {
self.insert_recursive(best_child, point);
}
}
}
fn calculate_area_increase(&self, old_bbox: &(f64, f64, f64, f64), new_bbox: &(f64, f64, f64, f64)) -> f64 {
let old_area = (old_bbox.2 - old_bbox.0) * (old_bbox.3 - old_bbox.1);
let new_area = (new_bbox.2 - new_bbox.0) * (new_bbox.3 - new_bbox.1);
new_area - old_area
}
fn calculate_expanded_bbox(&self, old_bbox: (f64, f64, f64, f64), point: (f64, f64)) -> (f64, f64, f64, f64) {
let (min_x, min_y, max_x, max_y) = old_bbox;
let new_min_x = min(min_x, point.0);
let new_min_y = min(min_y, point.1);
let new_max_x = max(max_x, point.0);
let new_max_y = max(max_y, point.1);
(new_min_x, new_min_y, new_max_x, new_max_y)
}
fn split(&mut self, node: &mut RTreeNode) {
let split_point = node.children.len() / 2;
let mut new_node = RTreeNode::new(node.is_leaf);
new_node.children = node.children.split_off(split_point);
node.bounding_box = Some(self.calculate_bounding_box(&node.children));
new_node.bounding_box = Some(self.calculate_bounding_box(&new_node.children));
if node.is_leaf {
let new_root = RTreeNode::new(false);
new_root.children.push(node.clone());
new_root.children.push(new_node);
new_root.bounding_box = Some(self.calculate_bounding_box(&new_root.children));
self.root = new_root;
} else {
let parent_bounding_box = self.calculate_bounding_box(&[&node.children, &new_node.children].concat());
node.bounding_box = Some(self.calculate_bounding_box(&node.children));
new_node.bounding_box = Some(self.calculate_bounding_box(&new_node.children));
let parent = &mut node.children;
parent.push(new_node);
node.bounding_box = Some(parent_bounding_box);
}
}
fn delete_recursive(&mut self, node: &mut RTreeNode, point: (f64, f64)) {
if node.is_leaf {
node.children.retain(|p| p != &point);
} else {
for child in &mut node.children {
let child_bbox = self.calculate_bounding_box(child);
if self.point_in_bbox(&point, &child_bbox) {
self.delete_recursive(child, point);
break;
}
}
node.bounding_box = Some(self.calculate_bounding_box(&node.children));
}
}
fn search_recursive(&self, node: &RTreeNode, query_bbox: (f64, f64, f64, f64), result: &mut Vec<(f64, f64)>) {
if node.is_leaf {
for point in &node.children {
if self.point_in_bbox(point, &query_bbox) {
result.push(*point);
}
}
} else {
for child in &node.children {
let child_bbox = self.calculate_bounding_box(child);
if self.bbox_intersects_query(&child_bbox, &query_bbox) {
self.search_recursive(child, query_bbox, result);
}
}
}
}
fn nearest_neighbors_recursive(&self, node: &RTreeNode, query_point: (f64, f64), k: usize, result: &mut Vec<(f64, (f64, f64))>) {
if node.is_leaf {
for point in &node.children {
self.update_nearest_neighbors(query_point, *point, k, result);
}
} else {
let mut sorted_children = node.children.clone();
sorted_children.sort_by(|a, b| {
let dist_a = self.distance(query_point, self.calculate_bounding_box(a));
let dist_b = self.distance(query_point, self.calculate_bounding_box(b));
dist_a.partial_cmp(&dist_b).unwrap()
});
for child in &sorted_children {
let child_bbox = self.calculate_bounding_box(child);
if self.distance(query_point, child_bbox) < result.last().map(|x| x.0).unwrap_or(f64::INFINITY) {
self.nearest_neighbors_recursive(child, query_point, k, result);
}
}
}
}
fn update_nearest_neighbors(&self, query_point: (f64, f64), point: (f64, f64), k: usize, result: &mut Vec<(f64, (f64, f64))>) {
let distance = self.distance(query_point, point);
if result.len() < k {
result.push((distance, point));
result.sort_by(|a, b| b.0.partial_cmp(&a.0).unwrap());
} else if distance < result[0].0 {
result[0] = (distance, point);
result.sort_by(|a, b| b.0.partial_cmp(&a.0).unwrap());
}
}
fn distance(&self, point1: (f64, f64), point2: (f64, f64)) -> f64 {
((point1.0 - point2.0).powi(2) + (point1.1 - point2.1).powi(2)).sqrt()
}
fn range_query(&self, query_bbox: (f64, f64, f64, f64)) -> Vec<(f64, f64)> {
let mut result = Vec::new();
self.range_query_recursive(&self.root, query_bbox, &mut result);
result
}
fn range_query_recursive(&self, node: &RTreeNode, query_bbox: (f64, f64, f64, f64), result: &mut Vec<(f64, f64)>) {
if node.is_leaf {
for point in &node.children {
if self.point_in_bbox(point, &query_bbox) {
result.push(*point);
}
}
} else {
for child in &node.children {
let child_bbox = self.calculate_bounding_box(child);
if self.bbox_intersects_query(&child_bbox, &query_bbox) {
self.range_query_recursive(child, query_bbox, result);
}
}
}
}
fn bbox_intersects_query(&self, bbox: &(f64, f64, f64, f64), query_bbox: &(f64, f64, f64, f64)) -> bool {
!(bbox.2 < query_bbox.0 || bbox.0 > query_bbox.2 || bbox.3 < query_bbox.1 || bbox.1 > query_bbox.3)
}
fn window_query_recursive(&self, node: &RTreeNode, query_bbox: (f64, f64, f64, f64), result: &mut Vec<(f64, f64)>) {
if node.is_leaf {
for point in &node.children {
if self.point_in_bbox(point, &query_bbox) {
result.push(*point);
}
}
} else {
for child in &node.children {
let child_bbox = self.calculate_bounding_box(child);
if self.bbox_fully_contained(&child_bbox, &query_bbox) {
self.window_query_recursive(child, query_bbox, result);
}
}
}
}
fn bbox_fully_contained(&self, bbox1: &(f64, f64, f64, f64), bbox2: &(f64, f64, f64, f64)) -> bool {
bbox1.0 >= bbox2.0 && bbox1.1 >= bbox2.1 && bbox1.2 <= bbox2.2 && bbox1.3 <= bbox2.3
}
fn point_in_bbox(&self, point: &(f64, f64), bbox: &(f64, f64, f64, f64)) -> bool {
bbox.0 <= point.0 && point.0 <= bbox.2 && bbox.1 <= point.1 && point.1 <= bbox.3
}
fn calculate_bounding_box(&self, points: &[(f64, f64)]) -> (f64, f64, f64, f64) {
let min_x = points.iter().map(|p| p.0).fold(f64::INFINITY, f64::min);
let min_y = points.iter().map(|p| p.1).fold(f64::INFINITY, f64::min);
let max_x = points.iter().map(|p| p.0).fold(f64::NEG_INFINITY, f64::max);
let max_y = points.iter().map(|p| p.1).fold(f64::NEG_INFINITY, f64::max);
(min_x, min_y, max_x, max_y)
}
fn knn_query(&self, query_point: (f64, f64), k: usize) -> Vec<(f64, (f64, f64))> {
let mut result = Vec::new();
self.knn_search(&self.root, query_point, k, &mut result);
result.sort_by(|a, b| a.0.partial_cmp(&b.0).unwrap());
result.truncate(k);
result
}
fn knn_search(&self, node: &RTreeNode, query_point: (f64, f64), k: usize, result: &mut Vec<(f64, (f64, f64))>) {
if node.is_leaf {
for child in &node.children {
result.push((self.distance(query_point, *child), *child));
}
} else {
let mut distances: Vec<_> = node.children.iter()
.map(|child| (child, self.calculate_min_distance(query_point, child)))
.collect();
distances.sort_by(|a, b| a.1.partial_cmp(&b.1).unwrap());
for (child, _) in distances.iter().take(k) {
self.knn_search(child, query_point, k, result);
}
}
}
fn calculate_min_distance(&self, point: (f64, f64), bounding_box: &(f64, f64, f64, f64)) -> f64 {
let mut min_distance = 0.0;
for i in 0..2 {
if point.0 < bounding_box.0 {
min_distance += (bounding_box.0 - point.0).powi(2);
} else if point.0 > bounding_box.2 {
min_distance += (point.0 - bounding_box.2).powi(2);
}
if point.1 < bounding_box.1 {
min_distance += (bounding_box.1 - point.1).powi(2);
} else if point.1 > bounding_box.3 {
min_distance += (point.1 - bounding_box.3).powi(2);
}
}
min_distance.sqrt()
}
fn update(&mut self, old_point: (f64, f64), new_point: (f64, f64)) {
self.recursive_update(&mut self.root, old_point, new_point);
}
fn recursive_update(&mut self, node: &mut RTreeNode, old_point: (f64, f64), new_point: (f64, f64)) {
if node.is_leaf {
for i in 0..node.children.len() {
if node.children[i] == old_point {
node.children[i] = new_point;
return;
}
}
} else {
for child in &mut node.children {
if self.intersects(child, &old_point) {
self.recursive_update(child, old_point, new_point);
return;
}
}
}
}
fn intersects(&self, box1: &(f64, f64, f64, f64), box2: &(f64, f64)) -> bool {
!(box1.2 < box2.0 || box1.0 > box2.2 || box1.3 < box2.1 || box1.1 > box2.3)
}
fn traverse(&self, visit_func: impl FnMut(&RTreeNode)) {
self.recursive_traverse(&self.root, visit_func);
}
fn recursive_traverse(&self, node: &RTreeNode, mut visit_func: impl FnMut(&RTreeNode)) {
visit_func(node);
if !node.is_leaf {
for child in &node.children {
self.recursive_traverse(child, &mut visit_func);
}
}
}
fn print_node_info(&self, node: &RTreeNode, depth: usize) {
let indentation = " ".repeat(depth);
if node.is_leaf {
println!("{indentation}Leaf Node Bounding Box: {:?}", node.bounding_box);
} else {
println!("{indentation}Internal Node Bounding Box: {:?}", node.bounding_box);
}
}
}
class RTreeNode {
is_leaf: boolean;
children: any[];
bounding_box: number[] | null;
constructor(is_leaf: boolean = true) {
this.is_leaf = is_leaf;
this.children = [];
this.bounding_box = null;
}
}
class RTree {
root: RTreeNode;
max_children: number;
constructor(max_children: number = 4) {
this.root = new RTreeNode();
this.max_children = max_children;
}
insert(point: number[]): void {
this._insertRecursive(this.root, point);
}
rangeQuery(queryBbox: number[]): number[][] {
const result: number[][] = [];
this._rangeQueryRecursive(this.root, queryBbox, result);
return result;
}
knnQuery(queryPoint: number[], k: number): [number, number][][] {
const result: [number, number][][] = [];
this._knnSearch(this.root, queryPoint, k, result);
result.sort((a, b) => a[1] - b[1]);
return result.slice(0, k);
}
calculateMinDistance(point: number[], boundingBox: number[]): number {
let minDistance = 0;
for (let i = 0; i < point.length; i++) {
if (point[i] < boundingBox[i]) {
minDistance += (boundingBox[i] - point[i]) ** 2;
} else if (point[i] > boundingBox[i + 2]) {
minDistance += (point[i] - boundingBox[i + 2]) ** 2;
}
}
return Math.sqrt(minDistance);
}
update(oldPoint: number[], newPoint: number[]): void {
this._recursiveUpdate(this.root, oldPoint, newPoint);
}
traverse(visitFunc: (node: RTreeNode) => void): void {
this._recursiveTraverse(this.root, visitFunc);
}
printNodeInfo(node: RTreeNode, depth: number): void {
const indentation = " ".repeat(depth);
if (node.is_leaf) {
console.log(`${indentation}Leaf Node Bounding Box:`, node.bounding_box);
} else {
console.log(
`${indentation}Internal Node Bounding Box:`,
node.bounding_box,
);
}
}
private _insertRecursive(node: RTreeNode, point: number[]): void {
if (node.is_leaf) {
node.children.push(point);
if (node.children.length > this.max_children) {
this._split(node);
}
} else {
let min_increase = Infinity;
let best_child = null;
for (const child of node.children) {
const childBbox = this._calculateBoundingBox(child);
const expandedBbox = this._calculateExpandedBbox(childBbox, point);
const increase = this._calculateAreaIncrease(childBbox, expandedBbox);
if (increase < min_increase) {
min_increase = increase;
best_child = child;
}
}
if (best_child) {
this._insertRecursive(best_child, point);
}
}
}
private _calculateAreaIncrease(oldBbox: number[], newBbox: number[]): number {
const oldArea = (oldBbox[2] - oldBbox[0]) * (oldBbox[3] - oldBbox[1]);
const newArea = (newBbox[2] - newBbox[0]) * (newBbox[3] - newBbox[1]);
return newArea - oldArea;
}
private _calculateExpandedBbox(oldBbox: number[], point: number[]): number[] {
const [minX, minY, maxX, maxY] = oldBbox;
const newMinX = Math.min(minX, point[0]);
const newMinY = Math.min(minY, point[1]);
const newMaxX = Math.max(maxX, point[0]);
const newMaxY = Math.max(maxY, point[1]);
return [newMinX, newMinY, newMaxX, newMaxY];
}
private _split(node: RTreeNode): void {
const splitPoint = Math.floor(node.children.length / 2);
const newNode = new RTreeNode({ is_leaf: node.is_leaf });
newNode.children = node.children.slice(splitPoint);
node.children = node.children.slice(0, splitPoint);
node.bounding_box = this._calculateBoundingBox(node.children);
newNode.bounding_box = this._calculateBoundingBox(newNode.children);
if (node === this.root) {
const newRoot = new RTreeNode({ is_leaf: false });
newRoot.children = [node, newNode];
newRoot.bounding_box = this._calculateBoundingBox(newRoot.children);
this.root = newRoot;
}
}
private _deleteRecursive(node: RTreeNode, point: number[]): void {
if (node.is_leaf) {
node.children = node.children.filter((p) => p !== point);
} else {
for (const child of node.children) {
const childBbox = this._calculateBoundingBox(child);
if (this._pointInBbox(point, childBbox)) {
this._deleteRecursive(child, point);
break;
}
}
node.bounding_box = this._calculateBoundingBox(node.children);
}
}
private _searchRecursive(
node: RTreeNode,
queryBbox: number[],
result: number[][],
): void {
if (node.is_leaf) {
for (const point of node.children) {
if (this._pointInBbox(point, queryBbox)) {
result.push(point);
}
}
} else {
for (const child of node.children) {
const childBbox = this._calculateBoundingBox(child);
if (this._bboxIntersectsQuery(childBbox, queryBbox)) {
this._searchRecursive(child, queryBbox, result);
}
}
}
}
private _nearestNeighborsRecursive(
node: RTreeNode,
queryPoint: number[],
k: number,
result: [number, number][],
): void {
if (node.is_leaf) {
for (const point of node.children) {
this._updateNearestNeighbors(queryPoint, point, k, result);
}
} else {
const sortedChildren = node.children
.slice()
.sort(
(a, b) =>
this._distance(queryPoint, this._calculateBoundingBox(a)) -
this._distance(queryPoint, this._calculateBoundingBox(b)),
);
for (const child of sortedChildren) {
const childBbox = this._calculateBoundingBox(child);
if (
this._distance(queryPoint, childBbox) < result[result.length - 1][0]
) {
this._nearestNeighborsRecursive(child, queryPoint, k, result);
}
}
}
}
private _updateNearestNeighbors(
queryPoint: number[],
point: number[],
k: number,
result: [number, number][],
): void {
const distance = this._distance(queryPoint, point);
if (result.length < k) {
result.push([distance, ...point]);
result.sort((a, b) => b[0] - a[0]);
} else if (distance < result[0][0]) {
result[0] = [distance, ...point];
result.sort((a, b) => b[0] - a[0]);
}
}
private _distance(point1: number[], point2: number[]): number {
return Math.sqrt(
(point1[0] - point2[0]) ** 2 + (point1[1] - point2[1]) ** 2,
);
}
private _rangeQueryRecursive(
node: RTreeNode,
queryBbox: number[],
result: number[][],
): void {
if (node.is_leaf) {
for (const point of node.children) {
if (this._pointInBbox(point, queryBbox)) {
result.push(point);
}
}
} else {
for (const child of node.children) {
const childBbox = this._calculateBoundingBox(child);
if (this._bboxIntersectsQuery(childBbox, queryBbox)) {
this._rangeQueryRecursive(child, queryBbox, result);
}
}
}
}
private _bboxIntersectsQuery(bbox: number[], queryBbox: number[]): boolean {
return !(
bbox[2] < queryBbox[0] ||
bbox[0] > queryBbox[2] ||
bbox[3] < queryBbox[1] ||
bbox[1] > queryBbox[3]
);
}
private _windowQueryRecursive(
node: RTreeNode,
queryBbox: number[],
result: number[][],
): void {
if (node.is_leaf) {
for (const point of node.children) {
if (this._pointInBbox(point, queryBbox)) {
result.push(point);
}
}
} else {
for (const child of node.children) {
const childBbox = this._calculateBoundingBox(child);
if (this._bboxFullyContained(childBbox, queryBbox)) {
this._windowQueryRecursive(child, queryBbox, result);
}
}
}
}
private _bboxFullyContained(bbox1: number[], bbox2: number[]): boolean {
return (
bbox1[0] >= bbox2[0] &&
bbox1[1] >= bbox2[1] &&
bbox1[2] <= bbox2[2] &&
bbox1[3] <= bbox2[3]
);
}
private _pointInBbox(point: number[], bbox: number[]): boolean {
return (
bbox[0] <= point[0] &&
point[0] <= bbox[2] &&
bbox[1] <= point[1] &&
point[1] <= bbox[3]
);
}
private _calculateBoundingBox(points: number[][]): number[] {
const minX = Math.min(...points.map((p) => p[0]));
const minY = Math.min(...points.map((p) => p[1]));
const maxX = Math.max(...points.map((p) => p[0]));
const maxY = Math.max(...points.map((p) => p[1]));
return [minX, minY, maxX, maxY];
}
private _knnSearch(
node: RTreeNode,
queryPoint: number[],
k: number,
result: [number, number][][],
): void {
if (node.is_leaf) {
for (const child of node.children) {
result.push([
child,
this._distance(queryPoint, this._calculateBoundingBox(child)),
]);
}
} else {
const distances: [number[], number][] = node.children.map((child) => [
child,
this.calculateMinDistance(
queryPoint,
this._calculateBoundingBox(child),
),
]);
distances.sort((a, b) => a[1] - b[1]);
for (const [child, _] of distances.slice(0, k)) {
this._knnSearch(child, queryPoint, k, result);
}
}
}
private _recursiveUpdate(
node: RTreeNode,
oldPoint: number[],
newPoint: number[],
): void {
if (node.is_leaf) {
for (let i = 0; i < node.children.length; i++) {
if (node.children[i].bounding_box.join(",") === oldPoint.join(",")) {
node.children[i].bounding_box = newPoint;
return;
}
}
} else {
for (const child of node.children) {
if (this._intersects(child.bounding_box, oldPoint)) {
this._recursiveUpdate(child, oldPoint, newPoint);
}
}
}
}
private _intersects(box1: number[], box2: number[]): boolean {
return !(
box1[2] < box2[0] ||
box1[0] > box2[2] ||
box1[3] < box2[1] ||
box1[1] > box2[3]
);
}
private _recursiveTraverse(
node: RTreeNode,
visitFunc: (node: RTreeNode) => void,
): void {
visitFunc(node);
if (!node.is_leaf) {
for (const child of node.children) {
this._recursiveTraverse(child, visitFunc);
}
}
}
}