|
BlackSem |
|
|
|
Задано:
1. множество точек на плоскости;
2. диаграмма Вороного для них (как общая коллекция отрезков).
Вопрос: определить, какие отрезки из множества под п. 2 образуют ячейку диаграммы Вороного для заданной точки из п.1
Строится диаграмма в какой то заданной прямоугольной области (то есть нет отрезков, концы которых уходят в бесконечность)
(PAV) : поправил название на более информативное
|
|
|
|
 |
|
PAV |
|
|
|
Насколько я понимаю, требуется определить границы многоугольника, в который попадает заданная точка из множества п.1.
Можно делать так. Перебираем все концы отрезков п.2, считаем расстояния до заданной точки и находим минимальное. Этот конец заведомо является вершиной искомого многоугольника.
Далее, начав с этой точки, двигаемся в одном из направлений (по часовой стрелке или против) и обходим весь искомый многоугольник. Если очередная точка, до которой мы дошли, является концом ровно двух отрезков, то все просто - оба они входят в искомый многоугольник, по одному пришли, по второму идем дальше. Если же отрезков с концом в заданной точке больше двух, то нужно определить, в какой сектор плоскости, на которые ее делят соответствующие лучи, попадает искомая точка.
|
|
|
|
|
|
PAV |
|
|
|
Уточнение. Конечно же, никакая точка не может быть концом только двух отрезков, их всегда как минимум три. Так что в каждой точке нужно именно решить, по какому пути двигаться дальше. Ну и отдельный алгоритм должен быть для первой точки, так как с нее мы начинаем и у нас еще нет предыдущей точки.
|
|
|
|
|
