Cтраница 2
Это позволяет естественным образом установить соответствие между точками границы многоугольника дР и точками окружности С. Для; каждой ВС - или СС-пары видимости в Р, порождаемой алгоритмом вычисления пар видимости, соединим соответствующие точки некоторой кривой, лежащей внутри окружности С. Кривые будем проводить таким образом, чтобы они нигде не пересекались, за исключением концевых точек. Двойственный граф областей, входящих в Р, дает естественный и конструктивный способ реализации этой операции. Обрабатывая вершину двойственного графа, степень которой равна единице, мы должны провести кривую между двумя точками, лежащими на С. Эта кривая разбивает круг на две части, одна из которых может быть исключена из рассмотрения на последующих этапах построения отображения. Таким образом, полное построение требуемой совокупности кривых может быть осуществлено в результате последовательной обработки с удалением вершин двойственного графа, имеющих степень, равную единице, выполняемой до тех пор, пока двойственный граф не станет пустым. [16]
Соблазнительно было бы сказать, что области из Р образуют разбиение внутренности многоугольника Р, но мы не можем так сказать, так как мы пока не знаем, имеет ли многоугольник Р внутренность. Однако, учитывая, каким образом были получены области из Р, мы знаем, что их можно склеить вместе по горизонтальным сторонам, определяющим пары видимости, таким образом, что получившаяся область будет топологически эквивалентна кругу. Алгоритм вычисления пар видимости легко модифицировать так, чтобы он выполнял такое склеивание, или, более правильно, порождал двойственный граф склеенной области, в котором области представляются вершинами, и вершины, соответствующие областям, разделяемым горизонтальной стороной, определяющей пару видимости, соединяются ребром. [17]
Оставшаяся часть данной статьи включает пять разделов и приложение. Эта структура данных состоит из двух уровней деревьев поиска с указателями. Показывается, что с использованием такой структуры данных временная сложность алгоритма вычисления пар видимости, рассматриваемого в разд. В заключение в разд. В приложении приведено описание деревьев поиска с указателями, которые используются не только в алгоритме, непосредственно вычисляющем пары видимости, но и в алгоритме жордановой сортировки. [18]
Путем линейного по времени сведения задачи триангуляции к задаче вычисления пар видимости [5, 9] мы получаем алгоритм с временной сложностью О ( п log log / г), решающий задачу триангуляции. Главными составляющими нашего алгоритма являются жорданова сортировка, метод сбалансированного разбиения на части и деревья поиска с указателями. Представляет интерес следующее замечание: и алгоритм жордановой сортировки, и алгоритм вычисления пар видимости используют деревья поиска с указателями, но только разных типов. Алгоритм жордановой сортировки требует быстрого доступа в окрестность элемента, занимающего произвольную позицию в дереве, но при этом нет необходимости искать элементы по вторичному порядку. Этим требованиям удовлетворяют однородные деревья поиска с указателями. [19]
Как мы увидим, это обеспечивает временную сложность О ( п log log n) для алгоритма вычисления пар видимости, использующего стратегию сбалансированного разбиения. [20]
Алгоритмы проверки многоугольника на простоту и получение фактов, подтверждающих непростоту многоугольника, легко могут быть расширены для обработки связных незамкнутых ломаных. Эта прямая разбивает ломаную на граничные сегменты, целиком лежащие по одну сторону от прямой. Выполним жорданову сортировку точек пересечения ломаной с прямой. В противном случае дальнейшую обработку будем производить аналогично шагу 4 алгоритма вычисления пар видимости ( см. разд. В результате мы построим многоугольники, целиком лежащие по одну сторону от прямой. [21]