1

想象一条通过原点的直线。由于旋转和反射很容易，假设斜率在 0 到 1 的范围内。我们在笛卡尔平面上有一个整数点网格。我想找到大于 0 和 <= D 的网格点最接近。

简单的方法是对于 1 .. D 中的每个 x，找到直线上方和下方的点并计算到直线的垂直距离。这将需要 2 x D 比较才能找到最小值。

这还不错，但我正在尝试提出一种 log(D) 方法。有吗？

一个等效的问题是找到最接近的有理数 n / d，其中 d <= D。

4

2 回答 2

1

这个问题似乎和你的一样：Finding the nearest integer fraction to a given random real

那里接受的答案使用Farey Sequence。

还链接到这个有趣的博客文章。

于 2013-03-19T00:54:35.380 回答
0

不是一个完整的答案，而是在某些情况下的优化：如果线的斜率是有理数，那么会有重复，如果 D 大于分母，则允许您查看更少的点。

例如：如果斜率为 12/17，那么您不需要从原点向外看超过 17 个点。之后它将重复。

当然，如果在该示例中 D < 17，则没有任何好处。

另外，如果你的斜率是π，那么你就不走运了......

于 2013-03-19T00:40:37.560 回答