Введение
В последние годы, всвязи с применением многогранников Вороного и симплексов Делоне в самыхразличных науках, появляется интерес к истории возникновения этихгеометрических построений. В ходе нашей работы мы рассмотрим математическуюсторону метода Делоне, обсудим идеи и основные результаты. Как известно, БорисНиколаевич был одним из учеников известного математика Г.Ф. Вороного. И поэтомурезультаты работ Делоне очень тесно связаны с методами Вороного.
Существует довольномного областей наук, где используются методы этих двух замечательныхматематиков. Кроме физики, математики и химии можно отметить наиболееизвестные: астрономию (изучение структуры Вселенной), экономику (методыоптимизации), картографию, экологию и компьютерную графику. Но все же главнымполем применения методов в наше время являются математические науки.
Следует рассказать ободной простой, но важной теории, которую Борис Николаевич начал еще в начале 1920-хгодов, — о так называемом методе пустого шара и связанном с ним разбиении пространствана специальные многогранники. Где-то в 1980-е годы, уже после смерти Б. Н. Делоне,эти разбиения получили название «триангуляции Делоне».
В нашей работе мы исследовалиодин из его методов – построение круга Делоне для трех многоугольников, а такжевычисление радиуса и центра круга.
Раздел 1 Основныерезультаты работ Делоне
Борис Николаевич Делонепрожил долгую и плодотворную жизнь, внеся свой вклад в теорию чисел, алгебру и геометрию,а также воспитав многих выдающихся учеников. Делоне был чрезвычайно одаренным человеком,неутомимым альпинистом, талантливым педагогом. Заслуга Делоне еще в том, что онмог изложить фундаментальные математические результаты, как свои, так и других авторов,простым и наглядным языком, понятным не только математикам.
Работы Делоне тесно связаныс результатами работ Вороного. Классические результаты Вороного и Делоне полученыдля систем точек (центров). Объектом нашего исследования является система точек,произвольно расположенных в пространстве. Наши точки обособлены одна от другой,и в системе точек нет бесконечно больших пустот. Делоне сформулировал это следующимобразом:
a) Можноуказать некоторый конечный радиус (пусть даже очень маленький), такой, что внутрисферы этого радиуса, построенной вокруг любой точки системы, нет других точек, принадлежащихданной системе.
b) Можноуказать другой конечный радиус (пусть даже очень большой), такой, что внутри сферыэтого радиуса, расположенной в любом месте нашей системы, всегда найдется хотя быодна точка системы.
Никаких других ограниченийнет. Точки могут располагаться как упорядоченно, так и случайно. Будем обозначатьтакую систему как {А}, поскольку наши точки обычно являются центрами атомов.
2 Разбиение Делоне 2.1 Метод пустого шара Делоне. Симплекс Делоне
Воспользуемся пустым шаром,который мы будем перемещать, изменяя его размер так, чтобы он мог касаться точексистемы {А}, но всегда оставался пустым.
Итак, поместим в системуточек {А} пустой шар Делоне. Это всегда возможно, если выбрать шар достаточно малым.Начнем увеличивать его радиус, оставляя центр шара на месте. В какой-то момент поверхностьшара встретит некоторую точку i системы {А}. Это обязательно произойдет, ибо в нашейсистеме нет неограниченно больших пустот. Будем продолжать увеличивать радиус пустогошара так, чтобы точка i оставалась на его поверхности. Для этого придется двигатьцентр шара от точки i. Рано или поздно шар достигнет своей поверхностью другой точкисистемы {А}.
/>
Рисунок 2.1 – РазбиениеДелоне двумерной системы точек
Симплексы Делоне заполняютпространство без щелей и наложений.
Описанная сфера любого симплексане содержит внутри себя других точек системы.
Пусть это будет точка j.Продолжим увеличивать радиус нашего шара, сохраняя уже обе точки на его поверхности.Увеличиваясь, шар достигнет какой-то третьей точки системы, точки k. В двумерномслучае наш «пустой круг» в этот момент зафиксируется, т.е. станет невозможным дальнейшееувеличение его радиуса при сохранении круга пустым. При этом мы выявляем элементарнуюдвумерную конфигурацию трех точек (i,j,k), определяющую некий треугольник, особенностьюкоторого является то, что внутри его описанной окружности нет других точек системы{А}. В трехмерном пространстве шар не определяется тремя точками. Продолжим увеличиватьего радиус, сохраняя все три найденные точки на его поверхности. Это будет возможнодо тех пор, пока поверхность шара не встретится с четвертой точкой l системы. Послеэтого движение и рост пустого шара станут невозможными. Найденные четыре точки (i,j,k,l)определяют вершины тетраэдра, который характерен тем, что внутри его описанной сферынет других точек системы {А}. Такой тетраэдр называется симплексом Делоне.
Симплексом в математикеназывают простейшую фигуру в пространстве данной размерности: тетраэдр – в трехмерномпространстве; треугольник – в двумерном. Произвольная тройка (четверка) точек системы,не лежащих в одной плоскости, всегда определяет некий симплекс. Однако он будетсимплексом Делоне только с том случае, если его описанная сфера пуста. Другими словами,симплексы Делоне определяются особым выбором троек (четверок) точек в системе {А}.
Мы построили один симплексДелоне, однако, помещая пустой шар в различные места и повторяя ту же процедуру,можно определить и другие. Утверждается, что совокупность всех симплексов Делонесистемы {А} заполняет пространство без наложений и щелей, т.е. реализует разбиениепространства, но на этот раз на тетраэдры. Это разбиение называется разбиением Делоне(рисунок 1).2.2 Вырождение
Мы ограничились тем фактом,что ровно четыре точки в пространстве фиксируют пустой шар. В общем случае возможно,чтоб на его поверхности оказалось больше, чем четыре точки системы. Например, еслиимеется октаэдрическая конфигурация точек, то на поверхности вписанного шара будетлежать шесть точек – вершин октаэдра, а если кубическая, то восемь. Можно представитьпроизвольную конфигурацию любого числа точек, лежащих на одной сфере. Все такиеконфигурации, если они имеются в системе, будут выявляться с помощью пустого шараДелоне. Если мы наткнулись поверхностью шара сразу на несколько точек системы {А},то при дальнейшем увеличении радиуса будем сохранять их всех на его поверхности.Рано или поздно мы упремся в последнюю точку (или точки), которая остановит движениенашего пустого шара.
Итак, если на поверхностипустого шара оказалось более четырех точек, будем их рассматривать как вершины некоегонесимплициального многогранника. Будем называть такой многогранник несимплициальнымполиэдром Делоне. Любой несимплициальный полиэдр Делоне может быть разбит на симплексыДелоне. Однако сделать это можно различными способами. В двумерном случае для многоугольникас N вершинами может реализоваться /> (число сочетанийиз N по три) различных симплексов. Каждое конкретное разбиение содержит всегда N-2симплекса. В трехмерном пространстве можно построить /> различных симплексов(рисунок 2). Однако, в отличии от двумерного случая, здесь в разных конкретных разбиенияхможет быть различное число симплексов.
/>
Рисунок 2 – Различные разложениядвумерного несимплициального полиэдра на симплексы
Любой Х-угольник разбиваетсявсегда на N-2 симплекса
Систему {A} будем называтьвырожденной, если в ней имеется хотя бы один несимплициальный полиэдр Делоне, т.е.хотя бы один раз на поверхности пустого шара оказывается более четырех точек системы.Если нет ни одной такой конфигурации, то система называется невырожденной.
3 Теорема о разбиении Делоне
Теорема: Полиэдры Делонесистемы {A} не входят друг в друга и заполняют все пространство, будучи смежнымипо целым граням. Разбиение пространства на полиэдры Делоне однозначно определяетсясистемой {A} и, обратно, однозначно ее определяет.
Покажем, что полиэдры Делонене входят друг в друга. Возьмем какие-либо два полиэдра Делоне системы {A}, обозначимих как D1 и D2, а описанные вокруг них сферы S1 и S2. Если S1 и S2 не пересекаются,то полиэдры D1 и D2 также не имеют общих точек и поэтому не входят друг в друга.Если же S1 и S2 пересекаются, то все вершины полиэдра D1 всегда лежат на той «шапочке»сферы S1, которая расположена вне сферы S2, поскольку по условию сфера S2 пуста(рисунок 3). Точно так же рассуждая, приходим к тому, что вершины полиэдра D2 лежатна той «шапочке» сферы S2, которая располагается вне сферы S1. Следовательно, вершиныполиэдров D1 и D2 всегда лежат по разные стороны от хордальной плоскости этих сферили, возможно, частично на ней самой. Это означает, что все точки полиэдров D1 иD2 должны лежать по разные стороны от этой плоскости, ибо все полиэдры Делоне –выпуклые многогранники. Отсюда следует, что никакие из них не входят друг в друга,но, возможно, касаются своими поверхностями.
Нужно убедиться, что полиэдрыДелоне могут соприкасаться только по целым граням. Возьмем произвольную грань некоторогополиэдра D. Станем двигать центр описанной вокруг него сферы по направлению из полиэдраперпендикулярно этой грани.
разбиениесимплекс делоне круг
/>
Рисунок 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
/>; 1 0 0 0
/>. 1 0 0 0
/>. 1 0 0 0
/>; 1 2 0 0
/>; 2 4 0 0
/>; 2 4 0 0
/>; 1 2 0 0
/>; 1 2 0 0
/>; 1 2 0 0
/>; 1 2 0 0
/>; /> 2 3 0 1
/>; 1 2 0 0
/>; 1 2 0 0
/>, />; 1 2 0 1
/>, />; 1 1 1 1
/> 1 0 0 0
/>; 2 2 0 0
/>. 2 2 0 0
26 32 1 3
+ * /> if
5 Описание работы программы
Создаем в оболочкеWPF три круга которые можно передвигать при помощи нажатия левой кнопки мыши с1,с2, с3. И два круга которые будут прорисовываться в результате вычисления формулс4 и с5.
xmlns=«schemas.microsoft.com/winfx/2006/xaml/presentation»
xmlns:x=«schemas.microsoft.com/winfx/2006/xaml»
Title=«MainWindow»Height=«350» Width=«525» KeyDown=«Window_KeyDown»xmlns:chartingToolkit=«clr-namespace:System.Windows.Controls.DataVisualization.Charting;assembly=System.Windows.Controls.DataVisualization.Toolkit»MouseWheel=«Window_MouseWheel»>
Stroke=«Black»/>
Создаемпеременные для начальных координат Х и У, для события если мышь нажата, и для выгибаниякруга.
doublebeginX = 0;
doublebeginY = 0;
boolisMouseDown = false;
Shapeshape;
Несколькофункций для подкрепления рисунка с работой мыши.
privatevoid Ellipse_MouseLeftButtonDown(object sender, MouseButtonEventArgs e)
{
shape= (Shape)sender;
Ellipseb = sender as Ellipse;
beginX= e.GetPosition(this).X;
beginY= e.GetPosition(this).Y;
isMouseDown= true;
b.Opacity= 0.5;
b.SetValue(Canvas.ZIndexProperty,1);
b.CaptureMouse();
}
privatevoid Ellipse_MouseLeftButtonUp(object sender, MouseButtonEventArgs e)
{
Ellipseb = sender as Ellipse;
isMouseDown= false;
b.Opacity= 1.0;
b.SetValue(Canvas.ZIndexProperty,0);
b.ReleaseMouseCapture();
}
privatevoid Ellipse_MouseMove(object sender, MouseEventArgs e)
{
if(isMouseDown)
{
Ellipseb = sender as Ellipse;
doublecurrX = e.GetPosition(this).X;
doublecurrY = e.GetPosition(this).Y;
doubleleft = (double)b.GetValue(Canvas.LeftProperty);
doubletop = (double)b.GetValue(Canvas.TopProperty);
b.SetValue(Canvas.LeftProperty,left + currX — beginX);
b.SetValue(Canvas.TopProperty,top + currY — beginY);
beginX= currX;
beginY= currY;
ReCalclateDeloneCircle();
}
}
privatevoid Window_KeyDown(object sender, KeyEventArgs e)
{
switch(e.Key)
{
caseKey.Left:
shape.SetValue(Canvas.LeftProperty,(double)shape.GetValue(Canvas.LeftProperty) — 1);
break;
caseKey.Right:
shape.SetValue(Canvas.LeftProperty,(double)shape.GetValue(Canvas.LeftProperty) + 1);
break;
caseKey.Up:
shape.SetValue(Canvas.TopProperty,(double)shape.GetValue(Canvas.TopProperty) — 1);
break;
caseKey.Down:
shape.SetValue(Canvas.TopProperty,(double)shape.GetValue(Canvas.TopProperty) + 1);
break;
caseKey.PageUp:
shape.SetValue(Canvas.LeftProperty,(double)shape.GetValue(Canvas.LeftProperty) — 1);
shape.SetValue(Canvas.TopProperty,(double)shape.GetValue(Canvas.TopProperty) — 1);
shape.Width+= 2;
shape.Height+= 2;
break;
caseKey.PageDown:
if(shape.Width — 2 >= 0)
{
shape.SetValue(Canvas.LeftProperty,(double)shape.GetValue(Canvas.LeftProperty) + 1);
shape.SetValue(Canvas.TopProperty,(double)shape.GetValue(Canvas.TopProperty) + 1);
shape.Width-= 2;
shape.Height-= 2;
}
break;
caseKey.Tab:
if(shape == c1)
shape= c2;
else
if(shape == c2)
shape= c3;
else
shape= c1;
break;
caseKey.Escape:
Close();
break;
}
ReCalclateDeloneCircle();
}
privatevoid Window_MouseWheel(object sender, MouseWheelEventArgs e)
{
intk = Math.Abs(e.Delta) / e.Delta;
if(shape.Width + 2 * k >= 0)
{
shape.SetValue(Canvas.LeftProperty,(double)shape.GetValue(Canvas.LeftProperty) — k);
shape.SetValue(Canvas.TopProperty,(double)shape.GetValue(Canvas.TopProperty) — k);
shape.Width+= 2 * k;
shape.Height+= 2 * k;
}
ReCalclateDeloneCircle();
}
Функциидля определения радиусов кругов Делоне, и для переопределения по мере передвижениякругов по рабочему окну.
privatevoid ReCalclateDeloneCircle()
{
doubler1 = c1.Width / 2;
doublex1 = (double)c1.GetValue(Canvas.LeftProperty) + r1;
doubley1 = (double)c1.GetValue(Canvas.TopProperty) + r1;
doubler2 = c2.Width / 2;
doublex2 = (double)c2.GetValue(Canvas.LeftProperty) + r2;
doubley2 = (double)c2.GetValue(Canvas.TopProperty) + r2;
doubler3 = c3.Width / 2;
doublex3 = (double)c3.GetValue(Canvas.LeftProperty) + r3;
doubley3 = (double)c3.GetValue(Canvas.TopProperty) + r3;
doublex4, y4, r4, x5, y5, r5;
CalclateDeloneCircle(x1,y1, r1, x2, y2, r2, x3, y3, r3, out x4, out y4, out r4, out x5, out y5, out r5);
r4= Math.Abs(r4);
if(!double.IsInfinity(r4))
{
c4.SetValue(Canvas.LeftProperty,x4 — r4);
c4.SetValue(Canvas.TopProperty,y4 — r4);
c4.Width= 2 * r4;
c4.Height= 2 * r4;
}
r5= Math.Abs(r5);
if(!double.IsInfinity(r4))
{
c5.SetValue(Canvas.LeftProperty,x5 — r5);
c5.SetValue(Canvas.TopProperty,y5 — r5);
c5.Width= 2 * r5;
c5.Height= 2 * r5;
}
}
privatevoid CalclateDeloneCircle(
doublex1, double y1, double r1,
doublex2, double y2, double r2,
doublex3, double y3, double r3,
outdouble x4, out double y4, out double r4,
outdouble x5, out double y5, out double r5)
{
doublex21 = x2 — x1;
doubley21 = y2 — y1;
doubler21 = r2 — r1;
doublex31 = x3 — x1;
doubley31 = y3 — y1;
doubler31 = r3 — r1;
doubleXY = x21 * y31 — x31 * y21;
if(XY == 0)
{
x4= double.NaN;
y4= double.NaN;
r4= double.NaN;
x5= double.NaN;
y5= double.NaN;
r5= double.NaN;
return;
}
doublez21 = (x21 * x21 + y21 * y21 — r21 * r21) / 2;
doublez31 = (x31 * x31 + y31 * y31 — r31 * r31) / 2;
doubleAx = y21 * r31 — y31 * r21;
doubleAy = -(x21 * r31 — x31 * r21);
doubleBx = -(y21 * z31 — y31 * z21);
doubleBy = x21 * z31 — x31 * z21;
doubleA = Ax * Ax + Ay * Ay — XY * XY;
doubleB = Ax * Bx + Ay * By;
doubleC = Bx * Bx + By * By;
doubleD = B * B — A * C;
if(D
{
x4= double.NaN;
y4= double.NaN;
r4= double.NaN;
x5= double.NaN;
y5= double.NaN;
r5= double.NaN;
return;
}
doubleR;
R= (-B — Math.Sqrt(D)) / A;
r4= R — r1;
y4= (Ay * R + By) / XY + y1;
x4= (Ax * R + Bx) / XY + x1;
R= (-B + Math.Sqrt(D)) / A;
r5= R — r1;
y5= (Ay * R + By) / XY + y1;
x5= (Ax * R + Bx) / XY + x1;
}
6.Вид рабочего приложения
/>
Рис.6.1
/>
Раис 6.2
ВЫВОДЫ
Данная программа демонстрируетвозможности программирования с помощью технологии Microsoft Windows PresentationFoundation. В этой программе наглядно показано новшества, которые WPF внесло в программированиеWindows приложений, а именно: новое визуальное оформление, новая философия настройкиэлементов, новые графические средства и новый программный интерфейс.WPF состоитиз двух взаимосвязанных программных интерфейсов. Программы WPF могут быть полностьюнаписаны на C# или любом другом языке программирования, компилируемом в соответствиис правилами .NET CLS(Common Language Specification). Кроме того, WPF содержит новыйязык разметки на базе XML, называемый XAML( eXtensible Application Markup Language).Вотдельных случая на XAML можно написать целую программу, однако это приложение построенокак из программного кода, так и из кода разметки. В этой программе XAML используетсядля определения пользовательского интерфейса, а программный код – для обработкисобытий. Подводя итоги можно сказать, что данная программа показывает преимуществатехнологии WPF над технологией Windows Forms.
Список литературы
1. МедведевН.Н. Метод Вороного – Делоне в исследовании структуры некристаллических систем /РАН, Сиб. отд-ние, РФФИ, Институт химической кинетики и горения СО РАН. Новосибирск:НИЦ ОИГГМ СО РАН, Издательство СО РАН, 2000, 214 с.