Изменения

Преобразуем предыдущий алгоритмРассмотрим подробнее последние две части Есть два случая. Мы двигаемся по отрезку слева направо*'''Простой''' {{---}} отрезок не пересекает ни одного трапецоида, то есть целиком внутри. Как только отрезок добавил очередной  Тогда удаляем этот старый трапецоид интиализируем новыйи на его место ставим дерево из двух концов отрезка, отрезка и четырех образовавшихся трапецоидов. Важно не забыть правильно определить соседей новых трапецоидов. В случае, если какие-то трапецоиды выродятся в треугольники, будет не четыре новых трапецоида, а 2 или 3. Как только появляется еще *Находим множество трапецоидов, которых пересек отрезок (в данном случаи он один сохраняем новый ).*Находим этот трапецоид в <tex> T </tex> и добавили вместо него нужные трапецоиды.*Спускаемся по <tex> D </tex> до соответвствующего трапецоида.*Вместо этого трапецоида добавляем ключ "x" и строим от туда часть структуры как показано на картинке.   *'''Сложный''' {{---}} отрезок пересекает сразу несколько трапецоидов. Итак наш отрезок пересекает трапецоиды <tex>\Delta_0, \Delta_1, \Delta_2 ... \Delta_k</tex>. Сначала добавляем вертикальные лучи из концов текущего отрезка. Это нужно, чтобы модифицировать <tex>\Delta_0</tex> и <tex>\Delta_k</tex>.Теперь мы должны удалить соответствующие листья и инициализируем следующийна их место поставить те новые, которые появились из-за изменения лучей. То есть  Дальше мы модифицуруем вертикальные лучи, которые пересекают текущий отрезок. Этот процесс происходит достаточно быстро, так мы храним много информацию об этих лучах.  <tex>\Delta_0, \Delta_1, \Delta_2 \ldots \Delta_k</tex>.*Находим множество трапецоидов, которых пересек отрезок.*Находим этот трапецоид в процессе поиска <tex> T </tex> и добавили вместо него нужные трапецоиды.*Спускаемся по <tex> D </tex> до соответвствующих трапецоидов преобразуем структуру.*Вместо них добавляем новые ключи как показано на картинке.