Page 97 - 4204

ЛЕКЦІЯ 7. ЕЛЕМЕНТИ ОБЧИСЛЮВАЛЬНОЇ ГЕОМЕТРІЇ.

Визначення сторін діаграми Вороного

Для визначення сторін діаграми Вороного використовують той

факт, що кожна сторона діаграми є серединним перпендикуляром

до однієї із сторін тріангуляції Делоне.

Тобто для двох сусідніх вузлів тріангуляції M (x , y ),
1 1 1

M (x , y ) потрібно записати рівняння прямої, що проходить че-
2 2 2

рез середину відрізка M 1 M з вектором нормалі n  M 1 M .
2
2
 x  x y  y 
Координати середини відрізка будуть M  1 2 , 1 2  , а
12
 2 2 

координати вектора нормалі n  M M  x  x , y  y . Отже,
1 2 2 1 2 1
рівняння сторони діаграми, що проходить між точками M та
1

M , запишемо так
2

(M M ) (  xx )  (M M ) (  yy )  0,
1 2 x 12 1 2 y 12

або підставивши вирази для координат середини відрізка

 x  x   y  y 
(x  x ) x 1 2   (y  y ) y 1 2   0.
2 1 2 1
 2   2 

Значення координат внутрішніх вершин полігона (діаграми)

знаходимо як координати точок перетину серединних перпенди-

кулярів. Наприклад для 3-х сусідніх точок тріангуляції M 1 (x 1 , y 1 ),

M 2 (x 2 , y 2 ), M 3 (x 3 , y 3 ) отримаємо систему лінійних рівнянь

(M 1 M 2 x (x  x 12 )  (M 1 M 2 y (y  y 12 )  ,0
)
)

)
)
 (M 1 M 3 x (x  x 13 )  (M 1 M 3 x (y  y 13 )  .0

96