0 0 0 1 0 0 0
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
[C++] Покрыть произвольные области окружностями с наименьшей суммарной площадью
Здравствуйте.
Дан черно-белый рисунок (матрица) с произвольно выбранными черными областями на белом фоне.
Необходимо покрыть все черные области окружностями так, чтобы суммарная площадь всех окружностей была наименьшей из всех возможных.
На входе - матрица с нулями(белый)\единицами(черный) произвольного размера.
На выходе - координаты центров и радиусы окружностей.
Язык - скорее всего C++, но не суть - главное алгоритм.
Есть алгоритм, работающий "в лоб" - перебираем все точки матрицы, в каждой
точке строим множество окружностей радиусом от 0 до N, если покрыли область -
добавляем к списку окр-тей, затем долгая сотрировка всех найденных окружностей
(отбрасываем вложенные, выделяем с наибольшей средней яркостью - число черных
точек деленное на число всех точек круга).
Необходимо оптимизировать алгоритм.
Есть идеи выделять все отдельные замкнутые черные области, разбивать их на
выпуклые фигуры - и пытаться покрыть уже эти выпуклые области.
Но дальше идей пока не дошло - как это реализовать пока представляю туманно...
Буду благодарен за любые мнения или ссылки по теме.
Дан черно-белый рисунок (матрица) с произвольно выбранными черными областями на белом фоне.
Необходимо покрыть все черные области окружностями так, чтобы суммарная площадь всех окружностей была наименьшей из всех возможных.
На входе - матрица с нулями(белый)\единицами(черный) произвольного размера.
На выходе - координаты центров и радиусы окружностей.
Язык - скорее всего C++, но не суть - главное алгоритм.
Есть алгоритм, работающий "в лоб" - перебираем все точки матрицы, в каждой
точке строим множество окружностей радиусом от 0 до N, если покрыли область -
добавляем к списку окр-тей, затем долгая сотрировка всех найденных окружностей
(отбрасываем вложенные, выделяем с наибольшей средней яркостью - число черных
точек деленное на число всех точек круга).
Необходимо оптимизировать алгоритм.
Есть идеи выделять все отдельные замкнутые черные области, разбивать их на
выпуклые фигуры - и пытаться покрыть уже эти выпуклые области.
Но дальше идей пока не дошло - как это реализовать пока представляю туманно...
Буду благодарен за любые мнения или ссылки по теме.
Разбиваешь черные области на квадраты, диагонали квадратов будут диаметрами окружностей, пересечение диагоналей будут центрами окружностей, вопрос в данном случае будет сводится к оптимизированию квадратов в черных областях, идеально если квадрат будет один, то есть чем больше квадраты тем меньше суммарная площадь окружностей
Цитата: unplugged
Здравствуйте.
Дан черно-белый рисунок (матрица) с произвольно выбранными черными областями на белом фоне.
Необходимо покрыть все черные области окружностями так, чтобы суммарная площадь всех окружностей была наименьшей из всех возможных.
На входе - матрица с нулями(белый)\единицами(черный) произвольного размера.
На выходе - координаты центров и радиусы окружностей.
Язык - скорее всего C++, но не суть - главное алгоритм.
Есть алгоритм, работающий "в лоб" - перебираем все точки матрицы, в каждой
точке строим множество окружностей радиусом от 0 до N, если покрыли область -
добавляем к списку окр-тей, затем долгая сотрировка всех найденных окружностей
(отбрасываем вложенные, выделяем с наибольшей средней яркостью - число черных
точек деленное на число всех точек круга).
Необходимо оптимизировать алгоритм.
Есть идеи выделять все отдельные замкнутые черные области, разбивать их на
выпуклые фигуры - и пытаться покрыть уже эти выпуклые области.
Но дальше идей пока не дошло - как это реализовать пока представляю туманно...
Буду благодарен за любые мнения или ссылки по теме.
Дан черно-белый рисунок (матрица) с произвольно выбранными черными областями на белом фоне.
Необходимо покрыть все черные области окружностями так, чтобы суммарная площадь всех окружностей была наименьшей из всех возможных.
На входе - матрица с нулями(белый)\единицами(черный) произвольного размера.
На выходе - координаты центров и радиусы окружностей.
Язык - скорее всего C++, но не суть - главное алгоритм.
Есть алгоритм, работающий "в лоб" - перебираем все точки матрицы, в каждой
точке строим множество окружностей радиусом от 0 до N, если покрыли область -
добавляем к списку окр-тей, затем долгая сотрировка всех найденных окружностей
(отбрасываем вложенные, выделяем с наибольшей средней яркостью - число черных
точек деленное на число всех точек круга).
Необходимо оптимизировать алгоритм.
Есть идеи выделять все отдельные замкнутые черные области, разбивать их на
выпуклые фигуры - и пытаться покрыть уже эти выпуклые области.
Но дальше идей пока не дошло - как это реализовать пока представляю туманно...
Буду благодарен за любые мнения или ссылки по теме.
а как насчет варианта когда число окружностей бесконечно ?
Цитата: LM(AL/M)
а как насчет варианта когда число окружностей бесконечно ?
Хитрый какой. Решил бесконечно маленькие окружности использовать ???
А если область - большой круг - что тогда ? Один большой - правильный ответ, а маленькие перекрыватся должны.
2 unplugged
Первым что пришло в голову - пробовать размещать сначала больщые круги и постепенно уменьшать радиус если большой ставить уже некуда. Критерием для розмещения можно принять процентное соотношение накритой черной площади к накритой белой + накрытой на предыдущих шагах.
На счет розбиения на опуклие области - Разбить многоугольник на опуклые части можно несколькими вариантами. Если будеш так делать то надо учитывать форму полученых опуклостей. А то прямоулольник ведь тоже опуклый, а если ево длинна намного больше шырини то одним кругом такое накрывать безсмысленно.
А вообще кажется мне что здесь точного решения нет и надо евристику. Но ето только мое некомпетентное мнение.
Цитата: barracuda
Разбиваешь черные области на квадраты, диагонали квадратов будут диаметрами окружностей, пересечение диагоналей будут центрами окружностей, вопрос в данном случае будет сводится к оптимизированию квадратов в черных областях, идеально если квадрат будет один, то есть чем больше квадраты тем меньше суммарная площадь окружностей
Вот тебе условный рисунок
Код:
Если на большом нарисовать круг, то етот ркуг накроет и маленький квадрат. Ето надо учитывать.
ЗЫ. Модератору. Сори что так неправильно использую тег code. Рисовать лень.
Цитата: Rebbit
Хитрый какой. Решил бесконечно маленькие окружности использовать ???
А если область - большой круг - что тогда ? Один большой - правильный ответ, а маленькие перекрыватся должны.
А если область - большой круг - что тогда ? Один большой - правильный ответ, а маленькие перекрыватся должны.
если область -- круг то в ответе и будет круг но по моему в задаче о прямоугольниках говорится
а насчет бесконечно маленьких окружностей... какое бы покрытие вы тут ни придумали всегда можно будет найти покрытие с меньшей площадью и т. обр. количество окружностей будет стремиться к бесконечности а минимальный радиус окружности -- к нулю
Цитата: LM(AL/M)
какое бы покрытие вы тут ни придумали всегда можно будет найти покрытие с меньшей площадью и т. обр. количество окружностей будет стремиться к бесконечности а минимальный радиус окружности -- к нулю
Спорить не стану, потому что не знаю.
Цитата: LM(AL/M)
по моему в задаче о прямоугольниках говорится
Если считать елемент матрицы маленьким прямоугольником - то да, но об етом в условии ничего не сказано.
А уменьшать радиусы целесообразно только на границах области.
unplugged Есть всетаки ограничения или на наименьшый радиус или на количество окружностей ???
Спасибо всем за ответы. В принципе, на уровне "для галочки" - задача уже мной решена и сдана :)
Что касается ограничений - естественно, радиус\координаты центра окружностей задаются в дискретах матрицы, минимальный радиус задан вначале и он > 1, иначе задача теряет смысл. ;)
Количество окружностей - в идеале - должно быть минимальным, а их радиусы - максимальными.
В итоге отказался от разнообразных "извращений" и сделал просто:
1. Проходим по всей матрице, выделяем все черные области - обходя их границы до возвращения в первую обнаруженную новую граничную точку. Путем фильтрации начального изображения избавляемся от возможного зацикливания алгоритма выделения замкнутых областей.
2. Далее, вкратце - каждую отдельную фигуру покрываем прямоугольниками\квадратами, а их - соотв. окружностями. Делая несколько таких покрытий с различно заданной высотой прямогольника, из них выбираем оптимальное - с минимальным покрытием не принадлежащих фигуре областей.
3. Для фигур, размеры которых меньше заданного минимального радиуса - просто берем описанный прямоугольник - и покрываем его.
От разбиения на выпуклые фигуры отказался, т.к. далеко не всегда это дает результаты лучше, чем такой метод - а нужен естественно универсальный способ, работающий с любыми областями.
В итоге, реализованный алгоритм работает быстрее и дает лучшее покрытие, чем исходный - что и требовалось получить. :)
Что касается ограничений - естественно, радиус\координаты центра окружностей задаются в дискретах матрицы, минимальный радиус задан вначале и он > 1, иначе задача теряет смысл. ;)
Количество окружностей - в идеале - должно быть минимальным, а их радиусы - максимальными.
В итоге отказался от разнообразных "извращений" и сделал просто:
1. Проходим по всей матрице, выделяем все черные области - обходя их границы до возвращения в первую обнаруженную новую граничную точку. Путем фильтрации начального изображения избавляемся от возможного зацикливания алгоритма выделения замкнутых областей.
2. Далее, вкратце - каждую отдельную фигуру покрываем прямоугольниками\квадратами, а их - соотв. окружностями. Делая несколько таких покрытий с различно заданной высотой прямогольника, из них выбираем оптимальное - с минимальным покрытием не принадлежащих фигуре областей.
3. Для фигур, размеры которых меньше заданного минимального радиуса - просто берем описанный прямоугольник - и покрываем его.
От разбиения на выпуклые фигуры отказался, т.к. далеко не всегда это дает результаты лучше, чем такой метод - а нужен естественно универсальный способ, работающий с любыми областями.
В итоге, реализованный алгоритм работает быстрее и дает лучшее покрытие, чем исходный - что и требовалось получить. :)