Изменения

Перейти к: навигация, поиск

Диаграмма Вороного

43 байта добавлено, 15:08, 14 мая 2015
Алгоритм
=== Алгоритм ===
Чтобы найти farthest-point диаграмму, сначала найдём выпуклую оболочку всех сайтов. Обозначим сайты, её образующие, через <tex>p_1, p_2, ..., p_m</tex>. Запомним порядки обхода для каждой вершины выпуклой оболочки по часовой стрелке (<tex>cw(p_i)</tex>) и против часовой (<tex>ccw(p_i)</tex>) и сделаем случайную перестановку точек. Далее удаляем из выпуклой оболочки все точки, кроме первых трёх (запоминая при этом их соседей в оболочке на момент удаления). После этого мы строим farthest-point диаграмму для первых трёх точек (пересекая полуплоскости) и последовательно добавляем остальные (удалённые) в порядке, обратном порядку удаления.
{|
418
правок

Навигация