CODEWITHSUNDEEP
c#c++algorithmimage-processing
david lin
david lin

Reputation: 59

Converting a polyline to a polygonal shape with width

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.

enter image description here

Upvotes: 4

Views: 2327

Answers (2)

Michael Simbirsky
Michael Simbirsky

Reputation: 3103

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.

Upvotes: 2

melak47
melak47

Reputation: 4850

The shape you seek can be calculated by placing a desired number of evenly spaced points in a circle around each input point, and then finding the convex hull for each pair of circles on a line segment. The union of these polygons will make up the polygon you want.

There are a number of algorithms that can find the convex hull for a set of points, and also libraries which provide implementations.

Upvotes: 1

Related Questions