如何通过网格点生成线段

Question

我正在尝试通过网格生成网格线段 points.I 有 34 个点，如下所示：

图片尺寸为720*480，有34个网格点，坐标在这里：

323.708 205.925
382.585 206.75
320.296 216.596
381.729 217.499
271.118 227.4
286.04 227.643
301.208 227.631
316.538 228.165
332.195 228.323
348.114 228.828
364.194 229.139
380.893 229.356
397.731 230.219
414.795 230.634
432.307 231.407
312.507 241.026
379.886 242.892
307.735 254.944
378.838 257.705
251.514 268.437
268.271 269.035
285.124 269.701
302.801 270.563
320.684 271.637
339.107 272.332
358.067 273.122
377.46 274.347
397.01 275.033
416.814 276.199
437.558 277.354
297.437 288.028
375.766 292.266
291.296 307.268
374.233 313.316

我试过霍夫变换来检测网格线。但我只需要一张点之间的空白被填充的图片（像这样）：

这样我就可以做接下来的工作了。使用霍夫变换有点浪费

我试过使用线性插值来填补空白，但我需要手动找到端点。所以，我想知道如何只用这些网格点自动生成网格线段

Answer 1

你已经知道重点了，所以霍夫变换的开销很大。

如果只有 34 个（甚至数百个）点，它们会形成大约 1000 对，您可以为每一对构建线，然后将这些线聚类为 rho-theta space，无需任何复杂算法（这种方法是二次的）。你将有 4 个大簇，不难从这些簇中找到哪些线段（点）是结束线段。

对于较大的数据集，您可以以随机方式为小的随机点子集形成初始聚类，然后将每个点添加到它适合的最佳直线（线性方法）

Answer 2

为每个点找到 N,S,E,W 方向上最近的点，如果列表中不存在线，则将线添加到列表中。如果 n 是我看到的点数：

循环i = <0,n-2>
循环j = <i+1,n-1>
每个轴方向

添加任何尺寸 |pnt[i1]-pnt[i1]| 小于或等于网格尺寸的线，同时线的方向与实际方向相似 NS 或 WE 所以：
```
abs(dot(direction/|direction|,(pnt[i1]-pnt[i1])/|pnt[i1]-pnt[i1]|))
```
如果方向向量不准确，
接近 1 或至少大于 0.75。您可以从以下方向开始：
```
NS = ( 0.0, 1.0 )
WE = ( 1.0. 0.0 )
```
NS 方向偏差较大，所以您可能应该使用更大的边距进行比较。

您可以去掉单位向量点积内的归一化

如何通过网格点生成线段

How to generate line segments by grid points

algorithm

grid

geometry

gridlines