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

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

Определим пересечение двух ППЛГ [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]