There is a problem: I wanna compute Minkowski sum for two almost convex polygons, where almost convex polygon - polygon, obtained by replacing some edges with arcs with 0 to PI radians in convex polygon.
I hope there is O(n + m) solution, where n, m - numbers of verteces in almost convex polygons.
For convex shapes the problem is trivial, but this problem puzzles me. Could anyone help me with any advice/idea/solution. Thanks in advance!
First, visualize the Minkowski sum (help with that here). Next, understand the area between an arc and a chord (that's the semi-hard part here). If your polygons are convex, and the arc is in the convex direction, then it will only add area to the Minkowski sum. To be specific, it will add exactly that area described by the arc and chord. If and only if you are dealing with convex polygons and arcs in the convex direction, you can simply substitute the exact same arc you used on the polygon as the corresponding edge of the Minkowski sum. Note that each edge of the Minkowski sum corresponds exactly to an edge of one of the relevant polygons.
I made a quick screen cap of a slide from the Minkowski link to illustrate my point. Forgive me that it's inexact, but I think you will get the idea. The purple area would be added to the area of the Minkowski sum.
If you are using this for motion planning or similar, you can adapt traditional algorithms for point containment almost trivially.
Edit: I think if the arcs are in the concave direction, it's simply a matter of area subtraction rather than addition. The important thing to maintain simplicity is that one of the polygons is convex and arc substitution happens on the convex polygon or an edge in the convex hull of the other.
