Изменения

Перейти к: навигация, поиск

Трапецоидная карта

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

Навигация