如何消除python中的重叠线？

Question

我有一个坐标列表列表，每个坐标列表代表SVG路径中由两个点定义的路径段，例如[x1, y1, x2, y2]。在某些情况下，列表中还会有一些较小的细分与其他细分完全重叠。

这里是一个简化的示例：

segments = [[1, 1, 2, 1], [2, 1, 2, 2], [2, 2, 3, 2], [3, 2, 3, 1], [3, 1, 1, 1]]

分别代表以下路径中的段：

在这种情况下，第一个片段与最后一个片段完全重叠，因此应删除segments[0]，因为它位于segments[4]内部。一条路径可以超过8,000个段。 消除较小的重叠段的最有效方法是什么？

更新

这些其他条件进一步定义了此问题：

• 段不一定像示例中那样沿x或y轴（即，也可以是诸如[1, 1, 2, 2]之类的段）。
• [如果只有部分重叠（例如，在一对线段[3, 1, 1, 1]和[2, 1, 4, 1]之间可以看到），则不会删除任何线段。

Answer 1

这是一个更简单的答案，它捕获所有线段（正交或不正交），只需要一个可普遍访问的包NumPy（和一些基本的几何知识）：

import numpy as np

segments = [[1, 1, 2, 1], [2, 1, 2, 2], [2, 2, 3, 2], [3, 2, 3, 1], [3, 1, 1, 1]]
# Function that checks whether the cross product between the segments' vectors
# and between one of the  segments's points & a point from the other segment are
# both == 0, which means that the segments are both on the same line; returns T/F
def sameLine(segment1, segment2):
    [x1, y1, x2, y2] = segment1
    [x3, y3, x4, y4] = segment2
    return np.cross(np.array([x1-x2, y1-y2]), np.array([x3-x4, y3-y4])) == 0 and \
        np.cross(np.array([x1-x2, y1-y2]), np.array([x3-x1, y3-y1])) == 0
# Function that checks whether one of two segments on the same line is completely
# overlaped by anoother and if so, the shorter one is added to the list of lines
# to be removed
def fullyOverlapped(segment1, segment2, overlapped):
    [x1, y1, x2, y2] = segment1
    [x3, y3, x4, y4] = segment2
    # If lines are vertical, look at the y-coordinates
    if x1 == x2:
        # If the first segment fully overlaps the second, add the latter to the list
        if (y1 <= y3 and y2 >= y4) or ((y2 <= y3 and y1 >= y4)):
            overlapped.append(segment2)
        # If the second segment fully overlaps the first, add the latter to the list
        elif (y1 >= y3 and y2 <= y4) or (y1 >= y3 and y2 <= y4):
            overlapped.append(segment1)
    # In all other cases, look at the x-coordinates
    else:
        if (x1 <= x3 and x2 >= x4) or (x2 <= x3 and x1 >= x4):
            overlapped.append(segment2)
        elif (x1 >= x3 and x2 <= x4) or (x2 >= x3 and x1 <= x4):
            overlapped.append(segment1)

overlapped = []
# Go over pairs of lines (avoiding duplicate checks or checking against oneself)
for i in range(len(segments)):
    for j in range(i+1, len(segments)):
        if sameLine(segments[i], segments[j]):
            fullyOverlapped(segments[i], segments[j], overlapped)
segments = [s for s in segments if s not in overlapped]
print(segments)

输出：

[[1, 1, 2, 1], [2, 1, 2, 2], [2, 2, 3, 2], [3, 2, 3, 1]]

Answer 2

更新：

[这种方法是通过使用库，并且功能齐全，可以解决整个问题，而较旧的方法是使用自定义算法，但没有考虑斜线段。

Google colab代码链接，以防在安装库时出错。https://colab.research.google.com/drive/1tcQ5gps8dQz9kNY93rfAK97hSQPjCvOt

from shapely.geometry import LineString
lines = [[1, 1, 1, 2],[2, 1, 4, 1],[1, 1, 2, 1], [2, 1, 2, 2], [2, 2, 3, 2], [3, 2, 3, 1], [3, 1, 1, 1]]
overlaped_lines = []
for i in lines:
  for j in lines:
    if j == i:
      continue
    if LineString([(i[0],i[1]),(i[2],i[3])]).within(LineString([(j[0],j[1]),(j[2],j[3])])):
      overlaped_lines.append(i)
      break

for i in overlaped_lines:
  lines.remove(i)

print(lines)

输出：

[[1, 1, 1, 2], [2, 1, 4, 1], [2, 1, 2, 2], [2, 2, 3, 2], [3, 2, 3, 1], [3, 1, 1, 1]]

以前的方法，

仅适用于平行于x或y轴的线，不适用于倾斜线。

我已经通过以下方式进行处理，

def find_overlap(lines):
    l = []
    i = 0
    for x1,y1,x2,y2 in lines:
        j=0
        for xx1,yy1,xx2,yy2 in lines:
            if j == i:
                j+=1
                continue
            #Check for lines along x-axis    
            if (y2-y1) == 0 and (yy2-yy1) == 0 and y1 == yy1 and y2 == yy2:
                a,b,c,d = min(xx1,xx2), max(xx1,xx2), min(x1,x2),max(x1,x2)
                if c >= a and d <= b:
                    l.append(lines[i])
                    break
            #Check for lines along y-axis         
            if (x2-x1) == 0 and (xx2-xx1) == 0 and x1 == xx1 and x2 == xx2:
                a,b,c,d = min(yy1,yy2), max(yy1,yy2), min(y1,y2),max(y1,y2)
                if c >= a and d <= b:
                    l.append(lines[i])
                    break   
            j+=1
        i+=1
    return l

def remove_overlap(l,lines):
    for i in l:
        lines.remove(i)
    return lines

lines = [[1, 1, 2, 1], [2, 1, 2, 2],[3, 4, 3, 1], [2, 2, 3, 2], [3, 2, 3, 1], [3, 1, 1, 1]]

l = find_overlap(lines)
lines_after_overlap_removal = remove_overlap(l,lines)

输出：

lines
Out[19]: [[1, 1, 2, 1], [2, 1, 2, 2],[3, 4, 3, 1], [2, 2, 3, 2], [3, 2, 3, 1], [3, 1, 1, 1]]

lines_after_overlap_removal
Out[20]: [[2, 1, 2, 2], [3, 4, 3, 1], [2, 2, 3, 2], [3, 1, 1, 1]]

说明：

1）首先，for循环解析给定列表，让我们考虑i = 0的示例，行[0] = [1，1，2，1]

2）第二个for循环检查沿x和y轴的其他坐标

例如：

[第一个for循环的[1，（y1）1,2，（y2）1]沿着x轴，即与x轴平行，因为y1 = y2。

现在第二个for循环为我带来了元素[2，（yy1）1，2，（yy2）2]，这里y1 == yy1但y2！= yy2

接着继续，最后带来[3，1，1，1]，其中y1 == yy1和y2 == yy2。

现在让我们检查其x坐标是否重叠，因为坐标可能是相反的顺序，我们必须将它们向前推，以便我们进行解释，例如：坐标从3变到1，等于1到3。通过从列表中查找最小值和最大值的简单操作即可完成。

然后检查转发的x1，x2与xx1，xx2，如果它们重叠，则在列表l中记下它。即将其附加到列表l。现在，最后一步将是删除重叠的元素，这由最后一个函数remove_overlap完成。