Vector Arrays with efficient searching

[DominicDolan]

Info

Currently there is no way of throwing lots of vectors or coordinates into an array and then be able to search that efficiently and in a helpful way.

Motive

This feature would be useful under scenarios that require dealing with a lot of points or coordinates, these scenarios can be quite common in game development. For example, if there was an array of 1000 points and you wanted to find the point in that array that is closest to (40, 60), the only way to do that would be to look through the entire array one by one with an O(n) efficiency. Another use case is trying to get all the points from the array that are contained in a specific rectangle, this would take even longer using brute force methods. It would be better to have something faster.

Task

Implement a version of the List interface that has all the usual features of a list but it is specific to 2D Vectors and allows fast searching of points and boxes. There is a way of doing this using something called Kd Trees. More information on this can be found in Computational Geometry - Algorithms and Applications by Mark de Berg, assuming you have access to that book