如何消除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]内。一条路径可以超过8000段。消除较小重叠段的最有效方法是什么？

更新

这些附加条件进一步定义了这个问题：

• 段不一定需要像示例中那样沿着x或{}轴（即，也可以是[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 determines if segment between coordinates 1 & 2 completely overlaps
# the segment between coordinates 3 & 4
def completelyOverlaps(x1, x2, x3, x4):
    return (x1 <= x3 and x1 <= x4 and x2 >= x3 and x2 >= x4) or \
        (x2 <= x3 and x2 <= x4 and x1 >= x3 and x1 >= x4)

overlapped = []
for i in range(len(segments)):
    for j in range(i+1, len(segments)):
        [x1, y1, x2, y2] = segments[i]
        [x3, y3, x4, y4] = segments[j]
        # Checks whether the cross product between two different pairs of points
        # are both == 0, which means that the segments are both on the same line
        if 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:
            # If lines are vertical, consider the y-coordinates
            if x1 == x2:
                # If 1st segment fully overlaps 2nd, add latter to the list
                if completelyOverlaps(y1, y2, y3, y4):
                    overlapped.append(segments[j])
                # If 2nd segment fully overlaps 1st, add latter to the list
                elif completelyOverlaps(y3, y4, y1, y2):
                    overlapped.append(segments[i])
            # In all other cases, consider the x-coordinates
            else:
                if completelyOverlaps(x1, x2, x3, x4):
                    overlapped.append(segments[j])
                elif completelyOverlaps(x3, x4, x1, x2):
                    overlapped.append(segments[i])

segments = [s for s in segments if s not in overlapped]

输出：

^{pr2}$

Answer 2

更新：

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

谷歌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)

输出：

^{pr2}$

以前的方法

仅适用于与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)

输出：

^{4}$

说明：

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坐标是否重叠，因为坐标的顺序可能是相反的，所以我们必须把它们向前推进以便我们进行解释， e、 g：从3到1的坐标等于1到3。 这是通过从列表中查找最小值和最大值的简单操作完成的。在

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