MayaFlux 1.0.0
Digital-First Multimedia Processing Framework
Loading...
Searching...
No Matches

◆ triangulate_polygon()

MAYAFLUX_API std::vector< std::array< uint32_t, 3 > > MayaFlux::Kinesis::triangulate_polygon ( std::span< const glm::vec2 > pts,
std::span< const uint32_t > hole_starts = {} )
nodiscard

Ear-clipping triangulation of a polygon with optional holes, as index triples.

pts holds the outer ring first, then each hole ring in turn. hole_starts gives the index of the first point of each hole, in increasing order. Each triple indexes pts. Depends only on the point positions, so the result can be cached and reused while the positions are unchanged, or scaled along one axis by a positive factor. Winding may be either direction.

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.

Parameters
ptsRing points in NDC: outer ring, then holes.
hole_startsIndex of the first point of each hole. Empty for no holes.

Definition at line 562 of file Geometry2D.cpp.

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 }
587 if (signed_area(pts, ring_idx[0]) < 0.F) {
588 std::ranges::reverse(ring_idx[0]);
589 }
590 for (size_t r = 1; r < rings; ++r) {
591 if (signed_area(pts, ring_idx[r]) > 0.F) {
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.

References signed_area().

Referenced by fill_polygon(), MayaFlux::Portal::Forma::PolygonFactory::operator()(), and MayaFlux::Portal::Forma::scale_form().

Here is the call graph for this function:
Here is the caller graph for this function: