Find the maximum number of lines that do not overlap

Question

How can I select the maximum line with having their coordinates so that they do not overlap?

For example, in the example below, we have three lines that you can see their first and last coordinates.

The order of the numbers you receive is in the form is x1 , y1 , x2 , y2)

And if we draw their coordinates, we realize that we have two vertical lines and one horizontal line, and it is better to choose the same two intentional lines because they do not overlap with that horizontal line.

so the result is = 2 (Because it was the maximum number of lines that we could choose)

could you write the python code?

Lukas Hestermeyer · Answer 1 · 2022-12-06T13:11:49.030

I would consider this an optimization problem and look into respective algorithms to solve it.

The most simple, but really ineffective variant would be brute force. Basically iterating over all lines and seeing which I can take with the line together without creating an overlap. Then you simply need to remember the max combination.

One improvement of this would be to store which lines overlap each other whilst iterating so that you dont need to try them out anymore.

If you want to be more fancy, I would look for optimization algorithms; potentially the knapsack problem is somewhat similar and gives a good starting point.

Here is some python code to get you started.

list_of_lines = [
    [4, 5, 9, 5],
    [7, 2, 7, 12],
    [9, 4, 9, 5]
]

    
# see https://stackoverflow.com/a/9997374/5240684
def ccw(A,B,C):
    return (C.y-A.y) * (B.x-A.x) > (B.y-A.y) * (C.x-A.x)

# Return true if line segments AB and CD intersect
def intersect(A,B,C,D):
    return ccw(A,C,D) != ccw(B,C,D) and ccw(A,B,C) != ccw(A,B,D)

class Point(object):
    def __init__(self, x,y):
        self.x = x
        self.y = y

class Line(object):
    def __init__(self, a: Point, b: Point):
        self.a = a
        self.b = b
    def intersects(self, line):
        return intersect(self.a, self.b, line.a, line.b)

n = 0
for i, line in enumerate(list_of_lines):
    a = Point(line[0],line[1])
    line1 = Line(a, Point(line[2],line[3]))
    
    for j in range(i+1, len(list_of_lines)):
        _l = list_of_lines[j]
        line2 = Line(Point(_l[0],_l[1]), Point(_l[2],_l[3]))
        
        if not line1.intersects(line2):
            n += 1
        
n
# returns 2

Note, that this code might have an issue, when the first line is not part of the solution. I have not checked this in detail, but I guess its a starting point anyways.

@5240684 thank you so much. Could you tell me what ```ccw``` does? @lukas-hestermeyer – — natasha, Dec 06 '22 at 17:26
There is a link above where the function was created. Please consider reading that. — Lukas Hestermeyer, Dec 08 '22 at 05:04
On another note: of this answer helped you out, please consider up voting or accepting the answer — Lukas Hestermeyer, Dec 08 '22 at 05:04

score 0 · Answer 2 · answered Dec 06 '22 at 15:28

If you have thousands of lines and if the typical line is short relative to the total space occupied by lines, then you you will be able to drastically reduce the time taking by checking every possible pair of lines by using a quad tree ( https://en.wikipedia.org/wiki/Quadtree ) and only checking lines that occupy the the same quadrant.

Find the maximum number of lines that do not overlap

2 Answers2