Ask HN: Algorithm for Calculating Contour of Polygons

This is something that's central to PCB manufacture and surface mount soldering.

Given:

  +------+
  |      |
  |     /|--------+
  |    / |        |
  |    | |        |
  |    \ |        |
  |     \|--------+
  |      |
  +------+

The output would be:

  +------+
  |      |
  |      +--------+
  |               |
  |               |
  |               |
  |      +--------+
  |      |
  +------+

Where in general we can have lines, circles, ovals, and so on.

Now there are algorithms for extracting the contour if the input shapes are limited to rectangles. The goal is to generalize to arbitrary shapes.

Quadtrees + intersection + inside/outside polygon computation could help. I've also read about the marching squares algo but that looks like it works on bit maps.