Разбиение Делоне (стр. 2 из 3)

При этом будем так менять радиус сферы, чтобы вершины выбранной грани оставались на ее поверхности. Сфера сразу покинет все остальные вершины D и, в конце концов, наткнется на некоторую точку (или точки) системы {A}, лежащую вне этого полиэдра. Отсюда мы найдем новый полиэдр Делоне, который является смежным полиэдру D по целой грани (грань полностью определяется своими тремя вершинами, а мы их не меняли). Это означает, что для произвольной грани любого полиэдра Делоне всегда существует смежный по целой грани другой полиэдр Делоне этой же системы {A}.

Отсюда следует, что в системе полиэдров Делоне нет пустот. Иначе существовали бы грани, являющиеся стенками таких пустот, не покрытые другими полиэдрами систем {A}.

Если бы разбиение пространства на полиэдры Делоне было неоднозначным, то это означало бы, что в системе нашлось два нетождественных полиэдра Делоне, имеющих общие внутренние точки. Но такого не может быть, ибо как было показано, никакие полиэдры Делоне одной системы {A} не входят друг в друга.

Обратное утверждение о том, что система дискретных точек {A} однозначно определяется разбиением Делоне, следует из того, что система {A} совпадает с множеством вершин полиэдров Делоне заданного разбиения. Итак, теорема доказана.

3.1 Симплициальное разбиение (триангуляция)

Следуя первоначальной логике Б.Н. Делоне, разбиением Делоне является разбиение системы {A} на полиэдры Делоне, т.е. допускаются вырожденные конфигурации точек. Однако во всех приложениях обычно предпочитают иметь дело только с симплексами. Каких-либо общих критериев разложения вырожденной конфигурации на симплициальные не существует. Но проблемы здесь нет. Всегда можно произвести достаточно малые смещения точек вырожденной конфигурации. В результате несимплициальный полиэдр распадется на конкретные симплексы Делоне. В дальнейшем будем предполагать, что наша система {A} невырождена, т.е. разбиение Делоне однозначно представлено симплексами Делоне.

Разбиение системы точек на симплексы иногда называют триангуляцией системы. В двумерном случае это разложение системы на треугольники. В общем случае мы будем называть такое разбиение симплициальным, или просто разбиением Делоне.

Отметим, что центр описанной сферы может служить точкой, «обозначающей» соответствующий симплекс Делоне. Множество всех таких центров будем называть системой {D}. Из теоремы о разбиении Делоне следует, что система {A} однозначно определяет систему {D} и наоборот, имея {D}, можно однозначно восстановить {A}.

3.2 Особенности взаимного расположения симплексов Делоне

Симплексы Делоне могут быть произвольной формы. Однако их взаимное расположение в составе разбиения Делоне подчиняется определенным требованиям. Отметим, что центр описанной сферы симплекса Делоне может располагаться как внутри, так и вне симплекса, хотя на первый взгляд кажется, что центр всегда должен быть внутри симплекса. Будем называть симплекс закрытым, если центр его описанной сферы лежит внутри симплекса (рисунок 4,а). Если центр вне симплекса , то такой симплекс назовем открытым (рисунок 4,а). Возможна ситуация, когда центр описанной сферы лежит точно на поверхности симплекса, в частности, на грани или ребре. Такие симплексы называются полуоткрытыми (рисунок 4,а). Заметим, что все вершины открытых и полуоткрытых симплексов лежат на одной полусфере. Грань симплекса назовем закрытой, если центр описанной сферы лежит по ту же сторону от плоскости этой грани, что и сам симплекс. Аналогично грань симплекса назовем открытой, если центр описанной сферы симплекса лежит по другую сторону от плоскости этой грани, чем сам симплекс. Открытый симплекс всегда имеет открытую грань.

Рисунок 4 – Центр описанной сферы симплекса может располагаться: а внутри; б – вне; в – на границе симплекса

Соответствующие симплексы называются закрытыми, открытыми и полуоткрытыми. Вне вершины открытых и полуоткрытых симплексов лежат на одной полусфере описанной сферы.

4. Алгоритм построения круга Делоне

Найдём пересечение трёх окружностей (одну точку), центры которых совпадают с данными, а радиусы увеличены на одинаковую величину

Перенесём начало координат в центр первой окружности

; ;

, где

; ;

; ; .

Отнимем от 2-го и 3-го уравнения 1-ое

Раскроем скобки, удалив при этом квадраты

, где

; .

Найдём

и , умножив на соответствующие коэффициенты и найдя разницу уравнений

где

, , .

где

, , .

, где , , .

, где .

Последовательный расчёт

+ *

if

; 1 0 0 0

; 1 0 0 0

; 1 0 0 0