# Simplifying polygons

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.

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

• 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. – Wouter Mar 9 '16 at 13:56
• @Wouter: quite interesting. Do we even need to consider the convex hull ? – Yves Daoust Mar 9 '16 at 13:58
• @TakahiroWaki: in the examples shown, I don't see any ambiguity of this kind. And in the first variants, n is given. – Yves Daoust Mar 9 '16 at 16:03
• Sorry,I mistaked posting. – Takahiro Waki Mar 9 '16 at 16:12
• 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? – 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$.

$g(x),h(x),・・・$

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

expression of edge detection is

$f(x)=(I_r-I_l)/2(erf(x/√2σ)+1))+I_l$

https://en.wikipedia.org/wiki/Edge_detection

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/

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