История изменений
Исправление
Eddy_Em,
(текущая версия)
:
Если расстояние между точками достаточно мало по сравнению с характерными размерами фигуры, можно вычленить связи (правда, долго придется перебирать) между соседними точками. Если каждая точка имеет лишь двух соседей, фигура не является самопересекающейся — сортировка по φ элементарно решает задачу. Если же есть точки с бóльшим числом связей, нужно будет разбить фигуру на более простые, а потом уже сортировать.
Еще я про Вороного вспомнил и связанного с ним де Лоне.
Исходная версия
Eddy_Em,
:
Если расстояние между точками достаточно мало по сравнению с характерными размерами фигуры, можно вычленить связи (правда, долго придется перебирать) между соседними точками. Если каждая точка имеет лишь двух соседей, фигура не является самопересекающейся — сортировка по φ элементарно решает задачу. Если же есть точки с бóльшим числом связей, нужно будет разбить фигуру на более простые, а потом уже сортировать.