Fitting place names into map shapes

Question

I'm drawing shapes using GDI+ using a list of lat/lon floats, and I need to place the name of the place within the borders of the polygon. Simply centering the text in the bounding rectangle doesn't work for irregular shapes. I have the text and the font so I can get the size of the rectangle that the text will need to fit in, but at that point I'm stuck.

This seems like a common problem that all mapping software solves, as well as the kind of thing you would find in an algorithm or computer graphics textbook.

So, given a list of floats for a polygon and a rectangle, is there a way to get the best possible point to place the text, using: 1) GDI+; 2) SQL Server Geospatial; or 3) c# code (or c, pseudocode, etc)

Answer 1

I think you're basically looking for the centroid of your polygon, around which you could center your text. The Wikipedia article contains good descriptions of the various methods.

A simple approach would be to just take the average of all the points that make up your polygon, and use this averaged point as the center for your text.

See also this question:

http://stackoverflow.com/questions/128348/how-do-i-find-the-center-of-a-number-of-geographic-points

It's a little more complicated than simple averaging, since you need to account for the curvature of the Earth in your calculations (maybe, if the scale is large enough).

Update: I just thought of a simple way you could do this. Write a function something like this:

public Point Centrality(Point somePoint, Point[] otherPoints)
{
    float sumOfSquares = 0;
    foreach (Point point in otherPoints)
    {
        float dist = DistanceBetween(somePoint, point);
        sumOfSquares += dist * dist;
    }
    return 1 / sumOfSquares;
} 

Then (this may be computationally expensive) iterate at whatever resolution you wish through the rectangle that bounds the region, and evaluate the Centrality of each point. The point with the highest Centrality score will almost certainly be within the boundaries of complex regions, since points outside the region will be distant from all points that make up the region (this is why you use squared distance instead of just distance).

This may just be a starting point. This measure would be highly affected by the granularity of the points/lines making up the region - for example, if the Florida panhandle was defined using twice as many points as the other half of Florida, the point with the highest Centrality measure would be well into the panhandle and not in the center as it should be.

Answer 2

The simplest thing to do would be to just draw them all beneath your shape with a rectangle around them.

-Get the maximum Y from your coordinates
-Get the minimum & maximum X from your coordinates
-Draw the box at position [maxX-minX / 2 - (sizemessage/2)),y]