Пересечение многоугольников (PSLG overlaying) — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
== Постановка задачи ==
 
== Постановка задачи ==
 
Определим пересечение двух [[ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых|ППЛГ]] <tex>S_1</tex> и <tex>S_2</tex> как ППЛГ <tex>O(S_1, S_2)</tex>, такой, что в нем существует грань <tex>f</tex> тогда и только тогда, когда существуют грани <tex>f_1</tex> в <tex>S_1</tex> и <tex>f_2</tex> в <tex>S_2</tex> такие, что <tex>f</tex> является наибольшим связным подмножеством <tex>f_1 \cap f_2</tex>. Иначе говоря, пересечение двух ППЛГ — это разбиение плоскости с помощью ребер из <tex>S_1</tex> и <tex>S_2</tex>. Необходимо построить [[ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых|РСДС]] для <tex>O(S_1, S_2)</tex>, имея РСДС для <tex>S_1</tex> и <tex>S_2</tex>. Кроме того, для каждой грани из <tex>O(S_1, S_2)</tex> будем хранить ссылки на грани из <tex>S_1</tex> и <tex>S_2</tex>, содержащие ее.
 
Определим пересечение двух [[ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых|ППЛГ]] <tex>S_1</tex> и <tex>S_2</tex> как ППЛГ <tex>O(S_1, S_2)</tex>, такой, что в нем существует грань <tex>f</tex> тогда и только тогда, когда существуют грани <tex>f_1</tex> в <tex>S_1</tex> и <tex>f_2</tex> в <tex>S_2</tex> такие, что <tex>f</tex> является наибольшим связным подмножеством <tex>f_1 \cap f_2</tex>. Иначе говоря, пересечение двух ППЛГ — это разбиение плоскости с помощью ребер из <tex>S_1</tex> и <tex>S_2</tex>. Необходимо построить [[ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых|РСДС]] для <tex>O(S_1, S_2)</tex>, имея РСДС для <tex>S_1</tex> и <tex>S_2</tex>. Кроме того, для каждой грани из <tex>O(S_1, S_2)</tex> будем хранить ссылки на грани из <tex>S_1</tex> и <tex>S_2</tex>, содержащие ее.
 +
 +
<картинка>
 +
 +
== Алгоритм ==
 +
Для начала, скопируем ППЛГ <tex>S_1</tex> и <tex>S_2</tex> в новый РСДС. Далее необходимо преобразовать полученный РСДС, чтобы он соответствовал <tex>O(S_1, S_2)</tex>. Отдельно рассмотрим преобразования вершин, полуребер и граней.
 +
 +
=== Вершины и полуребра ===
 +
Алгоритм базируется на [[Пересечение множества отрезков|заметающей прямой]], определяющей пересечения отрезков. Запускаем алгоритм на множестве отрезков, представляющих собой ребра из <tex>S_1</tex> и <tex>S_2</tex>. Напомним, что алгоритм поддерживает очередь событий <tex>Q</tex> и текущий статус <tex>T</tex> заметающей прямой. Также будем поддерживать ссылки между ребрами статуса и соответствующими полуребрами из РСДС. Поддерживаемый инвариант: над заметающей прямой корректный РСДС.
 +
 +
<картинка>
 +
 +
Обработка точки события происходит следующим образом: сначала обновляем <tex>Q</tex> и <tex>T</tex> (как в алгоритме пересечения отрезков). Если оба ребра события принадлежат одному ППЛГ, переходим к следующему событию. В противном случае, необходимо модифицировать РСДС. Возможны следующие варианты событий (см. рисунок ниже):
 +
 +
<картинка>
 +
 +
Рассмотрим один из случаев, остальные обрабатываются аналогично. Пусть ребро <tex>e</tex> из <tex>S_1</tex> пересекает вершину <tex>v</tex> из <tex>S_2</tex>. Ребро <tex>e</tex> заменяем двумя ребрами <tex>e'</tex> и <tex>e''</tex>. Два полуребра, соответствующих <tex>e</tex>, заменяются четырьмя полуребрами: два существующих полуребра будут исходить из концов <tex>e</tex>, а два новых полуребра — из <tex>v</tex> (см. рисунок). Устанавливаем ссылки на близнецов для ребер <tex>e'</tex> и <tex>e''</tex>. Обновим ссылки на следующие полуребра для <tex>h_1</tex> и <tex>h_4</tex>, пусть это будут <tex>h_5</tex> и <tex>h_6</tex>, соответственно. Не забудем установить полуребра <tex>h_1</tex> и <tex>h_4</tex> в качестве предыдущих полуребер у <tex>h_5</tex> и <tex>h_6</tex>. Теперь обновим ссылки на полуребра, инцидентные вершине <tex>v</tex>. Для этого сначала при помощи порядка обхода определим, между какими полуребрами <tex>S_2</tex> находится <tex>e</tex>. Рассмотрим полуребро <tex>h_3</tex>: свяжем его с первым полуребром, видимым из <tex>h_4</tex> при обходе по часовой стрелке и исходящем из <tex>v</tex>. Полуребро <tex>h_4</tex> должно быть связано с первым полуребром, идущим в <tex>v</tex>, при обходе против часовой стрелки. Аналогично обработаем <tex>e''</tex>.
 +
 +
 +
