As a quick recap, here is my planet with the country boundaries highlighted:
So the challenge here is to pick an essentially random location within the country boundaries that is suitable for it's capital city. As I already have a triangulation of the country to be used when deciding within which country a point on the planet's surface lies, I can use this to place the city. Rather than picking random points on the planet in the hope of eventually finding one that lies within the country of interest however it makes more sense to pick points within the triangulation to start with.
The simplest way therefore would be to just pick a random triangle from the country's triangulation then pick a random point within it. The first is trivial while the second can also be easily accomplished using barycentric co-ordinates to convert three random numbers in the range [0, 1] into a point within the triangle.
While this works, I didn't want capital city placement to be completely random, for my purposes I didn't want a capital city that was too close to the country boundaries but with the naive approach described above there is nothing to stop a capital being right on the border. This is purely a subjective restriction and I'm sure somewhere in the world there is a capital very close to a border but it just didn't feel right to me.
Unfortunately determining the distance between a point within a country and it's border isn't a trivial task, requiring the distance to each line segment making up the border to be calculated and the minimum taken. Determining what is an acceptable distance is also not as easy as it might be due to the wildly varying shapes of the countries. An acceptable distance for a generally circular country might be impossible to satisfy for a different country that was long and thin.
There isn't much that can be done to alleviate the first issue other than test as few candidate points as possible and possibly use some sort of spacial index to reduce the number of border segments being processed - while it's a bit brute force however it's not prohibitively expensive so improving it isn't top priority.
Without any particular knowledge of a country's shape however determining an acceptable distance from the border to place the capital city is a bit more of a challenge. Rather than try to work out some sort of heuristic from the border vertices I chose instead to use a sampling approach. For each country a number of random points are generated using the simple algorithm above and the distance from each to the country's border calculated. The point that is furthest from the border is chosen as the position of the capital city.
The number of points to test is a little trial and error - sample too few and you might not pick a point that's far enough away from the border to be acceptable while sample too many and you will inevitably end up with a point pretty much in the middle of every country which is too uniform and also unacceptable.
I ended up taking 25 sample points for each country which I think gives a decent spread of capital positions while still not generating any too close to the borders.
I am hoping the system can be extended to start placing secondary and tertiary settlements by adding other factors to the heuristic such as distance from already placed settlements (scaled by the relative sizes of each settlement) along with some physical factors such as the candidate site's proximity to rivers or bodies of water to encourage settlements in coastal areas and the general flatness of the terrain to make lowlands and valley floors more appealing than steep mountain sides.
For reference I thought it would be worth including an illustration of the triangulation generated from the country boundaries, as you can see the simple ear-clipping algorithm used tends to produce long thin triangles. These don't affect the functionality of the system but at some point in the future I might be adding these triangles to some sort of spacial organiser to improve query performance in which case a triangulation that was a bit more evenly distributed across the surface might be better, but it will do for now.
Then of course there is generation of the actual cities themselves complete with road network and buildings, so there is as ever plenty to do!