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 shapeThe 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.
How to detect thin extrusions from a polygon?
algorithms;geometry