First - consider that rectangles are chosen deliberately because the involved pixels can be "analyzed" quickly. Consider that circle-drawing routines define their content by the enclosing rectangle. The general case would be one you've already explored, pixel-by-pixel, and would cause a lot of pain solving each problem specifically.
BUT, there is a place for you to look for help:
Gimp 2 - an open source photo manipulation application - has two features (at least) you may find useful to consider:
Free Select Tool : selects a region defined by an arbitrary number of points defining a closed boundary
Scissor Select Tool: Used like Free Select Tool but it locates edges when connection adjacent points.
Since this is "Open Source", you can check out the source code used for both of these and see if it helps.
Gimp 2 Home Page^