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):

a shape

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.

boundary of the shape

An expanded version to make each pixel more visible:

enter image description here

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.

enter image description here

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 about this general approach? (Assuming your starting-point is the black outline as shown)

Create a mask by:

  1. Filling the outline with black. (store as 8-bit greyscale)
  2. Putting the filled shape through a low-pass (blur) filter. (convolution)
  3. Creating a bitmap of every pixel lower than a threshold value in the blurred shape.
  4. Possibly contour-growing that bitmap by a margin of a few pixels.
  5. Retaining your original outline only where it falls within the bitmap mask.

The most straightforward algorithm is probably comparing the distances between the points in the figure. Those that are close can be merged, deleting intermediate vectors.

However, you do run the risk of deleting a whole figure, which you might want to keep, as a separate object. In this case, keep the "thin sticks" as a separate figure, and measure the maximum width at each pixel row to determine if you want to keep it. You might say that if either the width or height is below a minimum, discard the figure.

  • Does "comparing the distances" means measuring every pair of points (i.e. every pair of red pixels, not just every pair of green pixels)? If a point is close to several others, do I merge it with its nearest neighbour (only)? Exclude pairs which are already connected by a short line? Will this round-off the corners of the square? Will it result in a long thin line, which (by merging its borders) has been squashed to like zero pixels wide instead of like 5 pixels wide? If I move a point (to merge it), does that create new border pixels (to retain the moved pixel's connection to its neighbours)? – ChrisW Dec 15 '16 at 18:43
  • @ChrisW I assumed you had already converted from pixels to point coordinates or a set of vectors from point to point. Keep in mind that you can also look at what you are cutting off, and determine if it is a "tail" like set of points -- the vector distance is long with a "tail". – Frank Hileman Dec 16 '16 at 19:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.