Заполните многоугольник меньшими фигурами (кругами)

Я просто попытаюсь объяснить свою проблему с изображениями:

Программа получает ввод (изображение):

введите здесь описание изображения

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

введите здесь описание изображения

Вывод должен выглядеть примерно так:

введите здесь описание изображения

Нет правильного результата, есть только хорошие и плохие.

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

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


person Jaka Konda    schedule 28.02.2016    source источник


Ответы (1)


Я использовал кластеризацию k-means, чтобы найти центры кругов. Количество кластеров рассчитывается:

numberOfClusters = round(polygonArea / basePolygonArea).

Входными данными для алгоритма k-средних являются точки белых пикселей.

person Jaka Konda    schedule 25.07.2016
comment
Привет @Jaka Konda - можете ли вы предоставить более подробное решение, которое вы использовали? У меня похожая проблема - мне нужно равномерно расположить круги на выбранном полигоне на карте. - person hbk; 23.06.2021
comment
@hbk, тыкаешь в призраков. Я попробую найти код позже в течение дня, он все равно будет устаревшим. Но, насколько я помню, я просто перебирал все пиксели, если они были белыми, сохранял их в векторе/cv::Array2d, а затем пересылал их k-средним с ожидаемым количеством кластеров, рассчитанным по формуле из моего ответа. Выход - центры. В моем случае круги были фиксированного диаметра, поэтому подходило k-среднее. - person Jaka Konda; 24.06.2021