Create a beveled edge for a two-dimensional polygon

Question

I am trying to programmatically generate beveled edges for two-dimensional polygons. For example, given an array of 4 vertices defining a square, I want to generate something like this:

_________ |\ _____ /| | | | | | | | | | |_____| | |/_______\| 

But calculating the vertices of the inner form puzzles me.

Simply creating a copy of the original form and scaling it will not work in the general case. (Imagine trying to skew an N-shaped polygon this way.)

My algorithm so far includes the analysis of adjacent edges (triples of vertices, for example, the lower left, upper left and upper right vertices of a square). From there I need to find the angle between them, and then create a vertex somewhere along this corner, depending on how deep I want the bevel to be.

And because I don’t have so much mathematical background that I’m stuck. How to find this central corner? Or is there a much simpler way to attack this problem?

Answer 1

The general algorithm is quite complicated. The operation you are looking for is called polygon offset; if you are looking for this, you can find some pointers / documents, etc.

If you work in or near C ++, you can try CGAL .

Answer 2

I would do something like this:

For each side, make a copy and press inward the desired bevel width. ("inward" - along the normal side vector). Once you do this, find the intersection points between the new copies (and the copies of the sides that they previously crossed), and use them as vertices for your inner shape. For intersections, you will need to consider the true lines (rather than segments), since the sides in the concave areas will need to grow.

This will be terribly broken if you try to use it in a form with areas not exceeding twice the width of your bevel size, but in any case, everything should be fine. (I'm sure you could add something to handle these cases, but this is another discussion)

Alternatively, if you want the bevel width to be relative to the vertices, you can also just push them inwards using the same principle. Estimate the normal vertex angle by averaging the normals of the side with which it connects.

Answer 3

Say your point is p1, and the points creating adjacent edges are points p2 and p3. Then we take the vector from p1 to p2 and p1 to p3. as -

 v1 = p2 - p1 v2 = p3 - p1 

Find the angle between v1 and v2 and create your point. You can find the angle using this .