On placing a tag on an area

The common approach I have used in the past for locating a tag on a given 2D shape has been to use the centroid location. For convex parts there is a very good solution. However, when the shape is not convex the centroid location may be outside of the shape surface.

Whenever the tags are intended to identify a shape it might be a problem is the label falls outside of the shape, even more so when multiple shapes are packed together, as user may not be able to be sure which label belongs to which part.

One idea of fixing that is to make sure the tag location is always inside the part, and for that purpose I have evolved through for different algorithms, trying to find the best result.

Algorithm 1

If centroid is within the shape area, then just use that. When it is outside (concave shape) then an horizontal sweep is done in 10% increments, at the centroid height, looking for a spot within the shape area. If that is not found, then same approach is repeated with a vertical sweep at the centroid width too.  It appears as a black box in the video.

Algorithm 2

At the centroid, one horizontal line is traced and shape is explored for the longest area intersection with this line. The middle point of this line is now used for performing a similar sweep but this time done vertically. The tag location will be at the middle point of the longest vertical intersection. It appears a in blue color in the video.

Algorithm 3

Similar to algorithm 2, but adding a second horizontal sweep trying to get a better centered result. It appears as a pink box in the video.

Algorithm 4

It follows a topological approach, looking for the point that it is furthest from the shape perimeters. To do so the shape is painted as a bitmap and a dilate operation is done repeatedly till the last pixels are removed from the image. It is the location of that last pixel the desired tag location. It appears in red color in the video.

Usually, the black box is hiding the centroid that appears as a small circle, but on a few cases that can be seen as the black box is moved away from the centroid.

If you have another way of solving the problem, please let me know in the comments below.

Algorithm 5

Actually, similar to number 4: Instead of using a bitmap, I use the vector representation of the perimeter as a polygon. Then I perform, repeatedly, negative polygon buffer operations [on the larger block] until polygon area reaches a certain threshold. Then I use the centroid of that remaining polygon as the location for the label. It turns out much more efficient than its cousin Algorithm 4 (provided you have a decent polygon offset implementation).