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

Question

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

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

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

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

Возможно, я пропустил очевидное? Я уверен, что есть лучшие решения.

Спасибо, Daniel

Я только что нашел an optimization (kmeans++) .Maybe это даст лучшие результаты ..

Answer 1

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

Answer 2

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

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

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

Edit: Если выпуклость была самым важным вопросом, вы могли бы просто взять точку в середине вы облако и радиалы проекта к краю, чтобы разделить облако на радиальную массив треугольников.

Answer 3

Может быть полезно 2D Polygon Partitioning