How to eliminate overlapping lines in python?

Question

I have a list of lists of coordinates, each representing a path segment in an SVG path defined by two points, such that [x1, y1, x2, y2]. In some cases there will be smaller segments that are fully overlapped by another one in the list.

Here is a simplified example:

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

Represents segments in the following path, respectively:

In this case, the first segment is fully overlapped by the last one and therefore segments[0] should be removed as it is inside segments[4]. A path can exceed 8,000 segments. What would be the most efficient way of eliminating the smaller overlapping segments?

UPDATE

These additional conditions further define this problem:

• Segments do not necessarily need to be along the x or y axes as in the example (i.e., a segment such as [1, 1, 2, 2] is also possible).
• If there is only a partial overlap (e.g., as would be seen between a pair of segments [3, 1, 1, 1] and [2, 1, 4, 1]), no segment is removed.

Answer 1

This is a simpler answer that captures all segments (orthogonal or not) and requires only a commonly accessible package, NumPy (and some basic geometry knowledge):

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]

OUTPUT:

print(segments)

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