Получение ближайшей точки на сетке к точке

Question

У меня есть одномерный гирд.его интервал является плавающей точкой.У меня также есть точка с координатой с плавающей точкой.Мне нужно найти расстояние до ближайшей точки сетки.
Например:

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

Результат будет -0.02, так как ближайшая точка находится позади него.
Однако, если бы это было

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

Результат будет 0.06.Как вы можете видеть в плавающей запятой и может быть отрицательным.
Я попробовал следующее:

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

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

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

Это работает, но я уверен, что есть путь без циклов

Answer 1

Давайте сначала вычислим ближайшие точки слева и справа следующим образом:

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

Тогда расстояние просто:

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

Обратите внимание, что мы можем найти ближайшие точки по потолку:

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

Answer 2

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

Поскольку вы говорите, что интервал не является (линейным), я бы кешировал суммы:

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.  

Затем выполните двоичный поиск, чтобы найти точку слева:

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

Затем найдите результат оттуда:

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

[РЕДАКТИРОВАТЬ] Не чувствую себя глупо.Вы сказали, что расстояние не было постоянным.Я интерпретировал это как нелинейный.Но тогда ваш пример кода является линейным, но не константой времени компиляции.Виноват.Я оставлю этот ответ в качестве более общего решения, хотя ваш (линейный) вопрос решается гораздо быстрее.

Answer 3

Вот моя первая попытка покраснеть, обратите внимание, что это совсем не проверено.

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

Гораздо в более общем смысле для произвольного расстояния, размеров и мер расстояния (метрика) искомая структура будет диаграммой Вороного.

Answer 5

Вы должны просто округлить число, используя это:

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