Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Оптимальный по времени алгоритм построения пересечения двух выпуклых многоугольников, изложенный в разд. 7.2.1, является плоским заметанием. Его непосредственное обобщение на случай трех измерений оказывается неоптимальным по причинам, приведенным в начале разд. 7.3.1. Однако корректное обобщение было недавно получено Гертелем и др. [Hertel, Melhorn, Mantyla, Nievergelt (1985)]; их метод не только является очень важным примером алгоритма пространственного заметания, но и представляет собой альтернативу технике построения пересечения многоугольников, изложенной в разд. 7.3.1, и может служить эталоном элегантности (а также высокой производительности). Чтобы дать представление об этом методе, возьмем его двумерный аналог в форме плоского заметания, при котором вычисляются точки, являющиеся пересечениями границ двух многоугольников Pi и Р2; затем обходом попеременно по границам Pi и Р2 между точками их пересечения строим границу Pi f] Pz- Паре ребер многоугольника Р, (i = 1, 2), пересеченных заметающей прямой в Е2, соответствует кольцо из многоугольников (именуемое короной), пересеченных заметающей плоскостью в Е3, а роль точек пересечения в Е2 играют многоугольные кольца в Е3. Авторы метода
392
Гл. 7. Пересечения
показали, что пространственное заметание эффективно корректирует эти короны и определяет по меньшей мере одну из вершин в каждом многоугольном кольце, начиная с которой можно легко построить всю границу. Доказано, что этот алгоритм требует О (NlogN) времени. Соответствующая задача проверки, безусловно, не сложнее задачи построения, а, вероятно, даже проще. И действительно, Добкин и Киркпатрик [Dobkin, Kirkpatrick (1984)] изобрели алгоритм для решения этой задачи с оценкой Q(N), а также отметили, что Дайер независимо получил аналогичный результат.
Задача построения ядра простого многоугольника (разд. 7.2.6) представляет интересный большой класс, к которому относят задачи видимости (ядро фактически — это множество таких точек, из которых видимы все вершины). Подобные задачи возникают во многих приложениях в машинной графике, анализе сцен, робототехнике и т. д. Основная идея заключается в том, что две точки pi и р2 (обоюдно) видимы, если отрезок pip2 не пересекает никакой «запретной» кривой. Видимость обычно определяется по отношению к некой точке р. В плоском случае, если запретными кривыми являются отрезки, то локус точек, видимых из р и называемых многоугольником видимости для р, представляет собой звездный многоугольник (возможно, неограниченный). Многоугольник видимости ограничен, если р лежит внутри простого многоугольника Р, а граница Р является запретной кривой. Для случая, когда множество отрезков на плоскости представляет собой единственный простой многоугольник, известны по меньшей мере два алгоритма с линейной оценкой по времени [ElGindy, Avis (1981); Lee (1983b)]. Используемый при этом подход близок к идее сканирования по Грэхему: здесь сначала определяется одна точка, видимая из р, а затем (используя свойство простоты) вершины Р сканируются, а невидимые из р участки Р удаляются. В том случае, когда множество отрезков представляет собой пг несвязанных выпуклых многоугольников, обладающих в сумме N ребрами, а К—число ребер в искомом ядре, данную задачу можно решить за время О (m log N-j-К) [Lee, Chen (1985)]. Эдельсбруннер и др. [Edelsbrunner, Overmars, Wood (1983)] также изучали эту задачу и исследовали вопрос о поддержании многоугольников видимости в том случае, когда разрешены операции вставки или удаления, и, кроме того, вопрос о когерентности, когда разрешены перемещения направления взгляда или заданных точек. Реализуя теоретико-множественные операции на многоугольниках видимости, можно определить специальные типы видимости; за сжатым обзором этого материала читатель отсылается к работе Туссена [Toussaint (1980)].
7.5. Упражнения
7.5. Упражнения
1. Заданы два выпуклых многоугольника Р, и P2, число вершин которых в сумме равно N. Построить алгоритм типа плоского заметания, который вычислял бы пересечение Р, и Р2 за время O(N) следующим образом:
(a) определял бы ^-множество всех пересечений границ Р} и Р2;
(b) используя Э', строил бы границу Pi П Р2.
2. Задан набор S, состоящий из N отрезков на плоскости; построить алгоритм, который решал бы вопрос о существовании прямой I, пересекающей все отрезки из S (прокалывающей прямой), и, если она есть, строил бы ее.
3. Задан набор S, состоящий из N отрезков на плоскости, и пробный отрезок s*; надо предварительно обработать 5 так, чтобы получить эффективный алгоритм для проверки факта пересечения s* с произвольным элементом S.
4. Пусть Р — выпуклый полиэдр. Запрос заключается в проверке пересечения отрезком s из Е3 полиэдра Р. Предполагая, что работа ведется с типовыми запросами, предварительно обработать Р и построить эффективный алгоритм обработки запросов.
5. Заданы два выпуклых полиэдра Р и Q, число вершин которых в сумме равно N. Можете ли вы придумать алгоритм, проверяющий факт пересечения Р и Q за время 6(Л?)?
