Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
. Пересечение двух звездны:
340
Гл. 7. Пересечения
Алгоритм решения этой задачи был бы весьма полезен для приложений типа трассировки или размещения, описанных в разд. 7.1.3. Прежде чем взяться за решение задачи С.2.1, опишем дополнительно ее важные приложения.
7.2.3.1. Приложения
Задача С.2.2 (ПРОВЕРКА ПЕРЕСЕЧЕНИЯ МНОГОУГОЛЬНИКОВ). Даны два простых многоугольника Р и Q с М и N вершинами соответственно. Пересекаются ли они?
G' с: Р Гааиицы не пересекаются
Рис. 7.12. Р сг Q, или QaP, или же есть пара пересекающихся ребер.
Как указано в разд. 7.2.1 для выпуклых многоугольников, если Р и Q пересекаются, то или Р содержит Q, или Q содержит Р, или некоторое ребро Р пересекает одно из ребер Q (рис. 7.12).
Поскольку Р и Q оба просты, то при любом пересечении их ребер эти ребра будут принадлежать разным многоугольникам. Обозначим через Т(N) время, необходимое для решения задачи С.2.1. Тогда можно определить факт пересечения ребер Р и Q за T(N-\-M) операций. И если пересечений не найдено, то останется только проверить Р cr Q или Q с= Р.
Если Р лежит внутри Q, то все вершины Р лежат внутри Q, поэтому можно один раз применить проверку принадлежности точки за время O(N) (по теореме 2.1), используя любую вершину Р. Если эта вершина лежит вне Q, то можно тем же самым способом установить, верно ли, что QczP, за время О(М). Отсюда имеем следующую теорему:
Теорема 7.5. Пересечение простых многоугольников преобразуется за линейное время к проверке пересечения прямолинейных отрезков:
ПРОВЕРКА ПЕРЕСЕЧЕНИЯ МНОГОУГОЛЬНИКОВ ocN ПРОВЕРКА ПЕРЕСЕЧЕНИЯ ПРЯМОЛИНЕЙНЫХ ОТРЕЗКОВ
7.2. Плоские приложения
341
Мы уже видели, что сложность алгоритмов, работающих с многоугольниками, может зависеть от того, известна или нет простота этих многоугольников. Например, выпуклую оболочку для простого многоугольника можно найти за время в(М) (теорема 4.12), в то время как Q(N\ogN) является нижней границей для непростых многоугольников. Поэтому было бы полезно иметь алгоритм проверки простоты.
Задача С.2.3 (ПРОВЕРКА ПРОСТОТЫ МНОГОУГОЛЬНИКА). Дан многоугольник. Прост ли он?
Простой и непростые многоугольники показаны на рис. 7.13. Поскольку многоугольник прост тогда и только тогда, когда
Рис. 7.13. Простой и непростые многоугольники.
никакая пара его ребер не пересекается, то немедленно имеем, что:
ПРОВЕРКА ПРОСТОТЫ МНОГОУГОЛЬНИКА ос„ ПРОВЕРКА ПЕРЕСЕЧЕНИЯ ПРЯМОЛИНЕЙНЫХ ОТРЕЗКОВ
7.2.3.2. Алгоритмы пересечения отрезков
Предположим, что заданы N интервалов на действительной оси и необходимо узнать, не перекрываются ли какие-нибудь два из них. Ответ можно получить за время 0(N2), проверив все пары интервалов, но тут же на ум приходит намного лучший алгоритм, основанный на сортировке. Если упорядочить 2N концевых точек этих интервалов и обозначить их как левые (Л) или правые (П), то эти интервалы не перекрываются тогда и только тогда, когда концы их образуют чередующуюся последовательность: Л, П, Л, П, П, Л, П (рис. 7.14). Эту проверку можно провести за 0(N\ogN) времени.
Хотелось бы ответить на два вопроса: можно ли улучшить этот алгоритм и обобщается ли он на случай двух измерений?
Чтобы получить нижнюю оценку, продемонстрируем соответствие между задачей о наложении интервалов и известным фундаментальным вопросом из теории множеств: ПРОВЕРКОЙ УНИКАЛЬНОСТИ ЭЛЕМЕНТОВ (даны N действительных чисел; все ли они различны? (разд. 5.2)). Ранее было показано,
Простой
Непростые
342
Гл. 7 Пересечения
что эта задача легко разрешима за время 0(N\ogN) методом сортировки, и, хотя нет простого способа показать, что сортировка необходима, тем не менее известно (из результатов Добкина и Липтона [Dobkin, Lipton (1976)] и Бен-Ора [Веп-Ог (1983)]), что необходимо затратить O(NlogN) времени в
~~Л ft л ti л л л гГ
Л и Л чередуются- Нет наложений
Л Л П Л П П Л Л Л Л Л Л
Л и Л не чередуются Рис. 7.14. Определение наложений интервалов.
модели вычислений типа дерева решений (следствие 5.1). Теперь покажем, что
УНИКАЛЬНОСТЬ ЭЛЕМЕНТОВ ос„ НАЛОЖЕНИЕ ИНТЕРВАЛОВ
Заданный набор из N действительных чисел {х,} можно преобразовать в набор из iN интервалов {[х,, а;] } за линейное время. Эти интервалы перекрываются тогда и только тогда, когда исходные числа не уникальны, и это доказывает следующую теорему:
Теорема 7.6. Для того чтобы определить, перекрываются ли N интервалов, необходимо и достаточно Q(N\ogN) сравнений, при условии что можно использовать лишь алгебраические функции на входе.
Насколько строгим является это ограничение на алгебраические функции? С одной стороны, оно запрещает использовать функцию «целая часть», которая, как было показано в разд. 6.4, является очень мощной операцией. (Напомним, что использование этой функции позволило Гонзалесу [Gonzales (1975)] решить задачу MAXGAP за Q(N) времени.) Методы, которые позволили бы доказать теорему 7.6 с использованием функции «целая часть», не известны, однако можно предположить, что ее добавление вряд ли повлияет на нижнюю оценку, тем более что теорема 7.6 приложима к случаю любого числа измерений. В частности, для проверки пересечения N отрезков на плоскости необходимо Q(N log N) операций.
