Компьютерная геометрия и графика. Лекция 3

План занятия: Задача о пересечении двух выпуклых многоугольников. Задача о пересечении двух произвольных многоугольников.

Задача о пересечении двух выпуклых многоугольников.

Дано: два многоугольника. A B А-отсекающий. В-отсекаемый. Для решения задачи ориентируем контур отсекающего многоугольника против часовой стрелки.

32A B 1 4 На каждом шаге выбираем очередное ребро отсекающего многоугольника. Поочередно проверяем положение всех вершин отсекаемого многоугольника относительно прямой, проходящей через выбранное текущее ребро.

Убираем те вершины отсекаемого многоугольника В, которые не лежат в той же полуплоскости (относительно выбранного ребра), в которой лежит многоугольник А. 2 A B 1 4

Если на каком-то шаге мы обнаружили, что весь многоугольник В находится с другой стороны (в нашем случае слева), то завершаем работу.

Алгоритм отсечения: z=V(t1, t2, t1,B[0]); j=0; for (i=0;i<N;i++) {z2=z; z=V(t1, t2, t1, B[i+1]); if (z*z2<0) R[j++]=Per(t1, t2, B[i], B[i+1]); if (z>0) R[j++]=B[i+1]; }

Алгоритм пересечения произвольных многоугольников.

Сложность задачи и ее отличие от предыдущего алгоритма в том, что пересечений может быть несколько

Пример:

Оба контура ориентируем против часовой стрелки. Находим самую левую вершину многоугольников, с нее начинается работа алгоритма. Идем по контуру и ищем ближайшую точку пересечения многоугольников.

Существует две ситуации: 1. Пройдя все вершины мы не нашли ни одной точки пересечения. Такое возможно в двух случаях: А и В вообще не имеют общих точек. А целиком лежит в В. А В А В

В таком случае мы просто берем любую точку одного многоугольника и задаем два вопроса 1. Точка принадлежащая многоугольнику А принадлежит В? 2. Точка принадлежащая многоугольнику В принадлежит А? Если ответ ДА только на один из этих вопросов, то один многоугольник целиком лежит в другом. Если ответ НЕТ на оба вопроса, то у многоугольников вообще нет пересечений. Если ответ ДА мы получили на оба этих вопроса, то многоугольники просто совпадают.

2. Точка (точки) пересечения все-таки найдены: В каждой точке пересечения поворачиваем налево (так как наш контур ориентирован против часовой стрелки), и переключаемся на другой многоугольник. Если после нескольких переходов попали в исходную точку, то получили ответ (или его часть, так как пересечений может быть несколько). Чтобы найти другую часть ответа, мы проверяем есть ли еще не рассмотренные точки пересечения. Если есть, то идем по ним аналогичным способом и получаем вторую часть ответа. И так далее, пока существуют еще не тронутые нами точки пересечения.

Возможные исключения: 1. Точка пересечения является вершиной одного из многоугольников. 2. Пересечение является вершиной двух многоугольников одновременно 3. Стороны многоугольников частично совпадают. Рассмотрим подробнее эти исключения:

1. Точка пересечения является вершиной одного из многоугольников:А Если угол целиком лежит в одной полуплоскости от стороны многоугольника (ВС), то переключаться не нужно. Если сторона (ВС) пересекает угол, то - нужно. А В С В С В этом случае не всегда надо переключаться с одного на другой многоугольник.

2. Пересечение является вершиной двух многоугольников одновременно: В этом случае не всегда надо переключаться с одного на другой многоугольник. А Переключаться надо, если углы пересекаются А Переключаться не надо, если углы не пересекаются, то есть один лежит внутри другого.

Вопрос о взаимной расположенности углов друг относительно друга выясняется легко: Ищем векторные произведения векторов, показанных на рисунке черными стрелками. Если все эти значения одинаковые по знаку, то переключаемся на другой многоугольник. Иначе не переключаемся. (то есть мы проверяем, что вершина 2 лежит между 1-3, а вершина 3 между 2-4) Надо переключаться! НЕ надо переключаться!

3. Стороны частично совпадают: Идем из точки D по синему многоугольнику. Дошли до точки пересечения с красным многоугольником (точка А). Переключаемся на него и идем уже по ребру красного, до пересечения с вершиной синего многоугольника. (точка В) А В D С D

А-В рассматриваем как единую точку пересечения. Смотрим на две соседние ей вершины: -точке А соседняя С (так как А вершина красного многоугольника), -точке В соседняя D (так как точка В вершина синего многоугольника) Если соседние вершины лежат по разные стороны от АВ то переключатся в точке В надо, иначе нет. А В D С D

КОНЕЦ.