Алгоритм кластеризации 2D точек в разложение ограничивающего прямоугольника

Question

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

Я уже пытался работать с K-Means но это не дает мне полезных результатов, так как мне нужно уже знать, сколько кластеров мне нужно.

Answer 1

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

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