Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Getting closest point on grid to point

I have a one dimensional gird. its spacing is a floating point. I have a point with floating point coordinate as well. I need to find its distance to the closest grid point.
For example:

            0.12
             |
             *
 |---------|---------|---------|---------|---------|
 0        0.1       0.2       0.3       0.4       0.5

The result would be -0.02 since the closest point is behind it.
However if it was

                -0.66
                  |
                  *
 |---------|---------|---------|---------|---------|
-1       -0.8      -0.6      -0.4      -0.2        0

The result will be 0.06. As you can see its in floating point and can be negative.
I tried the following:

float spacing = ...;
float point = ...;

while(point >= spacing) point -= spacing;
while(point < 0) point += spacing;

if(std::abs(point - spacing) < point) point -= spacing;

It works, but I'm sure there is a way without loops

like image 232
Dani Avatar asked Dec 01 '11 18:12

Dani


People also ask

How do you find the closest point to a set of points?

The idea is to split the point set into two halves with a vertical line, find the closest pair within each half, and then find the closest pair between the two halves. The result of finding the closest pair within each half speeds up finding the closest pair between the halves.


1 Answers

Let us first compute the nearest points on the left and right as follows:

leftBorder = spacing * floor(point/spacing);
rightBorder = leftBorder + spacing;

Then the distance is straightforward:

if ((point - leftBorder) < (rightBorder - point))
    distance = leftBorder - point;
else
    distance = rightBorder - point;

Note that, we could find the nearest points alternatively by ceiling:

rightBorder = spacing * ceil(point/spacing);
leftBorder = rightBorder - spacing;
like image 145
petrichor Avatar answered Oct 19 '22 20:10

petrichor