如何在常规网格中对线号进行配对以形成曲面 [英] How to pair line numbers making surfaces in a regular grid

问题描述

我在3D空间中有一堆由线连接的点.我想通过检测哪些线可以创建四面曲面来创建此类曲面.

我拥有我的点，编号线以及创建线的点对的坐标.我上传了一个图形以使其可视化:

它以红色显示点位置及其编号，以蓝色显示线及其编号.我的点分布在常规的 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 创建第一个曲面./p>

我正在尝试的算法

要找到曲面，我认为比较线的中心是一种逻辑方法.我的意思是从行号 17 开始，我要检查哪些行的中心比该行的中心的限制近(中心由黑叉显示).

我根据 x 坐标中的分辨率选择限制，例如 1.3 看起来不错.只有行号 24 比行号 17 的中心的限制更近.因此 17 无法创建任何曲面.

下一行是行号 18 ，五行的中心比它的限制更近: 17 ， 19 ， 25 ， 20 和 24 . 17 应该被忽略，因为它的值小于18(第一条规则).也应该忽略 19 ，因为它仅比18多一个数字，并且其中心的 x 值与行号 18 的中心相同code>(第二条规则).

然后，附近的中心到行号 19 的中心为 18 (将被删除，因为它小于19(第一条规则))，26 ， 21 和 25 .

下一行是 20 ，并且许多行的中心都比它的限制更近: 18 (已删除第一条规则)， 25， 24 ， 21 ， 28 ， 22 和 27 .行号 25 和 24 将被忽略，因为其中心的 x 值小于 x 的值 20 的中心(第三条规则)的角度，即我在 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个相邻参考，其中一些可以 None .如果不是 None ，则通过行号和连接的顶点号来描述邻居.

该算法实际上并不需要了解坐标，因为在描述直线的数据结构中已经存在很多信息.

这是代码(我省略了numpy):

  y_lines = list(范围(17，24))point_to_y_lines = [(1,2 ,,(2,3)，(3,4)，(5,6)，(6,7)，(8,9)，(10,11)]x_lines =列表(范围(24,30))point_to_x_lines = [(2,5)，(3,6)，(4,7)，(5,8)，(6,9)，(9,10)]从集合导入defaultdict#创建一个空的邻接列表，为每个顶点包含4个条目的列表做准备adj = defaultdict(lambda:[无] * 4)#在插槽中为北(0)和南(2)添加垂直线对于zip(y_lines，point_to_y_lines)中的(a，b)行:adj [a] [0] =(line，b)adj [b] [2] =(line，a)#也以相反的方向存储线#在插槽中添加水平线以东(1)和西(3)对于zip(x_lines，point_to_x_lines)中的(a，b)行:adj [a] [1] =(line，b)adj [b] [3] =(a行)#主要算法:找到矩形结果= []对于adj中的角:#对于每个至少具有一条边的顶点rect = []对于范围(4)中的方向:#在每个下一个拐角处旋转90°邻居= adj [角落] [方向]如果不是邻居:#糟糕，该方向没有线.放弃.休息线，角=邻居rect.append(行)否则:#我们关闭了一个矩形results.append(tuple(rect))打印(结果) 

I have a bunch of points in 3D space that are connected by lines. I want to create 4-sided surfaces by detecting which lines can create such surfaces.

I have coordinates of my points, numbered lines, and also the point pairs which create lines. I uploaded a drawing to visualize it:

It shows point locations and their numbers in red colour, and lines and their numbers in blue. My points are distributed in a regular x and y grid, but are 3-dimensional.

Here is the corresponding data:

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)]

Regarding my drawing: line numbers 18, 25, 20 and 24 create the first surface.

The algorithm I am trying with

To find surfaces, I think comparing the center of lines is a logical way. I mean starting from line number 17, I want to check the centers of which lines are closer than a limit to the center of this line (centers are shown by a black cross).

I select the limit based on the resolution in x coordinates, for example 1.3 looks fine. Only line number 24 is closer than the limit to the center of line 17. So 17 cannot create any surfaces.

The next line is line number 18, and centers of five lines are closer than the limit to it: 17, 19, 25, 20 and 24. 17 should be ignored because its value is less than 18 (first rule). 19 also should be ignored because it is only one number more than 18 and the x value of its center is the same as the center of line number 18 (second rule).

Then, the nearby centers to the center of line number 19 are 18 (will be removed because it is less than 19 (first rule)), 26, 21 and 25.

The next line is 20, and the center of lots of lines are closer than the limit to it: 18 (first rule, removed), 25, 24, 21, 28, 22 and 27. Line numbers 25 and 24 will be ignored because the x value of the their centers is less than the x value of the center of 20 (third rule), i.e. I go forward in x coordinates and do not include passed x coordinates.

Line number 21 will be removed because it is the only value more than 20 and its x is the same as line number 20 (second rule).

Next lines (21, 22 and 23, I go until the last line of y_lines) cannot create any surface because of the mentioned rules.

Desired output

The surfaces should be output as a list of tuples:

[(18, 25, 20, 24), (19, 26, 21, 25), (20, 28, 22, 27)]

I do appreciate any help for writing such an algorithm in python.

解决方案

As the comments show, there are a lot of things that need clarification, so my answer could still not be what you need.

I am making several assumptions about the problem:

• The z-coordinate is irrelevant for locating the squares
• There are only horizontal lines and vertical lines
• The horizontal lines are always having the point with the lesser x-coordinate in first place and the other, with a greater x-coordinate in second place. Similarly for the vertical lines...
• Lines do not intersect, except at their endpoints.
• The surfaces to be found always have 4 sides.
• A point has at the most 4 neighbors (in north, east, south, and west directions)

The problem is a graph problem, in which to find cycles of 4.

I propose to build an adjacency list, where each vertex has 4 neighbor references in clock-wise order (north, east, south, west), of which some can be None. When not None, the neighbor is described by a line number and the number of the connected vertex.

This algorithm does not really need to know about the coordinates, as already a lot of information is present in the data structure describing the lines.

Here is the code (I omitted 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)

这篇关于如何在常规网格中对线号进行配对以形成曲面的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！