Triangulating Generic Shapes
A demo project implementing an algorithm how intricate concave shapes with holes can be triangulated.
I have been working on a personal project which needed a concave shape triangulation, where the shapes may have large amounts of vertexes, as well as multiple holes. My chosen method was the ear clipping algorithm. Any polygon with at least four vertices has two ears. This algorithm iterates around the polygon edges and always clips off these ears (triangles) and terminates when there is no ears left in the polygon. A naive implementation is O(N3) as for every time an ear is cut off, we have to reconstruct the vertex list. My implementation triangulates the shape in O(N2) time. For the operations of cutting of ears, I implemented a simple linked-list based intermediate data storage in the beginning, which has fast add and remove operations ( O(1) ). More about complexity later. Originally, this algorithm does not support shapes with holes, but applying another algorithm allows triangulating a shape with any amount of holes. The final result is a list of vertices and list of indices of the triangles. For convex shapes the algorithm is fairly simple. I construct a linked list of the vertices and I begin cutting off the ears as I advance: I add the indices triplet to the list and remove the middle index from the linked-list. The algorithm terminates, when there are no more ears, i.e. the current ear has repeating indices.
Your browser needs to support animated SVG to see the demos.
Now, it may be possible that this vertex (let's call it A'), is obscured. If it is not, then we return this as A and we have our bridge vertices. If it is obscured, then we have to look for a vertex, that is mutually visible by B. The process for that is the following: we have a search triangle A'BC, and the A we are looking form, which is visible by B, must be in this triangle. We iterate in the vertices that fall in the area of this triangle and look for the vertex, which has the smallest distance from our ray. Since it was a horizontal ray, it simplifies the problem be just looking for the vertex, that has the smallest y coordinate difference with B. The resulting vertex will be guaranteed to be visible by B and we have the vertices for the bridge. One more thing to pay attention to is if we have more holes than one, we also have carefully choose the order how merge the actual hole with the outer shape. If we choose the order inappropriately, we may build a bridge, that would intersect with another hole. To avoid this, we sort the processing order of the holes by the x coordinates of B in descending order. In other words, we always add the hole, which has rightmost x coordinate and continue until all holes are merged in the shape.
O(N log N) + O(N) + O(N * N) -> O(N2)
With this tool you can do a lot a fun stuff, in this example I used it to triangulate buildings fetched from real map data.
I have been working on a personal project which needed a concave shape triangulation, where the shapes may have large amounts of vertexes, as well as multiple holes. My chosen method was the ear clipping algorithm. Any polygon with at least four vertices has two ears. This algorithm iterates around the polygon edges and always clips off these ears (triangles) and terminates when there is no ears left in the polygon. A naive implementation is O(N3) as for every time an ear is cut off, we have to reconstruct the vertex list. My implementation triangulates the shape in O(N2) time. For the operations of cutting of ears, I implemented a simple linked-list based intermediate data storage in the beginning, which has fast add and remove operations ( O(1) ). More about complexity later. Originally, this algorithm does not support shapes with holes, but applying another algorithm allows triangulating a shape with any amount of holes. The final result is a list of vertices and list of indices of the triangles. For convex shapes the algorithm is fairly simple. I construct a linked list of the vertices and I begin cutting off the ears as I advance: I add the indices triplet to the list and remove the middle index from the linked-list. The algorithm terminates, when there are no more ears, i.e. the current ear has repeating indices.
Your browser needs to support animated SVG to see the demos.
Simple quad has two ears
Animated
The problem becomes a bit more complicated as we want to triangulate concave shapes as well. We cannot include triangles that would lie outside the shape, for that, we have to check if the winding order of the triangle is the same as the winding order of the original shape. My demo supports both orders, as initially I calculate the winding of the whole shape and if the current ear's winding does not match with it, I disregard it.Triangulation of a concave shape
Animated
However, that is not enough unfortunately. We also have to guarantee that no other vertex would be inside our current ear we are about to add. Consider the following V shaped polygon: when we want to add our first ear, that would be invalid, as another polygon is inside (The top of the middle one). To guarantee that the algorithm works for any concave shapes, we also have to check for every ear if no other vertices lie inside the triangle, and if there's any, we disregard clipping the ear.Example polygon, where checking if other vertices are inside the ear triangle is needed
Animated
No we are able to clip any concave shapes without holes.Triangulating a star shape
Triangulating a star shape
However the biggest challenge is clipping shapes with holes, as this algorithm is not capable of that originally. My approach is to merge the inner and the outer shapes by choosing a vertex pair connecting the inner and the outer shape, where there is no intersection. This will be a bridge, which has two directed edges pointing to the other way. The hole has to have the opposite winding as the outer shape to make this work and program further assumes the holes are valid and are inside the shape. As for the bridge: when we reach the connected vertex on the outer shape (let's call this A), we get directed to the connected vertex on the inner hole (let's call this B). We iterate around the inner hole, until we reach the starting point of the inner hole, the B vertex. Then we exit the inner hole to A vertex again on the outer shape and we continue iterating as usual. My approach for this was adding cloned indices for the bridge vertices (A and B) as this was easier for simplifying three-way intersections and not include them in the final result, just refer to the original vertices with the indices. The final result will be only the vertices of the original shapes (outer and holes combined) and indices referring to these shape.Example of bridging outer and inner shape, see green edge that connects A with B
Animated version of triangulated holed mesh
The tricky part is how we locate vertices A and B. As for B, it is simpler: we just locate the rightmost vertex on the current inner hole. As for A, we have to pick a vertex on the outer hole that is visible by B, ie. connecting them does not intersect with any other edges. The algorithm begins by casting a ray from B in the (1, 0) direction, ie. to the right and let's call the closest ray hit in our algorithm C. If the ray hits a vertex on the outer loop, then this will be A and we terminate. If not, we observe the upper and the lower end vertices of the intersected edge and choose the one with higher X coordinate.Now, it may be possible that this vertex (let's call it A'), is obscured. If it is not, then we return this as A and we have our bridge vertices. If it is obscured, then we have to look for a vertex, that is mutually visible by B. The process for that is the following: we have a search triangle A'BC, and the A we are looking form, which is visible by B, must be in this triangle. We iterate in the vertices that fall in the area of this triangle and look for the vertex, which has the smallest distance from our ray. Since it was a horizontal ray, it simplifies the problem be just looking for the vertex, that has the smallest y coordinate difference with B. The resulting vertex will be guaranteed to be visible by B and we have the vertices for the bridge. One more thing to pay attention to is if we have more holes than one, we also have carefully choose the order how merge the actual hole with the outer shape. If we choose the order inappropriately, we may build a bridge, that would intersect with another hole. To avoid this, we sort the processing order of the holes by the x coordinates of B in descending order. In other words, we always add the hole, which has rightmost x coordinate and continue until all holes are merged in the shape.
Example shape with holes. Order of merging holes with shape is also important
Animated
Notice in the following example that how we are looking for the A vertex in the A'BC triangle. The closest vertex to the B is not necessarily going to work, we have to look for the one that is in the triangle, and has the smallest distance from the ray.Example of finding the vertex of the outer hole, if what we initially find was obscured
Animated
Now you have the ability to draw any generic polygon with holes...Triangulating a letter 'A', which is a shape with a hole
Notice that very thin triangles can be added as well
Regarding the complexity, It took O(N log N) to sort holes/merge with shape. It took O(N) to build the linked list data structure, It is O(N) to add ears, and for each ear, we have to see overlapping vertices with this triangle: O(N).O(N log N) + O(N) + O(N * N) -> O(N2)
With this tool you can do a lot a fun stuff, in this example I used it to triangulate buildings fetched from real map data.
Map building data triangulated