Generating a beveled edge for a 2D polygon

Question

I'm trying to programmatically generate beveled edges for geometric polygons. For example, given an array of 4 vertices defining a square, I want to generate something like this. But computing the vertices of the inner shape is baffling me.

Simply creating a copy of the original shape and then scaling it down will not produce the desired result most of the time.

My algorithm so far involves analyzing adjacent edges (triples of vertices; e.g., the bottom-left, top-left, and top-right vertices of a square). From there, I need to find the angle between them, and then create a vertex somewhere along that angle, depending on how deep I want the bevel to be.

And because I don't have much of a math background, that's where I'm stuck. How do I find that center angle? Or is there a much simpler way of attacking this problem?

Answer 1

I would do something like this:

for each side, make a copy and push it 'inward' the desired width of the bevel. ('inward' being along the normal vector of the side). Once you've done this, find the intersection points between the new copies (and the copies of whichever sides they previously intersected) and use those as the vertices for your inner shape. For the intersections, you'll need consider true lines (rather than segments), since sides in concave regions will need to grow.

This will break horribly if you try to use it on a shape with regions less then twice the width of your bevel size, but should be fine otherwise. (I'm sure you could add something to handle those cases, but that's another discussion)

Alternately, if you wanted the bevel width to be relative to vertices, you could also just push those 'inward' using the same principle. Estimate the vertice's normal angle by averaging the normals of the side it connects.

Answer 2

Let say your point is p1 and points creating adjacent edges are points p2 and p3. Then take a vector from p1 to p2 and p1 to p3. like -

v1 = p2 - p1
v2 = p3 - p1

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

Answer 3

The general algorithm is pretty complex. The operation you're looking for is known as offsetting the polygon; if you search around for that you might find some pointers/papers, etc.

If you're working in or near C++, you could try CGAL.