Algorithm for finding irrregular polygon centroid (label point)

Quick and dirty: If the "false" centroid is not in the polygon use the nearest vertex to that point.

You might want to look at this: http://github.com/tparkin/Google-Maps-Point-in-Polygon

It appears to use a Ray Casting algorithm that should match the case that you presented.

There is a blog post about it here. http://appdelegateinc.com/blog/2010/05/16/point-in-polygon-checking/

An (older) ESRI algorithm computes the center of mass and, after testing it for inclusion in the polygon, moves it horizontally if necessary until it lies within the polygon. (This could be done in many ways depending on what fundamental operations are available within your programming environment.) This tends to produce label points fairly close to the visual center of the polygon: try it out on the illustration.