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

Question

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

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

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

Answer 1

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

ps我会把它留作评论，但我的代表太低了..