获取离给定点最近的网格点

Question

获取离给定点最近的网格点

6

我有一个一维网格，其间距是一个浮点数。我有一个带有浮点坐标的点。我需要找到它到最近网格点的距离。
例如：

            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;

这个方法可行，但我相信有一种不需要循环的方式。

- Daniel

在他的例子中，它是线性的。 - GWW

@MooingDuck：它是线性的，只是不是常数（它是参数）。 - Daniel

5个回答

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

[编辑] 我感到有些愚蠢。你说间距不是固定的，我理解为不是线性的。但是你的示例代码确实是线性的，只是不是编译时常量。我的错。尽管你的（线性）问题可以更快地解决，但我将保留这个答案作为更一般的解决方案。

- Mooing Duck

调用内部间距是恒定的，调用之间的间距不是恒定的... - Daniel

2

以下是我初步尝试的翻译，注意这还没有经过测试。

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;

- Craig H

在他对你的回答的评论中，他说它在调用内是常量。 - Craig H

@MooingDuck：他说它不是常量。 - GWW

@MooingDuck：我没有说它不是线性的，我只是说它不总是0.1（这是一个参数）。 - Daniel

@Dani：我误解了评论。我的错。 - Mooing Duck

0

更普遍地说，对于任意间距、尺寸和距离度量（度量），您要查找的结构将是 Voronoi 图。

- Phil Miller

0

你可以使用以下代码来对数字进行四舍五入：

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

- slartibartfast

@Dani：我解释了如何使用非常数间距完成它。 - Mooing Duck

floor和ceiling会将数字四舍五入到最接近的整数，而不是最接近的步长值。 - Craig H

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- petrichor · Accepted Answer

首先，我们可以按照以下方式计算左右最近的点：

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;