Algorithm for finding the point that is the most distant from the borders of the figure in the image?

Question

Algorithms

Given a binary image.
The picture is a random figure.
It is necessary to find a point belonging to this figure, as far as possible from the borders of the figure or the borders of the image.
Those. the task is to find such a point belonging to the figure, from which it is possible to build a circle with a maximum radius, all points of which will not go beyond the boundaries of the figure or image.
An example of a figure could be a circle in the picture, the center of the circle will be the point I need.
What is the best way to solve this problem and what algorithm should be applied?

Answer 1

If the figure is convex, we can take an arbitrary point inside, which we will consider the center of the inscribed circle, take the radius equal to zero and apply the following algorithm:
1. Increase the radius by 1 conventional unit (pixel).
2. If the circle does not intersect the figure, go to step 1.
3. If it is possible to shift the center of the circle by 1 conventional unit so that the circle does not intersect the figure, shift the center and go to step 1.
If the figure is not convex, split it into convex sub-shapes and choose an arbitrary point in each of them. Then repeat the above algorithm for each selected point and choose the maximum result.
The algorithm will work rather slowly, but I don't know any other options.
PS In fact, it's like inflating a balloon inside a box. At first, we can place it anywhere, but then, inflating, it will take the right position on its own.
PPS As an alternative, you can create a matrix, in the M[i][j] element of which you can write the distance from the point with coordinates (i, j) to the nearest point of the figure. Then just find the maximum in the matrix.

Answer 2

I correctly understood, you need:
"Inscribe an arbitrary figure in a circle of minimum radius"
?
If yes, then I would try to start like this:
1) Find two points of the figure, as far as possible from each other
2) Your desired point is the center of this line connecting the points from 1 step

Answer 3

Well, wait, but you can’t do it on the forehead?
For simplicity, we assume that the figure is simply connected.
For each internal point, we look for the distance to the border (that is, we find the nearest point of the border). That internal point for which this distance is maximum is the required one.
What's bad, besides what's long?

Answer 4

We consider the figure as a graph: for each point, the neighbors are points from a small neighborhood (for example, 7 * 7), and the length of the edge is the Euclidean distance between the points. Then the distance between two points of the figure with good accuracy is equal to the shortest path on this graph. It remains to find the point furthest from the border. Takes O(S*log(S)), where S is the area of ​​the figure.