Identify the correct spot to place a label
What about putting the label at the innermost point of the segment? Let's define innermost by the maximum of the distance transform of the segment's mask.

With software systems like Mathematica and the sort, it is straightforward to achieve.

The mask for one segment, and its distance transform:


After repeating for each segment and positioning labels where the individual distance transforms are maximum: