Ломаю голову... (диаграмма Вороного)

[BlackSem]

Задано:
1. множество точек на плоскости;
2. диаграмма Вороного для них (как общая коллекция отрезков).
Вопрос: определить, какие отрезки из множества под п. 2 образуют ячейку диаграммы Вороного для заданной точки из п.1

Строится диаграмма в какой то заданной прямоугольной области (то есть нет отрезков, концы которых уходят в бесконечность)

(PAV) : поправил название на более информативное

[PAV]

Насколько я понимаю, требуется определить границы многоугольника, в который попадает заданная точка из множества п.1.

Можно делать так. Перебираем все концы отрезков п.2, считаем расстояния до заданной точки и находим минимальное. Этот конец заведомо является вершиной искомого многоугольника.

Далее, начав с этой точки, двигаемся в одном из направлений (по часовой стрелке или против) и обходим весь искомый многоугольник. Если очередная точка, до которой мы дошли, является концом ровно двух отрезков, то все просто - оба они входят в искомый многоугольник, по одному пришли, по второму идем дальше. Если же отрезков с концом в заданной точке больше двух, то нужно определить, в какой сектор плоскости, на которые ее делят соответствующие лучи, попадает искомая точка.

[PAV]

Уточнение. Конечно же, никакая точка не может быть концом только двух отрезков, их всегда как минимум три. Так что в каждой точке нужно именно решить, по какому пути двигаться дальше. Ну и отдельный алгоритм должен быть для первой точки, так как с нее мы начинаем и у нас еще нет предыдущей точки.