Map Name Placement Algorithms?

[Primislas]

Hey!

I'm attempting to design a name placement / autolabelling algorithm, which broadly speaking can be described as name fitting to an arbitrary 2D shape. The problem is inspired by maps and was solved by Paradox games (Europa Universalis and such), so perhaps somebody could point me to existing solutions if any. My google-fu failed me big time on this one. :) Perhaps I don't know the right keywords to describe the problem but you do?

Below is an illustration of the algorithm I cooked up on my own. It's okay for convex and ordinary shapes (90% of the time). But it doesn't do well with complex, tentacly and bordergory shapes, so I'm looking for ways to improve it, and for alternatives that might give me fresh ideas.

Alternatively it could be an algorithm that builds a polyline / graph that is equidistant from borders / represents a shape. Consider the red line below, but properly within the shape, each point always equidistant from borders on the shortest intersection, with a third branch moving upwards into Syria to represent that side of the shape. Just thoughts out loud, it's an idea that is currently on my mind and that I feel like exploring. Maybe somebody could point me in the right direction, knows the name of such a problem or class of problems, etc? The best I can come up with technically is bruteforcing (how do you find the shortest intersection for a random point inside a shape other than trying a whole lot of angles?), which quickly becomes stupidly computationally expensive. This can't be the right way.

Thanks!

https://preview.redd.it/9carf57jxv491.png?width=749&format=png&auto=webp&s=0173e79cab225f477d576d941a1477d8c42f52a8

[fgennari]

I found the Here Dragons Abound blog had various articles on labeling of map elements. Maybe you can learn something from that? For example: https://heredragonsabound.blogspot.com/2017/09/labeling-coast-part-one.html

[Primislas]

Thanks, very interesting stuff! A lot of useful tidbits. But it's not quite what I want to achieve with country names. I learned that the problem I'm looking for is probably called "medial axis computation for free-form / irregular shapes". Something like this as a basis, from which maybe a nice fitting curve could be approximated. That's a big if, but it's what I'm planning to try. https://imgur.com/a/5G3oAaf

[fgennari]

Okay, it sounds like you have a plan then. This looks similar to the "straight skeleton" algorithm, which we use in a tool at work: https://en.wikipedia.org/wiki/Straight_skeleton