确定一组点是否位于规则网格上
问题：假设您在 2D 平面上有一组点。我想知道这组点是否位于规则网格上（如果它们是二维晶格的子集）。我想要一些关于如何做到这一点的想法。
现在，假设我只对这些点是否形成一个轴对齐的矩形网格（底层网格是矩形，与 x 和 y 轴对齐）感兴趣，并且它是一个完整的矩形（晶格有一个没有孔的矩形边界）。任何解决方案都必须非常有效（优于 O(N^2)），因为 N 可以是数十万或数百万。
上下文：我编写了一个 2D 矢量场图生成器，适用于任意采样的矢量场。如果采样在规则网格上，则有更简单/更有效的插值方案来生成绘图，我想知道何时可以使用这种特殊情况。特殊情况足够好，值得这样做。该程序是用 C 编写的。
Problem: Suppose you have a collection of points in the 2D plane. I want to know if this set of points sits on a regular grid (if they are a subset of a 2D lattice). I would like some ideas on how to do this.
For now, let's say I'm only interested in whether these points form an axis-aligned rectangular grid (that the underlying lattice is rectangular, aligned with the x and y axes), and that it is a complete rectangle (the subset of the lattice has a rectangular boundary with no holes). Any solutions must be quite efficient (better than O(N^2)), since N can be hundreds of thousands or millions.
Context: I wrote a 2D vector field plot generator which works for an arbitrarily sampled vector field. In the case that the sampling is on a regular grid, there are simpler/more efficient interpolation schemes for generating the plot, and I would like to know when I can use this special case. The special case is sufficiently better that it merits doing. The program is written in C.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
这可能很愚蠢，但是如果您的点位于规则网格上，那么坐标的傅立叶变换中的峰值不是都是网格分辨率的精确倍数吗？您可以对 X 和 Y 坐标进行单独的傅立叶变换。如果网格上没有洞，那么我认为 FT 将是一个 delta 函数。 FFT 的复杂度为 O(nlog(n))。
ps 我本来可以将此作为评论，但我的代表太低了..
This might be dumb but if your points were to lie on a regular grid, then wouldn't peaks in the Fourier transform of the coordinates all be exact multiples of the grid resolution? You could do a separate Fourier transform the X and Y coordinates. If theres no holes on grid then the FT would be a delta function I think. FFT is O(nlog(n)).
p.s. I would have left this as a comment but my rep is too low..
不太确定这是否是您想要的，但是对于平面上的二维点的集合，您始终可以将它们安装在矩形网格上（无论如何都可以达到点的精度），问题可能是它们适合的网格可能点的填充太稀疏，无法为您的算法提供任何好处。
要找到适合一组点的矩形网格，您基本上需要找到所有点的 GCD x 坐标和所有以 xmin,ymin 为原点的 y 坐标的 GCD 我认为这应该是 O( n (log n)^2) 。
然而，如何判断该网格是否太稀疏尚不清楚
Not quite sure if this is what you are after but for a collection of 2d points on a plane you can always fit them on a rectangular grid (down to the precision of your points anyway), the problem may be the grid they fit to may be too sparsly populated by the points to provide any benefit to your algorithm.
to find a rectangular grid that fits a set of points you essentially need to find the GCD of all the x coordinates and the GCD of all the y coordinates with the origin at xmin,ymin this should be O( n (log n)^2) I think.
How you decide if this grid is then too sparse is not clear however
如果所有点仅来自网格上的交点，则 霍夫变换你的一组观点可能对你有帮助。如果您发现两组相互垂直的线最常出现（这意味着您在四个 θ 值均相距 90 度处找到峰值）并且在伽玛空间中发现重复峰值，那么您就有了一个网格。否则不会。
If the points all come only from intersections on the grid then the hough transform of your set of points might help you. If you find that two mutually perpendicular sets of lines occur most often (meaning you find peaks at four values of theta all 90 degrees apart) and you find repeating peaks in gamma space then you have a grid. Otherwise not.
这是一个适用于 O(ND log N) 的解决方案，其中 N 是点数，D 是维度数（在您的情况下为 2）。
则这些点位于规则的矩形网格中。
Here's a solution that works in O(ND log N), where N is the number of points and D is the number of dimensions (2 in your case).
then the points are in a regular rectangular grid.
假设网格由方向
Or（0 到 90 度范围内）和分辨率Res定义。您可以计算一个成本函数来评估网格（Or，Res）是否坚持您的点。例如，您可以计算每个点到网格中最近点的平均距离。那么你的问题是找到最小化成本函数的 (Or, Res) 对。为了缩小搜索空间并改进 ，可以使用一些启发式方法来测试“好的”候选网格。
这种方法与 jilles 提出的霍夫变换中使用的方法相同。 (Or, Res) 空间与霍夫伽马空间相当。
Let's say a grid is defined by an orientation
Or(within 0 and 90 deg) and a resolutionRes. You could compute a cost function that evaluate if a grid(Or, Res)sticks to your points. For example, you could compute the average distance of each point to its closest point of the grid.Your problem is then to find the (Or, Res) pair that minimize the cost function. In order to narrow the search space and improve the , some a heuristic to test "good" candidate grids could be used.
This approach is the same as the one used in the Hough transform proposed by jilles. The (Or, Res) space is comparable to the Hough's gamma space.