Getting the closest point on the grid to a point

Question

I have a one-dimensional face. its spacing is a floating point. I have a floating point coordinate. I need to find its distance to the nearest grid point.
For instance:

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

The result will be -0.02 , since the nearest 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 it in a 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; 

This works, but I'm sure there is a loop-free way

Answer 1

First, calculate the nearest points on the left and right as follows:

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

Then the distance is simple:

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

Note that we could find the nearest points alternately with the ceiling:

 rightBorder = spacing * ceil(point/spacing); leftBorder = rightBorder - spacing; 

Answer 2

 std::vector<float> spacing = ...; float point = ...; float result; 

Since you say the interval is not (linear), I will cache the sums:

 std::vector<float> sums(1, 0.0); float sum=0; for(int i=0; i<spacing.size(); ++i) sums.push_back(sum+=spacing[i]); //This only needs doing once. //sums needs to be in increasing order. 

Then do a binary search to find the point on the left:

 std::vector<float>::iterator iter; iter = std::lower_bound(sums.begin(), sums.end(), point); 

Then find the result from there:

 if (iter+1 == sums.end()) return point-*iter; else { float midpoint = (*iter + *(iter+1))/2; if (point < midpoint) result = point - *iter; else result = *(iter+1) - point; } 

[EDIT] Don't feel stupid. You said that the distance was not constant. I interpreted this as non-linear. But then your code sample is linear, not a compile-time constant. To blame. I will leave this answer as a more general solution, although your (linear) question will resolve much faster.

Answer 3

Here is my first attempt to blush, note that this has not been tested at all.

 float remainder = fmod(point, spacing); // This is the fractional difference of the spaces int num_spaces = point/spacing; // This is the number of "spaces" down you are, rounded down // If our fractional part is greater than half of the space length, increase the number of spaces. // Not sure what you want to do when the point is equidistant to both grid points if(remainder > .5 * spacing) { ++num_spaces; } float closest_value = num_spaces*spacing; float distance = closest_value - point; 

Answer 4

You should simply round the number using this:

 float spacing = ...; float point = ...; (point > 0.0) ? floor(point + spacing/2) : ceil(point - spacing/2); 

Answer 5

In a much larger sense, for arbitrary distance, dimensions, and distance measures (metrics), the structure you are looking for would be a Voronoi diagram.