Изменения

Если идти по отрезку слева направо, то как только отрезок пересек очередное вертикальное дополнение новый трапецоид левее этого дополнения заканчивается и больше изменяться не будет. Мы можем сразу поменять структуру.

Таким образом, сложный случай сводится к простому.

Совместим update и алгоритм поиска новых трапецоидов.

Находим первый трапецоид, в который попал новый отрезок.

Находим первый трапецоид <tex>\Delta_{0}</tex>

<tex>\Delta_{temp}</tex>

while q справа от rightp(<tex>\Delta_{0}</tex>)

Модифицируем <tex>\Delta_{0}</tex>

==Случай коллизии==