Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Переписав уравнение (6.1) в однородных координатах и применив преобразование (6.2), получим уравнение для ср(С) в однородных координатах:
12 + Щ + Ц=%К (6.3)
Переходя вновь к неоднородным координатам | == |i/|4, Л = = l2/h и Z = h/U, получаем уравнение для ср(С) в неоднородных координатах:
? = I2 -г- П2 + 1. (6.4)
которое описывает параболоид вращения 9>.
В дополнение к тому, что нам требовалось, преобразование
<р отображает плоскость z
= 1, единичную
Рис.
отображает диаграм!
i диаграмму (Ь).
сферу в гиперболоид с уравнением |2 + л2 — ?2+ 1 = 0 и точку начала координат в бесконечно удаленную точку по g-оси. В итоге диаграмма, приведенная на рис. 6.12 и повторенная на рис. 6.13(a), отображается при применении преобразования q> в диаграмму, представленную на рис. 6.13(b). Рассмотрим те-
6.3. Обобщения диаграммы
303
перь образы при преобразовании ф пар точек, лежащих соответственно на С и на плоскости г= 1, являющихся образами друг друга при преобразовании инверсии. Эти новые точки, лежащие соответственно на & и на плоскости ?= 1, теперь получаются простым проецированием параллельно ?-оси (по вертикали). Обозначим эту вертикальную проекцию у: =
Пусть снова S —это конечное множество точек, лежащих в плоскости ?=1, a S'= {у{р): peS}. Пусть рх и р2 — две произвольные точки из множества 5. Рассмотрим плоскости п(р\) и я(р2), касательные к & в точках v(pi) и у(р2) соответственно. Следующая лемма указывает на одно очень важное свойство этих двух плоскостей. Доказательство леммы оставляем в качестве упражнения читателю.
Лемма 6.4. Проекция линии пересечения плоскостей n(pi) и л(р2) на плоскость ? = 1 перпендикулярна отрезку р,р2 и делит его пополам.
Предположим теперь, что уже построено множество плоскостей {л{р): ре5}. Эти плоскости разбивают пространство на ячейки {Du D2, DM}. Установим, какая связь имеется между этими ячейками и многоугольниками Вороного (некоторой диаграммы Vor^S)) на плоскости ?= 1. Для каждой точки р i= S определим полупространство HS(p), задаваемое плоскостью л(р) и лежащее вне параболоида $Р (здесь снова я(р)—это плоскость, касательная к & в точке у(р)). Рассмотрим некоторую ячейку D разбиения пространства, задаваемого множеством плоскостей (я(р): рен5}. С ячейкой D связано (единственное) множество T(D)^S, определяемое как единственное подмножество множества S такое, что
HS(р) для каждой точки ре Т(D). (См. рис. 6.14, где приведен двумерный аналог.) Пусть q' — некоторая типичная точка в D, a q — ее вертикальная проекция на плоскость ? = 1. Кроме того, пусть р, е 7(D) и p,eS-— T(D) (рис. 6.14(b)). По определению множества T(D), q'е ^HS(pi) и q' ф HS(pj). Вертикальная плоскость т, проходящая по линии пересечения плоскостей я(р,) и я(р,), определяет два полупространства. Из условия /eHS(pi) и q'ф <^HS(p/) следует, что q' лежит в полупространстве, содержащем точку р-,. С учетом леммы 6.4 получаем, что q принадлежит полуплоскости H(pi,pj), и, так как точки pi^T(D) и Pi^S — T(D) выбирались произвольно, приходим к следующему результату:
Теорема 6.9. Проекция на плоскость ? = 1 ячейки D раз-бцения пространства, определяемого множеством плоскостей
304
Гл. 6. Близость: варианты и обобщения
{п(р): peS}, является многоугольником Вороного V(T), где Т — наибольшее подмножество такое, что Z) = HS(p) для каждой точки р ез Т.
Эта теорема показывает, что определенное выше разбиение пространства дает полную информацию о семействе диаграмм
(а) (Ь)
Рис. 6.14. (а)—Двумерный аналог разбиения пространства, определяемого касательными плоскостями; (Ь) — иллюстрация к доказательству теоремы 6.9.
Вороного высших порядков. Вопрос об алгоритмах построения диаграмм Вороного будет рассмотрен в следующем разделе.
6.3.1.3. Построение диаграмм Вороного высших порядков
Для разработки необходимого алгоритма исследуем взаимосвязь между Vork(S) и Vorft+1(5). (Уместно отметить, что Vorjv-i(S) называется также диаграммой Вороного дальней точки, что вполне оправданно, так как каждый ее многоугольник представляет множество точек плоскости, более близких к одной из точек множества S—{pi} (для некоторого /), чем к точке pi, т. е. множество точек, для которых р, является самой дальней точкой множества S.)
6.3. Обобщения диаграммы
Начнем обсуждение со случая, когда множество S содержит три точки рь р2 и рз (рис. 6.15). В этом случае имеется единственная вершина диаграммы Вороного, являющаяся общей точкой трех полупрямых (лучей), перпендикулярных отрезкам, соединяющим пары точек, и делящих их пополам. Обычная диаграмма Вороного показана на рис. 6.15 сплошными линиями. Если продолжить эти полупрямые за вершину диаграммы (на рисунке это показано штриховыми линиями), то получившиеся три луча разбивают плоскость на три области так, что
Рис. 6.15. Диаграммы Вороного ближайшей и дальней точек для множества из трех точек.
каждая точка в любой из этих областей находится ближе к одной из двух заданных точек, чем к третьей точке. Таким образом, мы получили диаграмму Вороного дальней точки множества S = {рь р2, рз}-
