Цитата:
|
но как осуществляется эта проверка?
|
не проверял, но вроде должно быть верно:
-Выбираем точку из множества
-Ставим затравку, считая, что ячейкой Вороного для данной точки будет вся плоскость.
-Проводим отрезки от точки до всех остальных точек множества
к каждому отрезку проводим серединный перпендикуляр
-Каждый перпендекуляр разбивает плоскость на 2 полуплоскости, надо выбрать ту полуплоскость где НЕ находится наша точка и вычесть полученное множество из текущей ячейки, т.о. на каждом шаге ячейка по площади будет становится все меньше и после обработки последнего отрезка получим готовую ячейку Вороного для данной точки.
Далее повторяем вышенаписаное для всех точек множества.
Цитата:
|
И как описываются эти зоны, чтобы потом можно было осуществлять проверки?
|
ячейка Вороного описывается набором конечных и полубесконечных отрезков, определить принадлежность точки такой ячейке вопрос чисто технический.