Изменения

Рассмотрим подробнее последние две части Есть два случаяПреобразуем предыдущий алгоритм.*'''Простой''' {{---}} Мы двигаемся по отрезку слева направо. Как только отрезок не пересекает ни одного трапецоида, то есть целиком внутри. Тогда удаляем этот старый добавил очередной трапецоид и на его место ставим дерево из двух концов отрезка, отрезка и четырех образовавшихся трапецоидов. Важно не забыть правильно определить соседей новых трапецоидов. В случае, если какие-то трапецоиды выродятся в треугольники, будет не четыре новых трапецоида, а 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> до соответвствующих процессе поиска трапецоидов.*Вместо них добавляем новые ключи как показано на картинкепреобразуем структуру.