如何消除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

更新：

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

Google colab link 用于代码，以防您在安装库时遇到任何错误。 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.

完成的

Answer 2

这是一个更简单的答案，它捕获所有线段（正交或非正交）并且只需要一个常用的包，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]

输出：

print(segments)

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

如何消除python中的重叠线？

How to eliminate overlapping lines in python?

python

algorithm

svg

coordinates

path-finding

更新

更新：

以前的方法，

我按照以下方式进行了处理，

输出：

解释：