math - 确定一组点是否位于规则网格上

Question

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

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

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

Answer 1

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

附言我会留下这个作为评论，但我的代表太低了..