I want to create a minimal polygon which approximates the boundary of an arbitrary (semi-random) shape.
By "minimal" I mean, "as few points as possible".
The original shape (to be bounded) is in bitmap format, with simple coloring.
The complication is that the shape may have lines (i.e. long thin areas/shapes) coming out of it. What algorithm can you suggest I use for detecting these lines?
For example, I want to detect lines which are no more than five pixels wide; the lines might be on a diagonal, or curved.
I'd prefer an algorithm, which I can implement, rather than a pre-implemented third-party tool or library.
For example, here is a sample simple shape (hand-drawn using Paint):
Note that it has a semi-random line coming out of it.
Here's the result of the shape-processing that I've implemented so far:
- The red pixels show a boundary traced around the shape
- The green pixels on the red boundary show a fairly minimal polygon, where the boundary changes shape.
An expanded version to make each pixel more visible:
The green pixels represent the polygon that I want, except that I'd like to cut off the tail shape at the bottom (so that basically just a square remains), because its maximum width makes it too thin to be interesting.
Given this data, what algorithm would detect that there's a thin shape coming out of the bottom?
Re. the performance requirements, the bitmap is likely to be say 1000 pixels square; the bounding polygon might have a couple of hundred points in total; and the algorithm is being run on a PC.