I want to:

  • Simplify a set of points that outlines a closed opaque image on a transparent background.

  • The simplified set of points should not intrude into the closed opaque image.

I use a Marching Squares Algorithm to fetch a set of points (x,y) that outlines the opaque pixels of an image. This gives a valid set of points outlining the opaque image.

Original image (an opaque sun image on a transparent background):

enter image description here

Result of Marching Squares Algorithm (a set of points--red, around the opaque sun):

enter image description here

This set of points is fine--entirely outside the sun (no intrusion). But the current set of points contains many points that can be eliminated because they are redundant. The redundant points are on the line segment connecting the previous and next point in the set.

For example in the illustration below, the middle red point is redundant and can be eliminated because connecting the first and last points results in the same line segment:

enter image description here

I've tried several path-point simplification algorithms like the Douglas-Peucker Algorithm. This algorithm does reduce points, but it also lets the simplified path intrude into the original image.

For example in the illustration below, the middle point has been eliminated but the result causes the path to intrude into the image:

enter image description here

I have an array containing all pixel colors on the image, so this array can be used to determine if any pixel is transparent (outside the image) or opaque (inside the image).

I'm looking for an algorithm to simplify the path-points which does not let the resulting path intrude into the original image.

  • 1
    $\begingroup$ What have you tried and where did you get stuck? Can you remove any other points but those directly on a straight line between two other points? $\endgroup$ – Raphael Sep 23 '14 at 17:00
  • $\begingroup$ @Raphael, thanks for your interest! Since posting I've had this theory: The points are on the image border (sorry I missed mentioning this in my Q) so if I travel from "pointA to pointB to pointC" in a clockwise direction, I know I must keep any pointB if angleAC is greater than angleAB because eliminating pointB would cause incursion. So I know which points can't be eliminated. Is this theory true? If yes, I can eliminate all points except those that can't be eliminated under this theory. $\endgroup$ – markE Sep 23 '14 at 17:33
  • $\begingroup$ @Raphael - continued: The above process might cause the resulting connection lineAC to gap off the border. A small gap is acceptable. A larger gap is unacceptable and I must put the point back that caused the gap. I haven't come up with how to calculate a tolerable gap--I'm stuck here. $\endgroup$ – markE Sep 24 '14 at 3:44

Your Answer

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

Browse other questions tagged or ask your own question.