Take the 2-minute tour ×

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        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

-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

share|improve this question
Is the spacing linear? –  GWW Dec 1 '11 at 18:46
In his examples it is linear. –  GWW Dec 1 '11 at 18:56
@MooingDuck: its linear, just not constant (its parameter) –  Dani Dec 1 '11 at 19:00
@GWW: its linear –  Dani Dec 1 '11 at 19:00
add comment

5 Answers

up vote 6 down vote accepted

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;
    distance = rightBorder - point;

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

rightBorder = spacing * ceil(point/spacing);
leftBorder = rightBorder - spacing;
share|improve this answer
Could you please include an explanation of the code? –  N.N. Dec 1 '11 at 20:04
Thanks for the suggestion. I modified the variables to make it self-expressive. Should I add more explanation? –  petrichor Dec 1 '11 at 20:10
An explanation in natural language would only make your answer better so go for it! –  N.N. Dec 1 '11 at 20:11
I added some sentences in the natural language :) –  petrichor Dec 1 '11 at 20:18
add comment
std::vector<float> spacing = ...;
float point = ...;
float result;

Since you say the spacing isn't (linear), I would cache the sums:

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

Then do a binary search to find the point to 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;
        result = *(iter+1) - point;

[EDIT] Don't I feel silly. You said the spacing wasn't constant. I interpreted that as not-linear. But then your sample code is linear, just not a compile-time constant. My bad. I'll leave this answer as a more general solution, though your (linear) question is solvable much faster.

share|improve this answer
The spacing is constant inside invocation, its not constant between invocations... –  Dani Dec 1 '11 at 18:59
add comment

Here is my first blush attempt, note that this is not 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) 

float closest_value = num_spaces*spacing;
float distance = closest_value - point;
share|improve this answer
In his comment to your answer he says it is constant within invocations. –  Craig H Dec 1 '11 at 19:01
@MooingDuck: No he states that it isn't constant. –  GWW Dec 1 '11 at 19:01
@MooingDuck: I didn't state its not linear, I just state its not 0.1 always. (its a parameter) –  Dani Dec 1 '11 at 19:01
@Dani: I misinterpreted the comment. My bad. –  Mooing Duck Dec 1 '11 at 19:03
add comment

You should just round the number using this:

float spacing = ...;
float point = ...;
(point > 0.0) ? floor(point + spacing/2) : ceil(point - spacing/2);
share|improve this answer
The spacing isn't constant –  Dani Dec 1 '11 at 18:40
@Dani: I clarified how it can be done with non-constant spacing. –  Mooing Duck Dec 1 '11 at 19:02
floor and ceiling round to the nearest integer, not the nearest step value. –  Craig H Dec 1 '11 at 19:08
add comment

Much, much more generally, for arbitrary spacing, dimensions, and measures of distance (metric), the structure you're looking for would be a Voronoi Diagram.

share|improve this answer
add comment

Your Answer