<tex></tex>

Версия 14:44, 17 мая 2015

Постановка задачи

Определим пересечение двух ППЛГ [math]S_1[/math] и [math]S_2[/math] как ППЛГ [math]O(S_1, S_2)[/math], такой, что в нем существует грань [math]f[/math] тогда и только тогда, когда существуют грани [math]f_1[/math] в [math]S_1[/math] и [math]f_2[/math] в [math]S_2[/math] такие, что [math]f[/math] является наибольшим связным подмножеством [math]f_1 \cap f_2[/math]. Иначе говоря, пересечение двух ППЛГ — это разбиение плоскости с помощью ребер из [math]S_1[/math] и [math]S_2[/math]. Необходимо построить РСДС для [math]O(S_1, S_2)[/math], имея РСДС для [math]S_1[/math] и [math]S_2[/math]. Кроме того, для каждой грани из [math]O(S_1, S_2)[/math] будем хранить ссылки на грани из [math]S_1[/math] и [math]S_2[/math], содержащие ее.

<картинка>

Алгоритм

Для начала, скопируем ППЛГ [math]S_1[/math] и [math]S_2[/math] в новый РСДС. Далее необходимо преобразовать полученный РСДС, чтобы он соответствовал [math]O(S_1, S_2)[/math]. Отдельно рассмотрим преобразования вершин, полуребер и граней.

Вершины и полуребра

Алгоритм базируется на заметающей прямой, определяющей пересечения отрезков. Запускаем алгоритм на множестве отрезков, представляющих собой ребра из [math]S_1[/math] и [math]S_2[/math]. Напомним, что алгоритм поддерживает очередь событий [math]Q[/math] и текущий статус [math]T[/math] заметающей прямой. Также будем поддерживать ссылки между ребрами статуса и соответствующими полуребрами из РСДС. Поддерживаемый инвариант: над заметающей прямой корректный РСДС.

<картинка>

Обработка точки события происходит следующим образом: сначала обновляем [math]Q[/math] и [math]T[/math] (как в алгоритме пересечения отрезков). Если оба ребра события принадлежат одному ППЛГ, переходим к следующему событию. В противном случае, необходимо модифицировать РСДС. Возможны следующие варианты событий (см. рисунок ниже):

<картинка>

Рассмотрим один из случаев, остальные обрабатываются аналогично. Пусть ребро [math]e[/math] из [math]S_1[/math] пересекает вершину [math]v[/math] из [math]S_2[/math]. Ребро [math]e[/math] заменяем двумя ребрами [math]e'[/math] и [math]e''[/math]. Два полуребра, соответствующих [math]e[/math], заменяются четырьмя полуребрами: два существующих полуребра будут исходить из концов [math]e[/math], а два новых полуребра — из [math]v[/math] (см. рисунок). Устанавливаем ссылки на близнецов для ребер [math]e'[/math] и [math]e''[/math]. Обновим ссылки на следующие полуребра для [math]h_1[/math] и [math]h_4[/math], пусть это будут [math]h_5[/math] и [math]h_6[/math], соответственно. Не забудем установить полуребра [math]h_1[/math] и [math]h_4[/math] в качестве предыдущих полуребер у [math]h_5[/math] и [math]h_6[/math]. Теперь обновим ссылки на полуребра, инцидентные вершине [math]v[/math]. Для этого сначала при помощи порядка обхода определим, между какими полуребрами [math]S_2[/math] находится [math]e[/math]. Рассмотрим полуребро [math]h_3[/math]: свяжем его с первым полуребром, видимым из [math]h_4[/math] при обходе по часовой стрелке и исходящем из [math]v[/math]. Полуребро [math]h_4[/math] должно быть связано с первым полуребром, идущим в [math]v[/math], при обходе против часовой стрелки. Аналогично обработаем [math]e''[/math].


[math][/math]