如何配对线号在规则网格中制作表面
How to pair line numbers making surfaces in a regular grid
我在 3D space 中有一堆由线连接的点。我想通过检测哪些线可以创建这样的曲面来创建 4 面曲面。
我有点的坐标、编号的线以及创建线的点对。我上传了一张图来形象化它：
它以红色显示点位置及其编号，以蓝色显示线及其编号。我的点分布在规则的 x 和 y 网格中，但是是 3 维的。
对应的数据如下：
coordinates=np.array([[1.,1.,1.], [1.,2.,1.1], [1.,3.,0.9], [1.,4.,1.2],\
[2.,2.,1.2], [2.,3.,1.],[2.,4.,1.1],\
[3.,2.,1.1], [3.,3.,0.95],\
[4.,3.,1.], [4.,4.,1.05]])
y_lines=np.arange(17,24)
point_to_y_lines=[(1,2), (2,3), (3,4), (5,6), (6,7), (8,9), (10,11)]
x_lines=np.arange(24,30)
point_to_x_lines=[(2,5), (3,6), (4,7), (5,8), (6,9), (9,10)]
关于我的绘图：线号 18、25、20 和 24 创建第一个表面。
我正在尝试的算法
要找到曲面，我认为比较线的中心是一种合乎逻辑的方法。我的意思是从行号 17 开始，我想检查哪些线的中心比该线中心的限制更近（中心由黑色十字显示）。
I select 基于 x 坐标分辨率的限制，例如 1.3 看起来不错。只有行号 24 比行中心的限制更近 17。所以 17 无法创建任何曲面。
下一行是行号18，有五行的中心比极限更接近它：17、19、25、20 和 24。 17 应该被忽略，因为它的值小于 18（第一条规则）。 19也应该被忽略，因为它只比18多一个数，其中心的x值与行号18的中心相同（第二条规则）。
那么，行号19的中心附近的中心是18（将被删除，因为它小于19（第一条规则）），26，21 和 25.
下一行是20，很多行的中心比极限更接近它：18（第一条规则，已删除），25，24、21、28、22 和 27。行号 25 和 24 将被忽略，因为它们中心的 x 值小于 20 中心的 x 值（第三条规则)，即我在 x 坐标中前进，不包括传递的 x 坐标。
行号 21 将被删除，因为它是唯一大于 20 的值，并且它的 x 与行号 20 相同（第二条规则）。
由于上述规则，下一行（21、22 和 23，我一直到 y_lines 的最后一行）无法创建任何表面。
期望的输出
表面应作为元组列表输出：
[(18, 25, 20, 24), (19, 26, 21, 25), (20, 28, 22, 27)]
非常感谢在 python 中编写此类算法的任何帮助。
正如评论所说，有很多地方需要说明，所以我的回答可能仍然不是你所需要的。
我对这个问题做了几个假设：
- z 坐标与定位方块无关
- 只有横线和竖线
- 水平线始终将具有较小 x 坐标的点放在第一位，将另一个具有较大 x 坐标的点放在第二位。同样对于垂直线...
- 线不相交，除了它们的端点。
- 要找到的表面总是有 4 个边。
- 一个点最多有4个邻居（北、东、南、西方向）
这道题是一道图题，求4的循环。
我建议构建一个邻接表，其中每个顶点有 4 个按顺时针顺序（北、东、南、西）的邻居引用，其中一些可以是 None。当不是None时，邻居由线号和连接顶点的编号描述。
该算法实际上不需要知道坐标，因为描述线条的数据结构中已经存在大量信息。
这是代码（我省略了numpy）：
y_lines = list(range(17, 24))
point_to_y_lines=[(1,2), (2,3), (3,4), (5,6), (6,7), (8,9), (10,11)]
x_lines = list(range(24,30))
point_to_x_lines=[(2,5), (3,6), (4,7), (5,8), (6,9), (9,10)]
from collections import defaultdict
# Create the empty adjacency list, prepared for lists of 4 entries per vertex
adj = defaultdict(lambda: [None]*4)
# Add vertical lines in the slots for north (0) and south (2)
for line, (a, b) in zip(y_lines, point_to_y_lines):
adj[a][0] = (line, b)
adj[b][2] = (line, a) # also store the line in opposite direction
# Add horizontal lines in the slots for east (1) and west (3)
for line, (a, b) in zip(x_lines, point_to_x_lines):
adj[a][1] = (line, b)
adj[b][3] = (line, a)
# Main algorithm: find the rectangles
results = []
for corner in adj: # for each vertex with at least one edge
rect = []
for direction in range(4): # make a 90° turn at each next corner
neighbor = adj[corner][direction]
if not neighbor: # Oops, no line in that direction. Give up.
break
line, corner = neighbor
rect.append(line)
else: # We closed a rectangle
results.append(tuple(rect))
print(results)
我在 3D space 中有一堆由线连接的点。我想通过检测哪些线可以创建这样的曲面来创建 4 面曲面。
我有点的坐标、编号的线以及创建线的点对。我上传了一张图来形象化它：
它以红色显示点位置及其编号，以蓝色显示线及其编号。我的点分布在规则的 x 和 y 网格中，但是是 3 维的。
对应的数据如下：
coordinates=np.array([[1.,1.,1.], [1.,2.,1.1], [1.,3.,0.9], [1.,4.,1.2],\
[2.,2.,1.2], [2.,3.,1.],[2.,4.,1.1],\
[3.,2.,1.1], [3.,3.,0.95],\
[4.,3.,1.], [4.,4.,1.05]])
y_lines=np.arange(17,24)
point_to_y_lines=[(1,2), (2,3), (3,4), (5,6), (6,7), (8,9), (10,11)]
x_lines=np.arange(24,30)
point_to_x_lines=[(2,5), (3,6), (4,7), (5,8), (6,9), (9,10)]
关于我的绘图：线号 18、25、20 和 24 创建第一个表面。
我正在尝试的算法
要找到曲面，我认为比较线的中心是一种合乎逻辑的方法。我的意思是从行号 17 开始，我想检查哪些线的中心比该线中心的限制更近（中心由黑色十字显示）。
I select 基于 x 坐标分辨率的限制，例如 1.3 看起来不错。只有行号 24 比行中心的限制更近 17。所以 17 无法创建任何曲面。
下一行是行号18，有五行的中心比极限更接近它：17、19、25、20 和 24。 17 应该被忽略，因为它的值小于 18（第一条规则）。 19也应该被忽略，因为它只比18多一个数，其中心的x值与行号18的中心相同（第二条规则）。
那么，行号19的中心附近的中心是18（将被删除，因为它小于19（第一条规则）），26，21 和 25.
下一行是20，很多行的中心比极限更接近它：18（第一条规则，已删除），25，24、21、28、22 和 27。行号 25 和 24 将被忽略，因为它们中心的 x 值小于 20 中心的 x 值（第三条规则)，即我在 x 坐标中前进，不包括传递的 x 坐标。
行号 21 将被删除，因为它是唯一大于 20 的值，并且它的 x 与行号 20 相同（第二条规则）。
由于上述规则，下一行（21、22 和 23，我一直到 y_lines 的最后一行）无法创建任何表面。
期望的输出
表面应作为元组列表输出：
[(18, 25, 20, 24), (19, 26, 21, 25), (20, 28, 22, 27)]
非常感谢在 python 中编写此类算法的任何帮助。
正如评论所说，有很多地方需要说明，所以我的回答可能仍然不是你所需要的。
我对这个问题做了几个假设：
- z 坐标与定位方块无关
- 只有横线和竖线
- 水平线始终将具有较小 x 坐标的点放在第一位，将另一个具有较大 x 坐标的点放在第二位。同样对于垂直线...
- 线不相交，除了它们的端点。
- 要找到的表面总是有 4 个边。
- 一个点最多有4个邻居（北、东、南、西方向）
这道题是一道图题，求4的循环。
我建议构建一个邻接表，其中每个顶点有 4 个按顺时针顺序（北、东、南、西）的邻居引用，其中一些可以是 None。当不是None时，邻居由线号和连接顶点的编号描述。
该算法实际上不需要知道坐标，因为描述线条的数据结构中已经存在大量信息。
这是代码（我省略了numpy）：
y_lines = list(range(17, 24))
point_to_y_lines=[(1,2), (2,3), (3,4), (5,6), (6,7), (8,9), (10,11)]
x_lines = list(range(24,30))
point_to_x_lines=[(2,5), (3,6), (4,7), (5,8), (6,9), (9,10)]
from collections import defaultdict
# Create the empty adjacency list, prepared for lists of 4 entries per vertex
adj = defaultdict(lambda: [None]*4)
# Add vertical lines in the slots for north (0) and south (2)
for line, (a, b) in zip(y_lines, point_to_y_lines):
adj[a][0] = (line, b)
adj[b][2] = (line, a) # also store the line in opposite direction
# Add horizontal lines in the slots for east (1) and west (3)
for line, (a, b) in zip(x_lines, point_to_x_lines):
adj[a][1] = (line, b)
adj[b][3] = (line, a)
# Main algorithm: find the rectangles
results = []
for corner in adj: # for each vertex with at least one edge
rect = []
for direction in range(4): # make a 90° turn at each next corner
neighbor = adj[corner][direction]
if not neighbor: # Oops, no line in that direction. Give up.
break
line, corner = neighbor
rect.append(line)
else: # We closed a rectangle
results.append(tuple(rect))
print(results)