Getting Into Shapes


This is, in part, a post for myself. They all are, but this is moreso. My day job includes some Geographic Information Services stuff, which is how we say “maps” when we want to be taken seriously as Information Technology professionals. When we make maps, what we really do is have a computer draw polygons, and then put dots on them. A common need is to put a dot in the middle of a polygon. Yes, this sounds silly, but describe your job this abstractly and see how it comes out.

The trouble is polygons can be complicated stuff. Can be, not are. If the polygon is, like, the border of your building’s property it’s probably not too crazy. It’s probably a rectangle, or at least a trapezoid. Maybe there’s a curved boundary. If you need a dot, such as to place the street address or a description of the property, you can make a good guess about where to put it so it’s inside the property and not too close to an edge.

But you can’t always. The polygons can be complicated. Especially if you’re representing stuff that reflects government or scientific or commercial interest. There’s good reasons to be interested in the boundaries between the low-low tide and the high-high tide lines of a beach, but that’s not going to look like anything simple for any realistic property. Finding a representative spot to fix labels or other business gets tricky.

So this crossed my Twitter feed and I’ll probably want to refer back to it at some point. It’s an algorithm, published last August by Vladimir Agafonkin at Mapbox, which uses some computation tricks to find a reasonable center.

The approach is, broadly, of a kind with many numerical methods. It tries to find an answer by taking a guess and then seeing if any obvious variations will make it a little better. If you can, then, repeat these variations. Eventually, usually, you’ll get to a pretty good answer. It may not be the exact best possible answer, but that’s all right. We accept that we’ll have a merely approximate answer, but we’ll get it more quickly than we otherwise would have. Often this is fine. Nobody will be upset that the label on a map would be “better” moved one pixel to the right if they get the map ten seconds faster. Optimization is often like that.

I have not tried putting this code into mine yet; I’ve just now read it and I have some higher-priority tasks at work. But I’m hoping to remember that this exists and to see whether I can use it.

Advertisements