Как разделить плоскость

Допустим, у меня есть фиксированное количество (X) точек, например. координаты в заданной плоскости (я думаю, вы можете назвать это двумерным облаком точек).

Эти точки должны быть разделены на многоугольники Y, где Y ‹ X. Многоугольники не должны перекрываться. Было бы замечательно, если бы многоугольники были выпуклыми (как диаграмма Вороного).

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

Я подумал о создании сетки, которая покрывает точки. Затем выполните итерацию по точкам, назначая их ближайшим ячейкам сетки.

Может я упускаю очевидное? Я уверен, что есть лучшие решения.

Спасибо, Даниэль

Я только что нашел оптимизацию (kmeans++). Возможно, это даст лучший результат полученные результаты..


coordinates polygon plane
person puls200    schedule 12.08.2009    source источник
comment
С сеткой вы можете получить пустые ячейки или все точки в одной ячейке. С радиальным массивом вы можете решить эту проблему с помощью решения, которое можно быстро и легко реализовать.   -  person SmacL    schedule 12.08.2009

Ответы (3)


arrow_upward
1
arrow_downward

Вы упомянули диаграмму Вороного, смотрели ли вы связанные с ней алгоритмы тесселяции? Если да, не могли бы вы подчеркнуть, почему они не работают для вас?

person Henk Holterman    schedule 12.08.2009
comment
Диаграммы Вороного имеют одну точку на многоугольник, однако здесь любое количество точек должно составлять многоугольник. Что я забыл упомянуть: я также пробовал алгоритм Ллойда (k-means), но результат слишком сильно зависит от начального выбора ... сходимость, как правило, не слишком хорошая. - person puls200; 12.08.2009

arrow_upward
0
arrow_downward

Вероятно, вам нужно лучше определить, какие критерии вы хотите использовать для создания полигональных разделов. Например, если это близость, вы можете сделать следующее;

  • Построить диаграмму Вороного.
  • Там, где любые два смежных полигона имеют близкого соседа, объединить их в один полигон.
  • Повторяйте, пока не получите нужное количество полигонов.

Если бы это было равное количество точек на полигон, вы могли бы сделать что-то подобное на основе слияния соседних полигонов до тех пор, пока не будет достигнуто желаемое количество точек.

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

person SmacL    schedule 12.08.2009

arrow_upward
0
arrow_downward

Может быть полезно Разбиение 2D-многоугольников< /а>

person Alin    schedule 12.08.2009