VecGeom/base/Triangulation.h

0001 /// @file Triangulation.h
0002 /// @brief Generic polygon triangulation helpers.
0003
0004 #ifndef VECGEOM_BASE_TRIANGULATION_H
0005 #define VECGEOM_BASE_TRIANGULATION_H
0006
0007 #include "VecGeom/base/Config.h"
0008 #include "VecGeom/base/Vector.h"
0009
0010 namespace vecgeom {
0011 inline namespace VECGEOM_IMPL_NAMESPACE {
0012
0013 /// @brief Triangulate a simple polygon by ear clipping.
0014 /// @details The loop clips one ear, erases its center vertex, then restarts from
0015 /// candidate `(0,1,2)`. Callers provide the geometric predicates so existing
0016 /// orientation and tolerance conventions remain local to the polygon type.
0017 /// @return True when at least one triangle was produced and every ear was found.
0018 template <typename TriangleList, typename MakeTriangle, typename IsConvexCorner, typename ContainsPoint>
0019 bool TriangulateEarClipping(size_t nvertices, TriangleList &triangles, MakeTriangle make_triangle,
0020                             IsConvexCorner is_convex_corner, ContainsPoint contains_point)
0021 {
0022   if (nvertices < 3) return false;
0023
0024   const size_t initial_size = triangles.size();
0025   Vector<size_t> indices;
0026   for (size_t index = 0; index < nvertices; ++index)
0027     indices.push_back(index);
0028
0029   size_t previous = 0;
0030   size_t current  = 1;
0031   size_t next     = 2;
0032   while (indices.size() > 2) {
0033     bool found_ear = false;
0034     for (size_t attempt = 0; attempt < indices.size(); ++attempt) {
0035       const size_t first  = indices[previous];
0036       const size_t second = indices[current];
0037       const size_t third  = indices[next];
0038       bool good_ear       = is_convex_corner(first, second, third);
0039
0040       for (size_t index : indices) {
0041         if (!good_ear) break;
0042         if (index == first || index == second || index == third) continue;
0043         good_ear = !contains_point(first, second, third, index);
0044       }
0045
0046       if (good_ear) {
0047         triangles.push_back(make_triangle(first, second, third));
0048         indices.erase(indices.begin() + current);
0049         previous  = 0;
0050         current   = 1;
0051         next      = 2;
0052         found_ear = true;
0053         break;
0054       }
0055       previous = (previous + 1) % indices.size();
0056       current  = (current + 1) % indices.size();
0057       next     = (next + 1) % indices.size();
0058     }
0059     if (!found_ear) return false;
0060   }
0061   return triangles.size() != initial_size;
0062 }
0063
0064 } // namespace VECGEOM_IMPL_NAMESPACE
0065 } // namespace vecgeom
0066
0067 #endif