Round Coordinates to the closest coordinate in a list

Question

My problem is that i am retrieving the mouses coordinates when the user of my program clicks the screen and i want to be able to round these coordinates to the nearest coordinate in an already defined list of coordinates(in this case its a list of all the centre points of a grid of shapes)

The grid of shapes is a grid of hexagons, the centre points of which are 30 pixels away from each other in the x axis and 30 in the y axis.

How would i round my mouses coordinates to the nearest centre point of the hexagons? Thanks

Answer 1

If the integers in the list are randomly placed, then you will have to conduct a binary search for the correct coordinates.

Otherwise, if the difference between consecutive integers is constant (like a grid), then you can use the / (division operator) to find the correct position.

Eg, if list = [0, 2, 4, 6, 8, 10] and coord = 4.5,
     index ~ int(coord / diff) = 2.

Answer 2

It sounds like a kd-tree would help you here:

The k-d tree is a binary tree in which every node is a k-dimensional point. Every non-leaf node can be thought of as implicitly generating a splitting hyperplane that divides the space into two parts, known as half-spaces. Points to the left of this hyperplane are represented by the left subtree of that node and points right of the hyperplane are represented by the right subtree. The hyperplane direction is chosen in the following way: every node in the tree is associated with one of the k-dimensions, with the hyperplane perpendicular to that dimension's axis. So, for example, if for a particular split the "x" axis is chosen, all points in the subtree with a smaller "x" value than the node will appear in the left subtree and all points with larger "x" value will be in the right subtree. In such a case, the hyperplane would be set by the x-value of the point, and its normal would be the unit x-axis.

And, to find the nearest neighbour:

Searching for a nearest neighbour in a k-d tree proceeds as follows:

1. Starting with the root node, the algorithm moves down the tree recursively, in the same way that it would if the search point were being inserted (i.e. it goes left or right depending on whether the point is less than or greater than the current node in the split dimension).
2. Once the algorithm reaches a leaf node, it saves that node point as the "current best"
3. The algorithm unwinds the recursion of the tree, performing the following steps at each node:
   1. If the current node is closer than the current best, then it becomes the current best.
   2. The algorithm checks whether there could be any points on the other side of the splitting plane that are closer to the search point than the current best. In concept, this is done by intersecting the splitting hyperplane with a hypersphere around the search point that has a radius equal to the current nearest distance. Since the hyperplanes are all axis-aligned this is implemented as a simple comparison to see whether the difference between the splitting coordinate of the search point and current node is less than the distance (overall coordinates) from the search point to the current best.
      1. If the hypersphere crosses the plane, there could be nearer points on the other side of the plane, so the algorithm must move down the other branch of the tree from the current node looking for closer points, following the same recursive process as the entire search.
      2. If the hypersphere doesn't intersect the splitting plane, then the algorithm continues walking up the tree, and the entire branch on the other side of that node is eliminated.
4. When the algorithm finishes this process for the root node, then the search is complete.

Answer 3

Iterate through the list and calculate the distance from your point to every point in the list. The distance is sqrt(sqr(x_mouse - x(i)) + sqr(y_mouse - y(i))). While iterating save the minimal calculated distance and the corresponding coordinate.