15.6. ЭФФЕКТИВНОЕ ОПРЕДЕЛЕНИЕ ПЕРЕСЕЧЕНИЯ МНОГОУГОЛЬНИКОВ

Определение пересечения двух многоугольников путем многократного применения алгоритма 15.3, описанное в предыдущем разделе, не всегда оказывается эффективным. Так, информация относительно расположения вершин многоугольника полученная за один прогон алгоритма, никак не используется при другом прогоне. Существуют различные способы увеличения эффективности этого процесса и некоторые из них будут здесь изложены. Напомним, что пит обозначают число вершин (или сторон) многоугольников соответственно. В наихудшем случае шаги 3—8 алгоритма 15.3 выполняются раз. Минимальная оценка трудоемкости определения пересечения составляет поскольку все вершины должны быть обработаны, по меньшей мере, один раз. Разница между может оказаться значительной, поэтому необходим поиск эффективных процедур.

Однако следует отметить, что, если — малое число (скажем, 3 или 4), как это часто бывает в прикладных задачах машинной графики, повышение эффективности процедуры может оказаться невозможным. Экономия, полученная за счет уменьшения числа осмотров одной вершины, может утрачиваться вследствие роста объема учетных операций. Поэтому проводимое в этом разделе обсуждение, относится к задаче определения пересечения двух многочленов лишь в случае, когда у обоих число вершин значительно. Существенное значение для машинной графики имеют алгоритмы, обеспечивающие эффективное определение попарных пересечений для большого числа многоугольников. Именно такая ситуация возникает при решении задачи разделения видимых и невидимых частей воспроизводимого объекта, а также при проверке рисунка схемы, особенно в случае высокой степени интеграции. Здесь также применимы принципы, положенные в основу эффективных алгоритмов определения пересечения многоугольников. Поэтому мы опишем несколько основных применяемых методов.

Один из возможных способов ускорения определения пересечения связан с использованием фигур более простой формы, чем заданные многоугольники. Пусть — правильные описанные прямоугольники для многоугольников соответственно. (Их легко построить, используя экстремальные значения координат вершин многоугольников.) Вместо того, чтобы решать задачу пересечения для многоугольников, можно решать значительно более простую задачу определения пересечения прямоугольников Если описанные прямоугольники не пересекаются, то это означает, что заданные многоугольники тем более не будут

пересекаться. Если один из прямоугольников находится внутри другого, например лежит внутри то можно рассматривать пересечение прямоугольника и многоугольника а затем пересечение полученного многоугольника и многоугольника П (рис. 15.5, а). Если прямоугольники имеют непустое пересечение то можно рассматривать пересечение каждого многоугольника с прямоугольником а получив два новых многоугольника, применять эту процедуру уже к ним (рис. Преимуществом этого подхода является быстрое исключение из рассмотрения вершин многоугольников, далеко отстоящих друг от друга.

Рис. 15.5. (см. скан) Иллюстрация к эффективному определению перо сечения двух многоугольников а — определение новых многоугольников для поиска пересечения многоугольников П] и о использование рекурсивной процедуры разбиения многоугольников в процессе разрезания

Другие подходы предусматривают предварительную сортировку вершин, и наиболее экономичным оказывается случай, когда по крайней мере один многочлен остается иксиро ванны

Первый метод, предложенный в статье [15.2], является весьма общим и подходит для решения различных геометрических задач. Рассмотрим множество прямых на плоскости и точки их попарного пересечения Очевидно, что Обозначим координаты точки Р; через Без всякой потери общности можно допустить, что точки пересечения снабжены индексами таким образом, что Вертикальные прямые делят плоскость полос таким образом, что в пределах каждой полосы отсутствуют пересечения прямых. Теперь отрезки прямых можно упорядочить в пределах каждой полосы в соответствии, например, со значением координату их средних точек. Это упорядочение является хорошо определенным в связи с

отсутствием пересечений отрезков в пределах полосы. Затраты на упорядочение К объектов составляют величину порядка и в данном случае они будут равны

Предположим далее, что задана новая точка и требуется определить, находится ли она на одной из к прямых или лежит внутри области, задаваемой этими прямыми. Чтобы решить эту задачу, можно сначала найти полосу, в которой расположена эта точка, используя значение ее координаты х, а затем определить ее положение относительно прямых, исходя из ее координаты у. Оба решения эквивалентны введению объекта в упорядоченный список, т. е. задаче, для решения которой требуется время, пропорциональное длине списка. В нашем случае это время равно Поскольку можно сказать, что затраты пропорциональны (Переборный алгоритм требует затрат порядка к.) В результате может быть сформулировано формальное утверждение.

Теорема 15.1. Определить положение точки относительно к прямых можно за время порядка при условии предварительной сортировки этих прямых. Затраты на предварительную сортировку определяются величиной порядка

Другой метод, предложенный в докладе [15.3], предусматривает выполнение аналогичной предварительной сортировки, но на этот раз в полярных координатах. На использование метода наложено жесткое ограничение, требующее выпуклости обоих многоугольников. Метод заключается в выборе внутри одного из многоугольников, например точки С и определении полуотрезков соединяющих точку вершинами многоугольника Затраты на отыскание точки и прямых пропорциональны т. Если прямые направлены из центра в вершину, то точкам, расположенным справа, соответствует положительное значение в уравнении (15.1) и, следовательно, легко установить, принадлежит ли точка сектору. Точка принадлежит сектору, образованному прямыми если соответствующее значение положительно относительно первой прямой и отрицательно относительно второй (рис. 15.6, а). Секторы можно упорядочить, например, по часовой стрелке, и, следовательно, можно найти сектор, которому принадлежит точка, затратив на это время, пропорциональное После нахождения сектора, содержащего одну вершину второго многоугольника, например для остальных вершин секторы можно найти, последовательно просматривая секторы и выясняя, не содержат ли они каких-либо вершин. Если многоугольник содержит центр (рис. 15.6, б), его секторы и вершины обходятся одновременно и никакие возвраты не предусматриваются. Если же центр лежит вне (рис. 15.6, в), то можно найти новый сектор, включающий и имеющий центр в

Рис. 15.6. Иллюстрация к эффективному определению пересечения двух многоугольников: а — определение секторов в рамках процедуры определения пересечения двух выпуклых многоугольников, б — определение пересечения в случае, когда центр С расположен внутри обоих многоугольников, для обоих многоугольников направление последовательного обхода вершин может быть одним и тем же, в — определение пересечения в случае, когда центр С находится вне многоугольника Обход вершин многоугольника должен проводиться последовательно в двух направлениях, однако осмотру подлежит лишь часть секторов многоугольника точке С. После этого вершины многоугольника разделяются на две группы, каждая из которых при поиске соответствующих секторов может обрабатываться последовательно. В любом случае на этот процесс затрачивается время, пропорциональное где я — число вершин многоугольника После окончания этой процедуры оценивается положение вершин, расположенных в каждом секторе, относительно стороны многоугольника находящейся в этом секторе.