Изменения

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

Пересечение многоугольников (PSLG overlaying)

1 байт добавлено, 22:38, 28 марта 2014
Нет описания правки
Для начала посмотрим, как можно больше информации от doubly connected edge lists для <tex>S1</tex> и <tex>S2</tex> мы можем повторно использовать в doubly connected edge lists для <tex>O(S1, S2)</tex>. Рассмотрим сеть ребер и вершин S1. Эта сеть разделена на кусочки краями <tex>S2</tex>. Эти кусочки в большинстве своем могут использоваться повторно, все, за исключением тех, которые отделены краями <tex>S2</tex>. Такие нужно обновлять. Если ориентация <tex>half-edge</tex> изменится, нам придется менять информацию в этих записях. Половинки ребра ориентированы таким образом, что <tex>face</tex>, которым они связаны лежит слева; форма <tex>face</tex> может изменяться в наложении, но он будет оставаться в той же стороне <tex>half-edge</tex>. Следовательно, мы можем повторно использовать <tex>half-edge</tex> records, соответствующие краям, которые не пересекаются ребра из другой карты. Иными словами, есть только <tex>half-edge</tex> records в <tex>DCEL</tex> для <tex>O(S1, S2)</tex>, которые мы не можем заимствовать из <tex>S1</tex> или <tex>S2</tex>, ими являются те, которые попадают на пересечение между краями из разных карт.
Это предлагает следующие подходы. Во-первых, скопировать doubly­connected edge lists <tex>S1</tex> и <tex>S2</tex> в один новый <tex>DCEL</tex>. Новый <tex>DCEL</tex> не является допустимым <tex>DCEL</tex>, т.к. он еще не представляет собой плоский подграф.
====Объединения графов====
 Это предлагает следующие подходы. Во-первых, скопировать doubly­ connected edge lists <tex>S1</tex> и <tex>S2</tex> в один новый <tex>DCEL</tex>. Новый <tex>DCEL</tex> не является допустимым <tex>DCEL</tex>, т.к. он еще не представляет собой плоский подграф. Это задача алгоритма заметающей прямой: он должен трансформировать <tex>DCEL</tex> в допустимый <tex>DCEL</tex> для <tex>O(S1, S2)</tex> путем вычисления пересечения между двумя сетями ребер, и связывая воедино соответствующие части из двух <tex>DCEL</tex>. Мы применяем этот алгоритм на множестве сегментов, что является объединением множеств ребер двух подграфов <tex>S1</tex> и <tex>S2</tex>. Напомним, что алгоритм поддерживается двумя структурами данных: очереди событий <tex>Q</tex>, в котором хранятся точки событий, и структура состояния <tex>T</tex>, которой является бинарное дерево храненящее сегменты, пересекающие линии развертки, расположенные слева направо. Мы теперь также должны поддерживать <tex>DCEL</tex> <tex>D</tex>. Первоначально <tex>D</tex> содержит копию <tex>DCEL</tex> для <tex>S1</tex> и <tex>DCEL</tex> для <tex>S2</tex>. В плоскости развертки преобразуем <tex>D</tex> к правильному <tex>DCEL</tex> для <tex>O(S1, S2)</tex>. Мы держим перекрестные указатели между ребер в структуре состояния <tex>T</tex> и половина текущих записей в <tex>D</tex>, которые соответствуют им. Таким образом мы можем получить доступ к части <tex>D</tex>, которая должна быть изменена, когда мы сталкиваемся с точкой пересечения.
В другом случае, мы поддерживаем то, что в любое время в течение развертки, часть выше линии развертки наложения будет считаться правильной. Теперь что мы должны делать, когда мы достигнем точки событий. Прежде всего, мы обновляем <tex>T</tex> и <tex>Q</tex>, как и в алгоритме заметающей прямой. Если событие включает в себя только ребра из одного из двух подграфов, это все, точка событие является вершиной, которые могут быть использованы повторно. Если событие включает края с двух подграфов, мы должны сделать локальные изменения в <tex>D</tex> -- связать doubly­ connected edge list двух оригинальных подграфов в точке пересечения.
139
правок

Навигация