Изменения

Это только идейные реализации идеи, в коде все выглядет пример выглядит примерно в 50 раз хуже.(по количеству строк)

struct Trapezoid Trapezoid next Trapezoid up Trapezoid down Trapezoid end Segment top Segment bottom Point left Point right

TrapezoidMap(S - segments)  Строим оболочку(просто находим крайние точки множества отрезков по четырем направлениям) Строим рандомную перестановку отрезков

ищем множество трапецоидов пересекаемых отрезком <tex>s_i</tex>. //это специальная функция// Удаляем это множество из карты и добавляем новые узлы появившиеся из-за <tex>s_i</tex> в поисковой структуре Аналогично для просто карты

LookforTrapezoid(<tex>s_i</tex> - segment)  Запоминаем левый и правый конец <tex>s_i</tex> Делаем запрос на левый конец в карте. j <tex>\leftarrow</tex> 0; while q <tex>\in</tex> правый от rightp(трапецоид_j) do if rightp(трапецоид_j) над <tex>s_i</tex> then ставим трапецоид_(j+1) нижним правым соседом трапецоид_j. else ставим трапецоид_(j+1) верхним правым соседом трапецоид_j. j <tex>\leftarrow</tex> j+1