I want to turn digitized polygons into simpler shapes.

More precisely, given a noisy closed polyline, I want to fit a polygon to it with an imposed number of sides, such as a triangle or quadrilateral, assuming that the data can roughly match. The fitted polygons need not be inscribed and/or circumscribed, an average fit is preferred. The number of polyline vertices will range between a few tenths and a few hundredths, and the polygons can be up to octagons. Robustness if preferred over accuracy. If that helps, the polygons can be assumed convex.

enter image description here

There are a few variants of the problem:

  • the number of sides is given, and there are no other constraints;
  • the number of sides is given and there are constraints such as right angles or parallel sides;
  • the number of sides isn't specified and some optimum should be found.

I am looking for resources on how to address these questions. I know the Douglas-Peucker line simplification process pretty well but I don't think it suffices here (because of the constraints).

  • 1
    $\begingroup$ If the only constraint is the number of sides, you could try generating the convex hull and then removing the points at which the angle is closest to $180^{\circ}$ until you have the desired number of sides. $\endgroup$ – Wouter Mar 9 '16 at 13:56
  • $\begingroup$ @Wouter: quite interesting. Do we even need to consider the convex hull ? $\endgroup$ – Yves Daoust Mar 9 '16 at 13:58
  • $\begingroup$ @TakahiroWaki: in the examples shown, I don't see any ambiguity of this kind. And in the first variants, n is given. $\endgroup$ – Yves Daoust Mar 9 '16 at 16:03
  • $\begingroup$ Sorry,I mistaked posting. $\endgroup$ – Takahiro Waki Mar 9 '16 at 16:12
  • 2
    $\begingroup$ Have you considered looking at the polyline point distances (squared) to the centroid, to determine the likely intended vertices? Followed by an iterative approach (using harmonic, string-like "forces" acting on the vertices) to find the shape fulfilling the rules best matching the original? $\endgroup$ – Nominal Animal Apr 21 '16 at 12:36

It is possible that noisy lines change n-polygon.It is necessarily that given a value k, my solution is $$ax+b≦f(x) ≦ax+d$$and$$d-b≦k. $$

then choose $f(x)=ax+(b+d)/2$.


Surround shape with$ f(x),g(x),・・・$are simplified shape. 

expression of edge detection is



Is vector graphics what you find? https://en.wikipedia.org/wiki/Vector_graphics or http://www.graphicmania.net/how-to-simplify-complex-paths-in-illustrator-cs5/

  • $\begingroup$ This is valid for a single line. I need to segment the shape in several lines. $\endgroup$ – Yves Daoust Mar 9 '16 at 16:18
  • $\begingroup$ g(x),h(x)・・・ finally can make closed polygon. $\endgroup$ – Takahiro Waki Mar 9 '16 at 18:34
  • $\begingroup$ Can you describe a complete procedure ? There's nothing I can do with these fragments of information. $\endgroup$ – Yves Daoust Mar 10 '16 at 7:45
  • $\begingroup$ I am afraid you don't get my question. I have polygons and I need to approximate them with polygons of fewer sides. $\endgroup$ – Yves Daoust Mar 11 '16 at 7:44

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.