4

问题：假设您在 2D 平面中有一组点。我想知道这组点是否位于规则网格上（如果它们是 2D 晶格的子集）。我想要一些关于如何做到这一点的想法。

现在，假设我只对这些点是否形成一个轴对齐的矩形网格（底层格子是矩形的，与 x 和 y 轴对齐）以及它是否是一个完整的矩形（晶格有一个没有孔的矩形边界）。任何解决方案都必须非常有效（优于 O(N^2)），因为 N 可以是数十万或数百万。

背景：我写了一个二维向量场图生成器，它适用于任意采样的向量场。在采样在规则网格上的情况下，有更简单/更有效的插值方案来生成图，我想知道什么时候可以使用这种特殊情况。特殊情况足够好，值得做。该程序是用 C 编写的。

4

5 回答 5

5

这可能很愚蠢，但是如果您的点位于规则网格上，那么坐标的傅立叶变换中的峰值不会都是网格分辨率的精确倍数吗？您可以对 X 和 Y 坐标进行单独的傅立叶变换。如果网格上没有孔，那么我认为 FT 将是一个 delta 函数。FFT 为 O(nlog(n))。

ps 我会将此作为评论，但我的代表太低了..

于 2016-11-14T03:02:07.693 回答
4

不太确定这是否是您所追求的，但是对于平面上的 2d 点的集合，您始终可以将它们放在矩形网格上（无论如何都要精确到点的精度），问题可能是它们适合的网格可能点太少，无法为您的算法提供任何好处。

要找到适合一组点的矩形网格，您基本上需要找到所有 x 坐标的GCD和所有 y 坐标的 GCD，原点位于 xmin,ymin 这应该是 O( n (log n)^2 ） 我认为。

但是，您如何确定该网格是否过于稀疏尚不清楚

于 2010-07-21T08:30:55.713 回答
3

如果这些点都仅来自网格上的交叉点，那么您的一组点的霍夫变换可能会对您有所帮助。如果您发现最常出现两组相互垂直的线（这意味着您在四个相隔 90 度的 theta 值处发现峰值）并且在伽马空间中发现重复峰值，那么您就有了一个网格。否则不行。

于 2010-07-21T08:52:34.493 回答
2

这是一个适用于 O(ND log N) 的解决方案，其中 N 是点数，D 是维度数（在您的情况下为 2）。

  1. 为 N 个数字分配带有空间的 D 数组：X、Y、Z 等（时间：O(ND)）
  2. 遍历您的点列表并将 x 坐标添加到列表 X，将 y 坐标添加到列表 Y 等（时间：O（ND））
  3. 对每个新列表进行排序。（时间：O（ND log N））
  4. 计算每个列表中唯一值的数量，并确保整个列表中连续唯一值之间的差异相同。（时间：O(ND)）
  5. 如果
    • 每个维度中的唯一值是等距的，并且
    • 如果每个坐标的唯一值个数的乘积等于原始点的个数 (length(uniq(X))*length(uniq(Y))* ... == N,

那么这些点在一个规则的矩形网格中。

于 2015-10-02T22:42:51.950 回答
1

假设一个网格由一个方向Or（在 0 和 90 度内）和一个分辨率定义Res。您可以计算一个成本函数来评估网格是否(Or, Res)粘在您的点上。例如，您可以计算每个点到网格中最近点的平均距离。

然后，您的问题是找到最小化成本函数的 (Or, Res) 对。为了缩小搜索空间并提高 ，可以使用一些启发式来测试“好”候选网格。

这种方法与 jilles 提出的 Hough 变换中使用的方法相同。(Or, Res) 空间与霍夫的伽马空间相当。

于 2010-08-13T13:45:34.320 回答