Page 98 - 4204

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

Тут M( i M ) , M( i M ) – координати вектора M i M , а x , y –
ij
ij
x
j
j
j
y
координати середини відрізка M i M .
j
Приклад. Записати рівняння сторін та знайти вершини діаграми Во-
роного для точок тріангуляції M , 1 ( ) 4 , M , 7 ( ) 2 , M ) 8 , 1 ( .
1 2 3

1) Знаходимо середини відрізків M ) 3 , 4 ( , M , 1 ( ) 6
12 13
2) Знаходимо координати векторів M M  , 6 (  ) 2 , M M  , 0 ( ) 4
1 2 1 3

3) Розв’язуємо систему рівнянь

(M 1 M 2 x (x  x 12 )  (M 1 M 2 ) y (y  y 12 )  ,0  (6 x  )4  (2 y  )3  ,0   4x  (2 6 / ) 3  ,5
)
    
)
)
 (M 1 M 3 x (x  x 13 )  (M 1 M 3 x (y  y 13 )  .0  ( 0 x  )1  (4 y  )6  .0  y  .6
Тобто внутрішня вершина діаграми, що відповідає точкам M , M , M
1 2 3
буде P , 5 ( ) 6 .
0
Зауважимо, що через точку P , 5 ( ) 6 буде проходити і третя сторона
0

діаграми (третій серединний перпендикуляр трикутника M M M ).
1 2 3

(M M ) (  xx )  (M M ) (  yy )  0   ( 6 x  ) 4  ( 6 y  ) 5  0.
2 3 x 23 2 3 y 23

 5 ( 6  ) 4  6 ( 6  ) 5  0  6  1 6  1 0.

Для визначення координат зовнішніх вершин використовується рів-

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

межі. Наприклад для прямокутної області з сторонами паралельними до

c
осей координат межа буде визначатися рівняннями x  , x  , y  ,
a
b
y  d . Тоді система рівнянь для визначення координати вершини діаграми,

c
розміщеної на перетині сторони M M і межі y  буде
2
1
(M M ) (x  x )  (M M ) (y  y )  ,0
 1 2 x 12 1 2 y 12
 y  .c

(M 1 M 2 y
)
Звідки легко отримується значення x  x  (c  y 12 ).
12
(M 1 M 2 x
)
За аналогією отримують координати інших зовнішніх вершин діаграми.

97