Ear-clipping triangulation of a polygon with optional holes, as index triples.
Every ring must be simple, rings must not cross or touch one another, and each hole must lie inside the outer ring and outside the others. Holes are joined to the outer ring by bridges to visible vertices, then the merged ring is clipped. Work is O(n^2) per clipped ear, plus O(n^2) per hole for bridging. Any violation, or fewer than three points in a ring, yields an empty vector.
564{
565 std::vector<size_t> bounds { 0 };
566 for (const uint32_t start : hole_starts) {
567 bounds.push_back(start);
568 }
569 bounds.push_back(pts.size());
570
571 for (size_t r = 0; r + 1 < bounds.size(); ++r) {
572 if (bounds[r + 1] < bounds[r] + 3) {
573 return {};
574 }
575 }
576 if (!rings_valid(pts, bounds)) {
577 return {};
578 }
579
580 const size_t rings = bounds.size() - 1;
581 std::vector<std::vector<uint32_t>> ring_idx(rings);
582 for (size_t r = 0; r < rings; ++r) {
583 for (size_t i = bounds[r]; i < bounds[r + 1]; ++i) {
584 ring_idx[r].push_back(static_cast<uint32_t>(i));
585 }
586 }
588 std::ranges::reverse(ring_idx[0]);
589 }
590 for (size_t r = 1; r < rings; ++r) {
592 std::ranges::reverse(ring_idx[r]);
593 }
594 }
595
596 std::vector<uint32_t> merged = ring_idx[0];
597 std::vector<Bridge> bridges;
598 for (size_t r = 1; r < rings; ++r) {
599 const std::vector<uint32_t>& hole = ring_idx[r];
600
601 size_t m = 0;
602 for (size_t t = 1; t < hole.size(); ++t) {
603 if (pts[hole[t]].x > pts[hole[m]].x) {
604 m = t;
605 }
606 }
607 const size_t anchor = hole[m];
608
609 std::optional<size_t> best;
610 float best_d2 = std::numeric_limits<float>::max();
611 for (size_t p = 0; p < merged.size(); ++p) {
612 const glm::vec2 d = pts[anchor] - pts[merged[p]];
613 const float d2 = glm::dot(d, d);
614 if (d2 < best_d2 && bridge_visible(pts, bounds, anchor, merged[p], bridges)) {
615 best_d2 = d2;
616 best = p;
617 }
618 }
619 if (!best) {
620 return {};
621 }
622
623 const size_t p = *best;
624 bridges.push_back({ .a = anchor, .b = merged[p] });
625
626 std::vector<uint32_t> out;
627 out.reserve(merged.size() + hole.size() + 2);
628 out.insert(out.end(), merged.begin(), merged.begin() + static_cast<std::ptrdiff_t>(p) + 1);
629 for (size_t t = 0; t <= hole.size(); ++t) {
630 out.push_back(hole[(m + t) % hole.size()]);
631 }
632 out.push_back(merged[p]);
633 out.insert(out.end(), merged.begin() + static_cast<std::ptrdiff_t>(p) + 1, merged.end());
634 merged = std::move(out);
635 }
636
637 return clip_ears(pts, std::move(merged));
638}
float signed_area(std::span< const glm::vec2 > path) noexcept
Signed area enclosed by treating the path as a closed polygon.