Implement Quadtree for Spatial Partitioning in JavaScript

Quadtrees are a powerful data structure used for efficiently partitioning a 2D space. They are particularly useful in applications like game development, image processing, and collision detection where you need to quickly query for objects within a specific region. This challenge asks you to implement a basic quadtree structure in JavaScript.

Problem Description

Your task is to implement a Quadtree class in JavaScript. This class should be able to store and query for points within a defined rectangular area.

The Quadtree should:

• Initialization: Be initialized with a bounding box representing the total area it covers. This bounding box can be defined by its x, y coordinates (top-left corner) and its width and height.
• Capacity: Have a maximum capacity for the number of points it can hold directly before it needs to subdivide.
• Insertion: Support an insert(point) method to add a point object. A point object should have at least x and y properties.
  • If the current node has not reached its capacity and is not subdivided, the point is stored in this node.
  • If the current node has reached its capacity, it should subdivide into four children quadrants (NorthWest, NorthEast, SouthWest, SouthEast) and redistribute all points (including the new one) into these children.
  • Points that fall exactly on the dividing lines should be handled consistently (e.g., always go to one specific quadrant).
• Querying: Support a query(range) method that takes a rectangular range (similar to the initial bounding box) and returns an array of all points within that range.
• Subdivision Logic: When a node subdivides, its bounding box should be divided into four equal quadrants.

Key Requirements:

• The Quadtree should be able to store multiple points.
• The subdivision process should be recursive.
• The query method should efficiently prune search space by checking if a quadrant's bounding box intersects with the query range.

Edge Cases to Consider:

• Points falling exactly on the boundaries between quadrants.
• Querying an empty quadtree.
• Querying a range that is entirely outside the quadtree's bounding box.
• Inserting points that fall outside the quadtree's initial bounding box (decide how to handle these - for this challenge, assume they are ignored or an error is thrown).

Examples

Example 1:

// Define a bounding box
const boundary = { x: 0, y: 0, width: 100, height: 100 };
const capacity = 4;
const quadtree = new Quadtree(boundary, capacity);

// Insert some points
quadtree.insert({ x: 10, y: 10 });
quadtree.insert({ x: 80, y: 20 });
quadtree.insert({ x: 30, y: 70 });
quadtree.insert({ x: 90, y: 90 });
quadtree.insert({ x: 40, y: 40 }); // This should trigger subdivision

// Query for points in a range
const queryRange = { x: 20, y: 20, width: 60, height: 60 }; // Area from (20,20) to (80,80)
const foundPoints = quadtree.query(queryRange);

console.log(foundPoints);

Output:
[
  { x: 80, y: 20 },
  { x: 30, y: 70 },
  { x: 40, y: 40 }
]
Explanation:
The initial points are inserted. When { x: 40, y: 40 } is inserted, the quadtree with capacity 4 subdivides. The point { x: 10, y: 10 } would go into the SouthWest quadrant. The query range covers points that were in the original tree and potentially in its children after subdivision. The output includes points within the query range.

Example 2:

const boundary = { x: 0, y: 0, width: 200, height: 200 };
const capacity = 1;
const quadtree = new Quadtree(boundary, capacity);

quadtree.insert({ x: 50, y: 50 });
quadtree.insert({ x: 150, y: 50 });
quadtree.insert({ x: 50, y: 150 });
quadtree.insert({ x: 150, y: 150 });
quadtree.insert({ x: 100, y: 100 }); // This insertion will cause extensive subdivision

const queryRange = { x: 90, y: 90, width: 20, height: 20 }; // A small central area
const foundPoints = quadtree.query(queryRange);

console.log(foundPoints);

Output:
[
  { x: 100, y: 100 }
]
Explanation:
With a capacity of 1, each insertion after the first will trigger a subdivision. The point { x: 100, y: 100 } is inserted into the center, and depending on the subdivision logic, it will likely end up in a leaf node that covers a small area around (100, 100). The query range is designed to specifically capture this central point.

Example 3: Edge Case - Querying outside bounds

const boundary = { x: 0, y: 0, width: 100, height: 100 };
const capacity = 4;
const quadtree = new Quadtree(boundary, capacity);

quadtree.insert({ x: 10, y: 10 });

const queryRange = { x: 110, y: 110, width: 20, height: 20 }; // Completely outside
const foundPoints = quadtree.query(queryRange);

console.log(foundPoints);

Output:
[]
Explanation:
The query range is entirely outside the quadtree's bounding box, so no points can possibly be found within it. The query method should correctly return an empty array.

Constraints

• The Quadtree must be implemented as a class named Quadtree.
• The Quadtree constructor will accept an object representing the bounding box and an integer for capacity.
• Points will be objects with x and y properties (numbers).
• Query ranges will be objects with x, y, width, and height properties (numbers).
• Performance is important. The query operation should ideally have a time complexity better than O(N) in most cases, where N is the total number of points.

Notes

• You'll need to define helper methods for subdividing and checking if a point or range intersects with a bounding box.
• Consider how you will represent the children quadrants. You could use an object with properties like northwest, northeast, southwest, southeast, or an array.
• A common approach for point distribution on boundaries is to include them in the quadrant that the boundary belongs to (e.g., points with x = midX always go to the East quadrants).
• Think about the base case for recursion: when a node is a leaf node (has no children) and either has capacity or has reached it and needs to subdivide.