Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
GVP (S) ={х? R2: d (р, х)2 + rp < d (q, х)2 + rq, V? <= S},
называемое обобщенной областью Вороного точки р (относительно множества S). Назовем множество GVor(S) = {GV,, (S): р е S} обобщенной диаграммой Вороного множества S.
(a) Показать, что для каждой точки ре5 область GVP(S) является выпуклой и имеет прямолинейные ребра.
(b) Показать, что в случае гр = 0 для всех peS обобщенная диаграмма Вороного превращается в обычную диаграмму Вороного множества S.
(c) Показать, что при надлежащем выборе значений чисел г'р можно добиться того, что для некоторых peS области GVP(S) будут пустыми.
(d) Разработать алгоритм построения обобщенной диаграммы Вороного множества S, имеющий сложность Q(N\ogN). (Указание: воспользуйтесь идеей, представленной в разд. 6.3.1 (диаграммы Вороного высших порядков).)
6.6. Упражнения
325
14. В задаче о НАИМЕНЬШЕЙ БОМБЕ требуется определить наименьшую окружность, охватывающую не менее k из N заданных точек на плоскости. Разработать полиномиальный алгоритм, решающий эту задачу.
15. Доказать, что граф Габриэля множества S из N точек (определение графа Габриэля дано в разд. 6.5) получается из триангуляции Делоне множества S в результате удаления из нее каждого ребра, которое не пересекает двойственное ему ребро диаграммы Вороного.
16. Доказать отношение (6.7) в разд. 6.5.
17. Ли. Показать, что в случае /-i-метрики граф относительного соседства jV точек на плоскости по-прежнему является подграфом соответствующей триангуляции Делоне. Разработайте алгоритм построения этого графа.
18. Разработать алгоритм со сложностью 0(N log N) построения срединных осей выпуклого iV-угольника (определение срединных осей дано в разд. 6.5).
ГЛАВА
Пересечения
Основной причиной изучения задач о пересечениях явился тот простой факт, что два объекта не могут одновременно находиться в одном и том же месте. Программа, предназначенная для архитектурного проектирования, должна внимательно позаботиться о том, чтобы двери не оказались там, где их невозможно открыть, а коридоры не проходили через шахту лифта. В машинной графике один объект, подлежащий выводу, заслоняет другой, если их проекции на картинную плоскость пересекаются. Выкройки можно вырезать из одного куска материи только тогда, когда их удается разложить так, что они не накрывают одна другую. Важность разработки эффективных алгоритмов определения пересечений станет ясной, если учесть, что в промышленных приложениях происходит постоянный рост сложности задач: сложное графическое изображение может состоять из сотни тысяч векторов, архитектурная база данных зачастую содержит свыше миллиона элементов, а одна интегральная схема может содержать миллионы компонентов. В подобных случаях даже квадратичные алгоритмы неприемлемы.
Другая причина для исследований сложности алгоритмов пересечения заключается в том, что они проливают свет на глубинную структуру геометрических задач и позволяют поставить ряд фундаментальных вопросов. Например, какова сложность решения вопроса о простоте многоугольника? Исследования подобных вопросов были бы оправданны, даже если бы они не имели никаких практических приложений, тем более что будет показано то, как широко используются алгоритмы данной главы. Поскольку две фигуры пересекаются только тогда, когда одна из них содержит хотя бы одну точку другой1), то естественно, что в алгоритмах пересечения не обойтись без про-
1) Это зависит от того, как определено пересечение границ.
7.1. Примеры из приложений
327
верки принадлежности точки. Поэтому можно считать задачи о пересечениях естественным расширением задач о принадлежности, рассмотренных в контексте геометрического поиска в гл. 2.
Для того чтобы лучше представить себе данную область, рассмотрим теперь более детально ряд характерных приложений.
7.1. Примеры из приложений
7.1.1. Задачи удаления невидимых линий и поверхностей
Одной из важных задач машинной графики, привлекшей к себе внимание многих исследователей [Desens, 1969); Freeman, Loutrel (1967); Galimberti, Montanari (1969); Loutrel (1970); Matsushita (1969); Newman, Sproull (1973); Sutherland (1966); Warnock (1969); Watkins (1970)], является задача удаления невидимых линий и поверхностей. Двумерным образом
Рис. 7.1. Удаление невидимых линий.
трехмерной сцены всегда является какая-нибудь ее проекция. Однако нельзя просто спроецировать каждый из объектов на картинную плоскость, поскольку некоторые объекты могут быть частично или полностью скрыты от наблюдателя. Чтобы создать правдоподобный чертеж, необходимо удалить те линии, которые не смог бы увидеть реальный зритель. На рис. 7.1 показана сцена до и после удаления невидимых линий.
Один объект заслоняет другой, если их проекции пересекаются, поэтому определение пересечений и их построение является сердцевиной задачи удаления невидимых линий. В разработку технического обеспечения для решения этой задачи были сделаны значительные инвестиции, поскольку она особенно трудна на практике ввиду предъявляемых к графическим дисплейным системам требований работы в реальном времени и так как объекты обычно находятся в движении.
