问题：假设你已经在2D平面的点的集合。我想知道这组点是否位于规则网格上（如果它们是二维网格的子集）。我想就如何做到这一点的想法。确定是否一组点位于一个规则的网格
现在让我们假设我只关心这些点是否构成一个轴对齐的矩形网格（即下面的网格是矩形的，与x和y轴对齐），并且它是一个完整的矩形（格子的子集具有无孔的矩形边界）。任何解决方案都必须非常有效（比O（N^2）更好），因为N可以是数十万甚至数百万。
上下文：我写了一个2D矢量场绘图发生器，用于任意采样的矢量场。如果采样是在一个规则的网格上，那么可以使用更简单/更高效的插值方案来生成图，我想知道什么时候可以使用这种特殊情况。这个特例足够好，它值得这样做。该程序是用C写
不太清楚，如果这是你之后，但对于2D点的飞机上收集什么，你可以做他们的矩形网格（到你点的精度反正） ，问题可能是它们适合的网格可能太稀少了，以便为算法提供任何好处。
找到一个适合一组点的矩形网格，你基本上需要找到所有x坐标的GCD和所有y坐标的原点在xmin，ymin的GCD，这应该是O（n（log n）^ 2）我想。
你怎么决定，如果这个格是那么过于稀疏并不清楚不过
如果点全部来自交叉口只来对电网那么你的点的集合的hough transform可能会帮助您。如果发现线的两条相互垂直的集发生次数最多（意味着你在theta的四个值找到峰隔开所有90度），你会发现在重复伽马空间峰那么你有一个网格。否则不是。
假设网格由方向Or（0到90度内）和分辨率Res定义。你可以计算一个成本函数来评估一个网格(Or, Res)是否坚持你的观点。例如，您可以计算每个点到网格最近点的平均距离。
你的问题，然后找到（或RES）对，最小化成本函数。为了缩小搜索空间并改善搜索空间，可以使用一些启发式来测试“好”候选网格。
该方法是一样的在霍夫使用的一个变换提出jilles。 （或Res）空间与霍夫的伽玛空间相当。
下面是一个在O（ND log N）中工作的解决方案，其中N是点数，D是维数（在您的案例中为2）。
则点是在规则的矩形网格。
我知道这个问题已经过时了，但我正在研究完全相同的问题（从采样点插入矢量场），并想知道是否有更好的解决方案。 – 2015-10-02 22:44:34
这可能是愚蠢的，但如果你的点位于规则网格上，那么坐标的傅里叶变换中的峰值都不是网格分辨率的精确倍数？你可以做一个单独的傅立叶变换的X和Y坐标。如果网格上没有漏洞，那么FT就会成为我认为的delta函数。 FFT是O（nlog（n））。
p.s.我会留下这个评论，但我的代表太低..
让我更好地理解你的问题：你假设你的格基础向量？他们有相同的长度吗？它们是正交的吗？他们是“（1,0）”还是“（0,1）”？ – 2010-07-21 21:10:21