問題：假設你已經在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