Implementing a Quadtree for Spatial Data Management

Quadtrees are hierarchical data structures used to partition a two-dimensional space into four equal quadrants. They are incredibly useful for spatial indexing, collision detection, and efficient searching of data points within a defined region. This challenge asks you to implement a basic Quadtree in JavaScript, focusing on insertion, subdivision, and querying.

Problem Description

You are tasked with creating a Quadtree class in JavaScript. The Quadtree should represent a rectangular region of space and be able to store points within that region. The tree should subdivide itself into four quadrants (northwest, northeast, southwest, and southeast) when it becomes "full" (defined by a maximum capacity). You need to implement the following methods:

• constructor(x, y, width, height, capacity): Initializes the Quadtree with a given rectangular boundary (defined by top-left corner x, y and width, height) and a capacity which determines the maximum number of points a node can hold before subdividing.
• insert(point): Attempts to insert a given point (represented as an object with x and y properties) into the Quadtree. If the point lies within the Quadtree's boundary and the node has capacity, the point is added. Otherwise, the point is ignored.
• queryRange(x, y, width, height): Returns an array of all points within the given rectangular range (defined by top-left corner x, y and width, height) that are contained within the Quadtree.
• getSubdivisions(): Returns an array containing the four sub-quadrants (NW, NE, SW, SE) as Quadtree objects. Returns an empty array if the node is not subdivided.

Examples

Example 1:

Input:
let qt = new Quadtree(0, 0, 100, 100, 2);
qt.insert({x: 10, y: 20});
qt.insert({x: 30, y: 40});
qt.insert({x: 50, y: 60}); // Node will subdivide
let results = qt.queryRange(20, 30, 40, 50);
Output:
[{x: 10, y: 20}, {x: 30, y: 40}]
Explanation: The query range overlaps with the points inserted. The node subdivided, so the points are distributed among the quadrants.

Example 2:

Input:
let qt = new Quadtree(0, 0, 50, 50, 1);
qt.insert({x: 10, y: 10});
let results = qt.queryRange(60, 60, 20, 20);
Output:
[]
Explanation: The query range is completely outside the Quadtree's boundary, so no points are returned.

Example 3: (Edge Case - Point outside boundary)

Input:
let qt = new Quadtree(0, 0, 100, 100, 2);
qt.insert({x: 110, y: 120}); // Point outside boundary
let results = qt.queryRange(0, 0, 100, 100);
Output:
[]
Explanation: The point is outside the Quadtree's boundary and is therefore not inserted, so the query returns an empty array.

Constraints

• x, y, width, and height will be non-negative numbers.
• capacity will be a positive integer.
• Point x and y coordinates will be numbers.
• The Quadtree should subdivide when the number of points exceeds the capacity.
• The queryRange method should return an array of points in no particular order.
• Performance: Insertion and querying should be reasonably efficient, considering the hierarchical nature of the Quadtree. Avoid excessive recursion.

Notes

• Consider how to define the boundaries of the four sub-quadrants when a node subdivides.
• Think about how to handle points that fall on the boundaries between quadrants. You can choose to assign them to any of the adjacent quadrants.
• You don't need to implement deletion functionality for this challenge.
• Focus on the core functionality of insertion, subdivision, and querying.
• The getSubdivisions() method is primarily for testing and understanding the structure of the Quadtree. It's not strictly required for the core functionality.
• Consider using helper functions to encapsulate logic like checking if a point is within the Quadtree's bounds or if a range overlaps with the Quadtree's bounds.