Алгоритм поиска точки, максимально удалённой от границ фигуры на изображении?

Question

[Plant]

Дано бинарное изображение.
На картинке нарисована произвольная фигура.
Нужно найти точку принадлежащую этой фигуре, максимально удалённую от границ фигуры или границ изображения.

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

Примером фигуры может быть круг на картинке, центр круга и будет нужной мне точкой.

Как лучше решить эту задачу и какой алгоритм применить?

Answer 1

[Alexander Movchan]

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

1. Увеличить радиус на 1 условную единицу (пиксель).
2. Если окружность не пересекает фигуру, перейти к шагу 1.
3. Если возможно сдвинуть центр окружности на 1 условную единицу так, что окружность не будет пересекать фигуру, сдвинуть центр и перейти к шагу 1.

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

Алгоритм будет работать довольно медленно, но других вариантов я не знаю.

P.S. По сути, это всё равно, что надувать воздушный шарик внутри коробки. Сначала мы можем разместить его где угодно, но потом, надуваясь, он сам займёт верное положение.

P.P.S. Как альтернативный вариант, можно создать матрицу, в элемент M[i][j] которой записать расстояние от точки с координатами (i, j) до ближайшей точки фигуры. Потом просто найти максимальное в матрице.

Answer 2

[Кирилл Оленёв]

Я правильно понял, вам нужно:
"Вписать произвольную фигуру в окружность минимального радиуса"
?
Если да, то я бы попробовал бы для начала так:
1) Находим две точки фигуры, максимально удалённые друг от друга
2) Ваша искомая точка - центр этой прямой, соединяющая точки из 1 шага

Comments

[bobrovskyserg]

Враки.
Представьте себе месяц (который на небе, серпом).
Продолжать?

[Plant]

Вписать окружность максимально возможного радиуса в фигуру. Ps. мне нужно найти точку максимально удалённую от границ. А вписывание окружности это возможно один из вариантов решений задачи.

[Кирилл Оленёв]

bobrovskyserg: Согласен, но для выпуклых подойдёт)

[Oxoron]

Как граница фигуры задается?

[bobrovskyserg]

Кирилл Оленёв:
Да что ж вы - полукруг выпуклый!

[Plant]

бинарное изображение n*m
фон - 0, фигура - 1
все пиксели фигуры связные
фон является границей и/или граница изображения

Answer 3

[localghost]

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

Comments

[Plant]

Да, в лоб можно решить данным способом.

[bobrovskyserg]

localghost, Plant:
Сложность от размера - O(n^3) в лучшем случае (если фигура раскатана в линию - O(n^4))
Нафиг-нафиг.
Написано только что

[localghost]

Plant: Ну тогда можно пытаться оптимизировать.
Скажем, если фигура выпуклая, то можно начинать с какой-то разумной догадки и шагать от нее, причем отсекать все дальнейшие шаги в сторону той точки границы, расстояние до которой и так определяло расстояние до границы вообще.

[localghost]

bobrovskyserg: Да, но это уж совсем "в лоб". Если у нас уже есть приличная догадка, то для большинства внутренних точек мы остановим проверку точек границы куда раньше, чем проверим все. Математически ужасно, но в реальности будет быстрее.

[bobrovskyserg]

localghost:
Да, для выпуклой асимптотика O(n^2) и можно доехать наискорейшим спуском.
Правда, решение может не быть таким, как ожидалось: для прямоугольника - не центр, а любая точка на "средней линии".
И не стоит от этого отмахиваться - можно придумать выпуклую фигуру без симметрии с подобной проблемой. Хоть бы трапецию.

[localghost]

Ну, я не знаю, какое решение ожидалось :)
Про спуск уже тоже подумал, и там разве не будет гораздо быстрее? Для выпуклой фигуры множество искомых точек выпуклое и односвязное, так? Тогда мы придем к некоторой искомой точке "лесенкой" от любой точки чуть ли не за O(n^0.5), если n это общее число точек, а фигура не слишком вытянутая. (Мой первый комментарий про оптимизации, таким образом, можно игнорировать.) Если нам нужно хоть какое-то решение, то для выпуклой фигуры все, видимо, просто, если я ничего не упустил.

Answer 4

[Mrrl]

Рассматриваем фигуру как граф: у каждой точки соседями считаются точки из небольшой окрестности (например, 7*7), а длиной ребра - евклидовы расстояния между точками. Тогда расстояние между двумя точками фигуры с хорошей точностью равно кратчайшему пути на этом графе. Осталось найти точку, самую далёкую от границы. Считается за O(S*log(S)), где S - площадь фигуры.

Comments

[Plant]

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

[Mrrl]

Plant: Точкам на границе приписать значение W=0. Потом для каждой точки Q, лежащей в квадрате 7*7 от уже подсчитанной точки P посчитать W(P)+dist(P,Q), и если оно меньше текущего W(Q), то заменить W(Q) на W(P)+dist(P,Q). Лучше всего делать это с помощью приоритетной очереди - перебирать точки P с наименьшим подсчитанным значением - тогда менять значение уже подсчитанной точки не придётся (примерно как алгоритм Дейкстры, но с большим числом стартовых вершин). Тогда значение точки - приближённое расстояние от неё до края, а точка с наибольшим значением - искомая.