Группировка линий с учетом пересечений каждой линии с использованием Python

Question

Есть 5 строк.Я хочу сгруппировать их, учитывая, пересекаются они или нет, ограничив двумя конечными точками каждой линии.

Я хочу получить логику для любой из линий, не ограничиваясь данным сценарием. Массив из 5 линий (координаты конечных точек).

lines_all = [[(1, 10), (5, 10)],[(3, 5), (5, 5)],[(3, 10), (3, 13)],[(5,10),(5,13)],[(3,13),(4,13)]]

Тогда, наконец, я хочу получить следующий список массивов.

result = [[[(1, 10), (5, 10)], [(3, 10), (3, 13)],[(3, 13), (4, 13)]], [[(1, 10), (5, 10)], [(5, 10), (5, 13)]],[(3, 5), (5, 5)]]

Answer 1

Чтобы найти все пересечения отрезков, вы можете использовать Алгоритм Бентли-Оттмана .

Произвольно найдено Реализация Python