Converting a polyline to a polygonal shape with width

Question

While I was trying to parse and convert a Gerber RS274X file to a GDSII file, I encountered a certain problem.

If you stroke a solid circle along a certain path (a polyline), what you get is a solid shape, which can be subsequently converted to a closed polygon. My question would be is there a library or reliable algorithm to automate this process,where the input would be a string of points signifying the polyline, the output would be the resulting polygon.

Below is an image I uploaded to explain my problem.

Answer 1

The algorithm you are talking about is called "Minkowski sum" (in your case, of polyline and of a polygon, approximating a circle). In you case the second summand (the circle) is convex and it means the Minkowski sum can be computed rather efficiently using so called polygon convolution.

You did not specify the language you use. In C++ Minkowski sum is available as part of Boost.Polygon or as part of CGAL.

To use them you will probably need to convert your polyline into a (degenerated) polygon by traversing it twice: forward, then backward.

Union of convex hulls proposed by @melak47 will produce correct result but much less efficiently.