algorithm - How can I add and subtract convex polygons?

I have two 2D convex polygons overlapping each other. I am looking for an algorithm to subtract and add them. The result must be a single concave polygon or (even better) a set of biggest convex ones forming the concave result (e.g. triangles).

(Left: The initial overlapping polygons. Middle: The resulting concave polygon after adding. Right: A set of convex polygons forming the concave result. Here it would be better to get convex polygons bigger than a triangle for performance reasons. An subtraction of the two overlapping polygons would lead to the same picture as on the left but with the overlapping area not being part of the resulting polygon.)

How can I do this?

Answer

TL;DR You need to implement boolean operations using BSP trees.

Well, it seems we are talking about Constructive Solid Geometry here. I have implemented CSG on a commercial level so I know a thing or two about it.

The classic paper about CSG is called Merging BSP Trees Yields Polyhedral Set Operations, to be honest it's too much to explain here, but briefly speaking the algorithm deals with polygon(s) that lay on the same plane as a binary space partitioning, basically constructing a BSP tree from each polygonal mesh. The second step is to merge those BSP trees; you simply take one tree and insert it into the other. The algorithm then proceeds to explain how to deal with each leaf node for dividing and substracting the nodes, nodes that are not needed in the final shape will be removed, others will be given the appropriate parent.

But wait! That paper is basically speaking about polygonal meshes and 3D planes, NO?

The algorithm can be generalized into any dimension, so in your 2D case it's easy to use line segments instead of plane as the binary partitions. So each polygon will be converted into a BSP tree than the two will be merged. Finally you traverse the resulting tree to generate the final polygon,

Note that this algorithm and CSG in general doesn't deal with rendering and mesh faces directly and isn't really rendering ready, so you need to extract the faces of the final BSP trees. I also find ray tracing an easier approach for rendering the CSG result, you only need the rays to traverse the tree instead of extracting and actually splitting the faces (remember we only deal with binary partitions).

Regarding numerical robustness. It's good to note that there are two types of geometric computations,

• Those that are based on construction, you construct a shape based on the result of a previous operation. For example y = sqrt(x) and then use y in a new operation. This is called construction; the problem is that numerical errors will accumulate quickly.



• Alternatively there are operations that use predicates instead, essentially instead of using construction you simply ask whether a condition is true/false and use the same value in different operation. Classic tests include incircle and the orientation test; this is also suspect to numerical errors especially if you use single or double precision but will usually give a much better results. other solutions that vary on speed and accuracy exist. Here is one of the recent papers that avoid construction by using a plane based geometry to give accurate results. I will also quote from the paper:

The concept of plane-based representation of polygonal meshes was first described by Sugihara and Iri [SI89]. This kind of representation provides one important advantage when it comes to tasks that involve changing the topology of solids represented by meshes like the evaluation of Boolean expressions: no new primary geometry information has to be constructed to obtain the resulting polyhedron

And finally I would like to add, if you like to start your BSP CSG implementation I would recommend starting on BSP Faqs.