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
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.
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;
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With