Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Полиэдр называется простым, если никакая пара несмежных его граней не имеет общих точек. Простой полиэдр разбивает пространство на две непересекающиеся области — внутреннюю (конечную) и внешнюю (бесконечную). (И опять, в обиходе термин «полиэдр» часто используется для обозначения объединения границы и внутренней области.)
Поверхность любого полиэдра (рода нуль) изоморфна пла-нарному подразбиению. Поэтому числа v, е и f соответственно для его вершин, ребер и граней удовлетворяют формуле Эйлера (1.1).
Простой полиэдр называется выпуклым, если его внутренняя область является выпуклым множеством.
1.3. Геометрические предпосылки
1.3.3. Геометрическая двойственность. Поляритет
Теперь рассмотрим другую интерпретацию преобразования (1.8), вновь для простоты на примере d = 2. Итак, мы видели, что (1.8) отображает точки в точки, а прямые в прямые Е2, т. е. это преобразование сохраняет размерность отображаемых объектов. Предполагая, что \В\Ф0, перепишем (1.8) в виде
ri-ifi (1.9)
и далее будем считать, что векторы, обозначенные через %, представляют направление (т. е. прямую, проходящую через начало координат), а векторы, обозначенные через ц, представляют нормаль к плоскости, проходящую через начало координат. Поэтому соотношение (1.9) интерпретируется как преобразование в Е3, переводящее прямую (представленную %) в плоскость (представленную ц) и называемое корреляцией. Это частный случай (при d = 2) общего свойства: в пространстве Ed+l, по которому соотношение (1.9) отображает линейное многообразие размерности s ^ d + 1 в двойственное ему многообразие размерности d-f-1 — s; в такой интерпретации (1.9) называется преобразованием двойственности и, действительно, та же самая матрица В может использоваться для описания корреляции, которая переводит плоскости в прямые линии. Для заданной корреляции, описываемой матрицей В и переводящей прямую в плоскость, мы хотим найти корреляцию, описываемую матрицей D и переводящую плоскость в прямую, так чтобы пара (В, D) сохраняла инцидентность, т. е. если прямая % принадлежит плоскости т], то прямая ir|Z> принадлежит плоскости \В. Очевидно, что прямая % принадлежит плоскости т| тогда и только тогда, когда
Irf = 0. Поэтому потребуем, чтобы
|B(TiD)r = iBDV = 0.
Поскольку последнее уравнение должно выполняться для любых % и ц, мы получаем BDT = kl, или
D = k(B-l)T,
где k — некоторая константа.
Заметим, что произведение BD переводит прямые в прямые, а плоскости в плоскости. Теперь для заданной пары (В, (В-1)7), сохраняющей инцидентность, потребуем, чтобы произведение В ¦ (В~1)т переводило каждую прямую и каждую плоскость в самих себя, т. е. потребуем, чтобы В - (В-1)7" = kl, или, что
40
Г л. 1. Введение
то же самое, В = kBT. В последнем равенстве нужно, чтобы k = ±1; особенно интересен случай, когда
т. е. В — невырожденная, симметричная матрица третьего порядка.
Теперь рассмотрим результат действия корреляции аналогичной (1.9) при центральном проецировании на плоскость х3= 1. Видно, что точки переходят в прямые, а прямые — в точки.
Рис. 1.6. Иллюстрация соответствия между полюсом и полярой при полярном преобразовании по отношению к единичной окружности.
Остаток этого раздела будет посвящен анализу этого отображения в Е2; через % будем обозначать точки, а через tj — прямые. Если матрица В третьего порядка удовлетворяет условию В — Вт, то, полагая х = (х\, х2, хъ), получаем хорошо известное соотношение [Birkhoff, MacLane (1965)]
это соотношение в однородных координатах задает коническое сечение на плоскости (известное как коника, заданная В). Возьмем фиксированный вектор % (представляющий точку на плоскости в однородных координатах) такой, что %В%Т = 0. По определению точка % лежит на конике, заданной В; если назвать точку % полюсом, а прямую §Вхг полярой для §, то увидим, что полюс на конике инцидентен своей собственной поляре. Такое преобразование точек в прямые и наоборот, называемое поляритетом, полезно при создании геометрических алгоритмов. Это связано с тем, что интуитивно нам удобнее ра-
В = ВТ,
(1.10)
хВхт = 0;
1.4. Модели вычислений
41
ботать с точками, чем с прямыми (в Е2) или плоскостями (в ?3), и мы используем эту возможность в следующих главах.
В частности, пусть В — матрица, определяющая единичную окружность на плоскости Е2 (рис. 1.6). В этом случае
поэтому точка р = (pi, р2, 1) отображается в прямую /, уравнение которой имеет вид р^Х\ + р2х2 — х3 = О (в однородных координатах). Расстояние от р до начала координат этой плоскости равно д/р2 + р\, а расстояние от / до этого начала координат равно l/д/р2 + р2,. Значит, в этом частном случае поляритета:
расстояние(р, 0) X расстояние(поляра (р),0) = 1. Отметим также, что при этом поляритете преобразование не связано ни с какими вычислениями, просто по-разному интерпретируется тройка (pi, р2, р3): в одном случае — как координаты (pi/рз, Pi/рг) точки, а в другом — как коэффициенты уравнения прямой р\Хх-\-р2х2—рзх$=0 в однородных координатах.
