JavaScript Octree Implementation

This challenge requires you to build an Octree data structure in JavaScript. Octrees are hierarchical tree data structures used to partition a three-dimensional space by recursively subdividing it into eight octants. This is particularly useful for efficiently storing and querying spatial data, such as points, bounding boxes, or collision detection in 3D applications like games or simulations.

Problem Description

You need to implement a JavaScript class representing an Octree. This Octree should be capable of storing points in 3D space. The main functionality will be inserting points and querying for points within a specified region.

Key Requirements:

1. Octree Node Structure: Each node in the Octree should represent a cubic region in 3D space. It should store:

   • The bounding box (min and max coordinates) of the region it represents.
   • A list of points contained directly within this node (if it's a leaf node or before subdivision).
   • References to its eight children nodes (if subdivided).
   • A maximum capacity for points before subdivision.

2. Insertion (insert method):

   • The insert method should take a 3D point (e.g., an object with x, y, z properties) as input.
   • When a point is inserted, it should be placed in the appropriate child node.
   • If a node reaches its maximum capacity, it should subdivide itself into eight children, distributing the existing points and the new point among them.
   • Points should only be stored in leaf nodes, or if they lie exactly on the boundary of subdivisions (you can decide on a consistent rule for this, e.g., always assign to the octant that contains the majority of the point's volume if it's an object, or a specific octant if it's a point). For simplicity in this challenge, assume points are distinct and we can assign them to one octant.

3. Querying (queryRange method):

   • The queryRange method should accept a bounding box (defined by its minimum and maximum x, y, z coordinates) and return an array of all points within that bounding box.
   • The query should efficiently traverse the Octree, only visiting nodes whose regions intersect with the query bounding box.

Expected Behavior:

• The Octree should be initialized with a root bounding box and a maximum capacity per node.
• Inserting points should correctly populate the tree.
• Querying should return accurate results, including points from parent nodes if the query range encompasses them and they are within the query range.

Edge Cases:

• Inserting points exactly on the boundaries between octants.
• Querying with a bounding box that is larger or smaller than the Octree's root bounding box.
• Querying an empty Octree.
• Inserting a large number of points to test subdivision.

Examples

Example 1:

// Define point structure
class Point {
    constructor(x, y, z) {
        this.x = x;
        this.y = y;
        this.z = z;
    }
}

// Define bounding box structure
class BoundingBox {
    constructor(minX, minY, minZ, maxX, maxY, maxZ) {
        this.minX = minX;
        this.minY = minY;
        this.minZ = minZ;
        this.maxX = maxX;
        this.maxY = maxY;
        this.maxZ = maxZ;
    }

    // Helper to check if a point is inside this bounding box
    containsPoint(point) {
        return point.x >= this.minX && point.x <= this.maxX &&
               point.y >= this.minY && point.y <= this.maxY &&
               point.z >= this.minZ && point.z <= this.maxZ;
    }

    // Helper to check if this bounding box intersects with another
    intersects(otherBox) {
        return !(otherBox.maxX < this.minX || otherBox.minX > this.maxX ||
                 otherBox.maxY < this.minY || otherBox.minY > this.maxY ||
                 otherBox.maxZ < this.minZ || otherBox.minZ > this.maxZ);
    }
}

// Assume Octree class with insert and queryRange methods is implemented

// Initialize Octree
const rootBounds = new BoundingBox(0, 0, 0, 100, 100, 100);
const maxCapacity = 4;
const octree = new Octree(rootBounds, maxCapacity);

// Insert points
const pointsToInsert = [
    new Point(10, 10, 10),
    new Point(60, 60, 60),
    new Point(20, 20, 20),
    new Point(70, 70, 70),
    new Point(30, 30, 30), // This will trigger subdivision of the first octant
    new Point(80, 80, 80),
    new Point(90, 90, 90)
];

pointsToInsert.forEach(p => octree.insert(p));

// Query for points in a region
const queryBox = new BoundingBox(0, 0, 0, 40, 40, 40);
const foundPoints = octree.queryRange(queryBox);

console.log(foundPoints);

Output:

[
  Point { x: 10, y: 10, z: 10 },
  Point { x: 20, y: 20, z: 20 },
  Point { x: 30, y: 30, z: 30 }
]

Explanation: The Octree is initialized to cover the space from (0,0,0) to (100,100,100) with a max capacity of 4 points per node. Points (10,10,10), (20,20,20), (60,60,60), and (70,70,70) are inserted. When (30,30,30) is inserted, the root node (or the first octant node if it was already subdivided) exceeds its capacity of 4. It subdivides. The query box from (0,0,0) to (40,40,40) only contains points (10,10,10), (20,20,20), and (30,30,30) that fall within this specific region.

Example 2:

// ... (Point and BoundingBox classes as above)

// Initialize Octree
const rootBounds = new BoundingBox(-50, -50, -50, 50, 50, 50);
const maxCapacity = 2;
const octree = new Octree(rootBounds, maxCapacity);

// Insert points
const pointsToInsert = [
    new Point(0, 0, 0),
    new Point(10, 10, 10),
    new Point(-10, -10, -10),
    new Point(5, 5, 5) // Triggers subdivision
];

pointsToInsert.forEach(p => octree.insert(p));

// Query for points in a larger region that encompasses multiple octants
const queryBox = new BoundingBox(-20, -20, -20, 20, 20, 20);
const foundPoints = octree.queryRange(queryBox);

console.log(foundPoints);

Output:

[
  Point { x: 0, y: 0, z: 0 },
  Point { x: 10, y: 10, z: 10 },
  Point { x: -10, y: -10, z: -10 },
  Point { x: 5, y: 5, z: 5 }
]

Explanation: The Octree is initialized to cover a space centered at the origin. With a low capacity of 2, it subdivides early. The query box is large enough to encompass points from several of the octants that have been created. All points inserted fall within this query range.

Example 3: Querying an empty region

// ... (Point and BoundingBox classes as above)

// Initialize Octree
const rootBounds = new BoundingBox(0, 0, 0, 100, 100, 100);
const maxCapacity = 4;
const octree = new Octree(rootBounds, maxCapacity);

// Insert a single point
octree.insert(new Point(50, 50, 50));

// Query for points in a region that doesn't contain the inserted point
const queryBox = new BoundingBox(0, 0, 0, 10, 10, 10);
const foundPoints = octree.queryRange(queryBox);

console.log(foundPoints);

Output:

[]

Explanation: An Octree is created and a single point is inserted at (50,50,50). A query is then made for points within the region (0,0,0) to (10,10,10). Since the inserted point is outside this query region, the result is an empty array.

Constraints

• Point Coordinates: Point coordinates (x, y, z) will be integers or floating-point numbers within the range [-1000, 1000].
• Bounding Box Dimensions: The root bounding box will be axis-aligned and cubic, with minX = minY = minZ and maxX = maxY = maxZ. The initial size will be between 1 and 1000.
• Max Capacity: The maximum capacity per node will be an integer between 1 and 16.
• Number of Points: You can expect to insert up to 10,000 points.
• Performance: The queryRange operation should ideally have an average time complexity better than O(N) where N is the total number of points, by leveraging the spatial partitioning of the Octree.

Notes

• You will need to define helper classes for Point and BoundingBox or use a similar representation. A BoundingBox class should at least have methods to check if a point is contained within it and if it intersects with another BoundingBox.
• When subdividing a node, you'll need to determine how to divide its space into eight equal octants. Consider the center point of the current node's bounding box.
• The octants can be indexed (e.g., 0 to 7) or named based on their relative position to the center (e.g., front-bottom-left, back-top-right). Consistency is key.
• Think about how to handle points that lie exactly on the boundary between octants. A common approach is to assign them to one specific octant consistently.
• The queryRange method should recursively check for intersections between the query box and the bounding boxes of child nodes.