Closest distance to border of shape

Question

I have a shape (in black below) and a point inside the shape (red below). What's the algorithm to find the closest distance between my red point and the border of the shape (which is the green point on the graph) ?
The shape border is not a series of lines but a randomly drawn shape.

Thanks.

Answer 1

As always, it depends on the data, in this case, what your shapes are like and any useful information about your starting point (will it often be close to a border, will it often be near the center of mass, etc).

If they are similar to what you show, I'd probably test the border points individually against the start. Now the problem is how you find the border without having to edge detect the entire shape.

The problem is it appears you can have sharply concave borders (think of a circle with a tiny spike-like sliver jutting into it). In this case you just need to edge detect the shape and test every point.

I think these will work, but don't hold me to it. Computational geometry seems to be very well understood, so you can probably find a pro at this somewhere:

Method One If the shape is well behaved or you don't mind being wrong try this:

1- Draw 4 lines (diving the shape into four quandrants). And check the distance to each border. What i mean by draw is keep going north until you hit a white pixel, then go south, west, and east.

2- Take the two lines you have drawn so far that have the closest intersection points, bisect the angle they create and add the new line to your set.

3- keep repeating step two until are you to a tolerance you can be happy with.

Actually you can stop before this and on a small enough interval just trace the border between two close points checking each point between them to refine the final answer.

Method Two (this wil work with the poorly behaved shapes and plays well with anti-aliasing):

1- draw a line in any direction until he hit the border (black to white). This will be your starting distance.

2- draw a circle at this distance noting everytime you go from black to white or white to black. These are your intersection points.

As long as you have more than two points, divide the radius in half and try again.

If you have no points increase your radius by 50% and try again (basically binary search until you get to two points - if you get one, you got lucky and found your answer).

3- your closet point lies in the region between your two points. Run along the border checking each one.

If you want to, to reduce the cost of step 3 you can keep doing step 2 until you get a small enough range to brute force in step 3.

Also to prevent a very unlucky start, draw four initial lines (also east, south, and west) and start with the smallest distance. Those are easy to draw and greatly reduce your chance of picking the exact longest distance and accidentally thinking that single pixel is the answer.

Edit: one last optimization: because of the symmetry, you only need to calculate the circle points (those points that make up the border of the circle) for the first quadrant, then mirror them. Should greatly cut down on computation time.

Answer 2

So your shape is defined as bitmap and you can access the pixels.

You could scan ever growing squares around your point for border pixels. First, check the pixel itself. Then check a square of width 2 that covers the point's eight adjacent pixels. Next, width 4 for the next 16 pixels and so on. When you find a border pixel, record its distance and check against the minimum distance found. You can stop searching when half the width of the square is greater than the current minimum distance.

An alternative is to draw Bresenham circles of growing radius around the point. The method is similar to the square method, but you can stop immediately when you have a hit, because all points are supposed to have the same distance to your point. The drawback is that this method is somewhat inaccurate, because the circle is only an approximation. You will also miss some pixels along the disgonals, because Bresenham circles have artefacts.

(Both methods are still quite brute-force and in the worst case of a fully black bitmap will visit every node.)

You need a criterion for a pixel on the border. Your shape is antialiassed, so that pixels on the border are smoothed by making them a shade of grey. If your criterion is a pixel that isn't black, you will chose a point a bit inside the shape. If you cose pure white, you'll land a bit outside. Perhaps it's best to chose a pixel with a grey value greater than 0.5 as border.

If you have to find the closest border point to many points for the same shape, you can preprocess the data and use other methods of [nearest-neighbour serach].

Answer 3

If you define the distance in terms of 'the minimum number of steps that need to be taken to reach from the start pixel to any pixel on the margin', then this problem can be solved using any shortest path search algorithm like bread first search or even better if you use A* search algorithm.