Octree Implementation in JavaScript

Octrees are tree data structures used for spatial partitioning, efficiently organizing 3D space into hierarchical regions. They are invaluable for collision detection, ray tracing, and other applications involving spatial queries. This challenge asks you to implement a basic octree in JavaScript, capable of inserting and querying points within its defined bounds.

Problem Description

You are tasked with creating an Octree class in JavaScript. The octree should be initialized with a bounding box (defined by its minimum and maximum coordinates) and a maximum capacity for points it can hold before subdividing. The class should provide the following methods:

• insert(point, data): Inserts a point (represented as an array [x, y, z]) and associated data into the octree. The point should be added to the appropriate leaf node. If a node reaches its maximum capacity, it should subdivide into eight child octrees.
• queryRange(min, max): Returns an array of all points within the specified range (defined by its minimum and maximum coordinates). The range is a bounding box.
• getBoundingBox(): Returns the bounding box of the octree as an object with min and max properties, each containing an array [x, y, z].

Key Requirements:

• The octree should recursively subdivide when a node's capacity is exceeded.
• Points should be stored within leaf nodes.
• The queryRange method should efficiently search for points within the given range.
• The octree should handle empty input gracefully.

Expected Behavior:

• insert should correctly place points within the octree, subdividing when necessary.
• queryRange should return all points within the specified range, and no points outside of it.
• getBoundingBox should return the correct bounding box.

Edge Cases to Consider:

• Empty input (no points to insert).
• Points lying exactly on the boundaries of octant divisions.
• Ranges that completely encompass the octree's bounding box.
• Ranges that do not intersect the octree's bounding box.
• Very large or very small bounding boxes.

Examples

Example 1:

Input:
Octree(min=[0, 0, 0], max=[10, 10, 10], capacity=2)
insert([2, 2, 2], "data1")
insert([7, 7, 7], "data2")
insert([1, 1, 1], "data3")
queryRange([0, 0, 0], [5, 5, 5])
Output: [[2, 2, 2, "data1"], [1, 1, 1, "data3"]]
Explanation: The query range encompasses points [2, 2, 2] and [1, 1, 1]. [7, 7, 7] is outside the range.

Example 2:

Input:
Octree(min=[0, 0, 0], max=[10, 10, 10], capacity=1)
insert([2, 2, 2], "data1")
insert([7, 7, 7], "data2")
queryRange([0, 0, 0], [10, 10, 10])
Output: [[2, 2, 2, "data1"], [7, 7, 7, "data2"]]
Explanation: The query range encompasses all points in the octree.

Example 3: (Edge Case - No Intersection)

Input:
Octree(min=[0, 0, 0], max=[10, 10, 10], capacity=2)
insert([2, 2, 2], "data1")
insert([7, 7, 7], "data2")
queryRange([15, 15, 15], [20, 20, 20])
Output: []
Explanation: The query range does not intersect the octree's bounding box, so no points are returned.

Constraints

• The coordinates of points and bounding boxes will be numbers.
• The capacity of the octree will be a positive integer.
• The bounding box will be defined by min and max arrays, where min[i] < max[i] for all dimensions i.
• The octree should be reasonably efficient for a basic implementation. While a highly optimized implementation is not required, avoid unnecessary computations.
• The maximum depth of the octree should be limited to prevent excessive recursion. A reasonable limit is 10.

Notes

• Consider using a recursive approach to implement the octree's subdivision and querying logic.
• Think about how to efficiently determine if a point lies within a given octant.
• The data associated with each point can be of any type.
• When subdividing, ensure that the child octrees have the correct bounding boxes.
• You can assume that the input points are within the octree's initial bounding box.
• Focus on correctness and clarity of code over extreme optimization.