How to split an arbitrary shape into convex polygons?

Question

Java

Hello everybody!
The input is a set of coordinates (x, y), each of which denotes a point on the plane. At the output, you need to get an array of splitting this form into primitives.
In general, maybe there is a simpler algorithm for my task. My task is as follows:
there is a picture with a contour, for example:

There are holes in the contour.
Purpose: to get at the output the arrangement of numbers in the circuit in such a way that there are 2-3 digits in a sufficiently large circuit, and only one in a small one (if it fits). That is:

"Sufficiently large" and "small" are relative concepts, therefore, sufficiently large is the number of pixels in the contour> N, and small is < M.
I must say that I find the coordinates of the contour with a breadth-first search algorithm and write them to an array, so that you can access all the coordinates of the contour.
There were several ideas, including inscribing a contour into a rectangle and placing a number in the center, but:
1) The number can be in a hole
2) The number can be outside the contour altogether
Next, you can triangulate and put a number in the center of each triangle, but the problem is that, judging by the algorithms that I googled, triangulation works mainly for convex polygons, and there can be a lot of triangles, and, accordingly, numbers.
So, the last idea I settled on is splitting this shape into convex polygons and putting a number in their centers.
Actually, the question is: I need either an idea how this can be done more simply, or a Java code that makes this partition, or the most complete description of the partition algorithm.
Many thanks in advance for your reply!

Answer 1

1. Write a function that would determine whether an arbitrary point is in the contour. You can stand in the upper left corner, go pixel by pixel and write true/false values ​​to the "occurrence" map using the boundaries of the contour - as soon as you have passed through the contour, change the value being written to the opposite (false -> true). Floodfil can also come in handy.
2. Build a distance map to the borders. For each pixel, print the value of the minimum distance to some border if the point is inside the outline.
3. Find local maxima.
4. Arrange the numbers in local maxima, you can automatically adjust the font size, operating on the resulting distance to the border.
The distance map will resemble the following picture (approximately,
Sounds complicated, but it should work.