12
\$\begingroup\$

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).

enter image description here

(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?

\$\endgroup\$
  • \$\begingroup\$ Are we talking about 2D here? because in 3D combining polygons doesn't really make a lot of sense. \$\endgroup\$ – concept3d Mar 3 '14 at 23:24
  • \$\begingroup\$ Yes, sry, I'm talking about 2D! Though I don't see why it does not make less sense in 3D than in 2D. \$\endgroup\$ – Sebastian Barth Mar 4 '14 at 7:10
  • 2
    \$\begingroup\$ adding two polygons in 3D, if they are flat, it doesn't make much sense unless they are on the same plane, if they have volume (solids) then it's a different story. \$\endgroup\$ – concept3d Mar 4 '14 at 7:14
  • \$\begingroup\$ Ok, I've got it. I was not thinking about graphics, but collision objects. Thank you for the clarification. \$\endgroup\$ – Sebastian Barth Mar 4 '14 at 7:20
  • \$\begingroup\$ For addition, find all the points they intersect and add the vertices to a set. The set is important to prevent overlap. Then, simply add every other vertices from the other two shapes into the set. This set contains all the vertices of the additive shape. \$\endgroup\$ – Vaughan Hilts Mar 4 '14 at 18:44
9
\$\begingroup\$

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

enter image description here

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

\$\endgroup\$
  • \$\begingroup\$ Cool, but counter-intuitive, considering that a BSP of a convex polygon or polyhedron is a list. Great paper. \$\endgroup\$ – 3Dave Mar 10 '14 at 20:44
  • \$\begingroup\$ @DavidLively yes, but can make it a balanced tree by choosing the root plane to be non of the faces. Actually this is part of the challenge that they don't talk about \$\endgroup\$ – concept3d Mar 11 '14 at 5:12
  • \$\begingroup\$ Ah, that makes sense. Sort of a hybrid BSP, then. \$\endgroup\$ – 3Dave Mar 11 '14 at 14:02
  • \$\begingroup\$ @DavidLively also the BSP is not really easy to render, though the OP question is a simple case, in a more complex case with geometry of million of polygons, once you finished the tree construction you are far from done. \$\endgroup\$ – concept3d Mar 11 '14 at 14:08
  • \$\begingroup\$ @concept3d I hope this won't be too annoying since this is a 5 years old answer, but there's two things I don't really understand: When trying to determine whether a point lies on the left or right of a plane/line, wouldn't it be easier to simply rotate the whole thing so the plane/line corresponds to a trivial plane/line, and then just consider the coordinates of the rotated point? How about using the Sutherland–Hodgman algorithm instead of BSP trees? Sounds quite similar to this approach. \$\endgroup\$ – John P Mar 22 at 0:21
1
\$\begingroup\$

Going by your example:

Pick a starting vertex on polygon A, and then start checking for intersecting edges clockwise (or counterclockwise). If there isn't an intersection, add the previous vertex to your resulting polygon. If there is an intersection, add the point at which they intersected to your resulting polygon, and then start iterating over polygon B, in the same winding order. Do the same thing, again swapping to polygon A if an intersection occurs.

Once you've accumulated all the vertices for the new polygon, perform a triangulation algorithm on it. The ear clipping method is easy to implement, but there are faster options out there.

Important: ensure the vertex you start at isn't inside the other polygon (check this article for point in polygon tests).

Iterating over each edge, to check for an intersection would be an O(n^2) algorithm. You could speed it up by first finding the vertices that are inside the other polygon, as the edges linked to those vertices will be the intersecting ones.

\$\endgroup\$
0
\$\begingroup\$

If you want a concave polygon, just pick the closest edge between the two input polygons, and add two new edges:

enter image description here

Convex gets slightly more complicated:

enter image description here

One approach is iterative in that it adds vertices from the second polygon to the first, one at a time, evolving the first polygon into a container that encompasses everything.

Basically:

  • Iterate through the second polygon's vertices.
  • For each vertex V, iterate through the first polygon's edges:
  • Find a "range" of edges that all face the vertex
  • take the outer pair of vertices that define that range, and remove all edges in the range that connects them
  • Draw two new segments from those outer vertices to the new vertex (from the second polygon), making sure that the new edges face the correct direction.
  • Proceed to the next vertex from the second polygon

Here's a diagram illustrating the process for the first vertex:

enter image description here

A faster method is to find the list of edges on each polygon that do not face the other polygon, remove everything else, and connect the endpoints of the remaining line strips to each other.

Perhaps someone else can chime in with some subtraction advice.

\$\endgroup\$
  • \$\begingroup\$ This only seems to address half the problem (addition). It might also be good to point out how the algorithms works or could be optimized if the polygons overlap. \$\endgroup\$ – Josh Mar 7 '14 at 16:17
  • \$\begingroup\$ The algorithm implicitly ignores vertices that are "inside" of the target polygon, which also compensates for the issue where an edge from the second polygon crosses the first. \$\endgroup\$ – 3Dave Mar 7 '14 at 16:53
  • \$\begingroup\$ That almost equals the merge phase (point 4. of the merge hull algorithm. In my case it is not a correct solution to enclose more area after combining the polygons. The correct solution would be to keep both polygons as they are since they aren't overlapping, nor touching. \$\endgroup\$ – Sebastian Barth Mar 10 '14 at 13:44
  • \$\begingroup\$ @luftgewehrindianer Ah - Yeah, that makes a big difference. Perhaps I misunderstood the question. Are you looking to add the polygons together, without worrying about whether the result is convex or concave? Or generate a convex set based on the intersection? (Ignoring subtraction for the moment.) \$\endgroup\$ – 3Dave Mar 10 '14 at 14:37
  • \$\begingroup\$ @DavidLively Imagine two convex polygons of the same color and without border stoke. When they overlap, it looks like one new convex or concave polygon. He tries to find a triangulation of the combined shape. Don't add area between both polygons. \$\endgroup\$ – danijar Mar 10 '14 at 20:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.