ear_cut.h

/*****************************************************************************
 * VCLib                                                                     *
 * Visual Computing Library                                                  *
 *                                                                           *
 * Copyright(C) 2021-2025                                                    *
 * Visual Computing Lab                                                      *
 * ISTI - Italian National Research Council                                  *
 *                                                                           *
 * All rights reserved.                                                      *
 *                                                                           *
 * This program is free software; you can redistribute it and/or modify      *
 * it under the terms of the Mozilla Public License Version 2.0 as published *
 * by the Mozilla Foundation; either version 2 of the License, or            *
 * (at your option) any later version.                                       *
 *                                                                           *
 * This program is distributed in the hope that it will be useful,           *
 * but WITHOUT ANY WARRANTY; without even the implied warranty of            *
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the              *
 * Mozilla Public License Version 2.0                                        *
 * (https://www.mozilla.org/en-US/MPL/2.0/) for more details.                *
 ****************************************************************************/
 
#ifndef VCL_ALGORITHMS_CORE_POLYGON_EAR_CUT_H
#define VCL_ALGORITHMS_CORE_POLYGON_EAR_CUT_H
 
#include "projection.h"
 
#include <vclib/concepts/mesh.h>
#include <vclib/space/core/polygon.h>
#include <vclib/views/mesh.h>
 
#if __has_include(<mapbox/earcut.hpp>)
#include <mapbox/earcut.hpp>
#else
// inclusion for usage of vclib without CMake - not ideal but necessary for
// header only
#include "../../../../../external/earcut.hpp-2.2.3/include/mapbox/earcut.hpp"
#endif
 
/* Structs to make working the mapbox earcut algorithm on vcl::Point2 */
 
namespace mapbox::util {
 
template<typename Scalar>
struct nth<0, vcl::Point2<Scalar>>
{
    inline static auto get(const vcl::Point2<Scalar>& t) { return t.x(); };
};
 
template<typename Scalar>
struct nth<1, vcl::Point2<Scalar>>
{
    inline static auto get(const vcl::Point2<Scalar>& t) { return t.y(); };
};
 
} // namespace mapbox::util
 
namespace vcl {
 
template<Point2IteratorConcept Iterator>
std::vector<uint> earCut(Iterator begin, Iterator end)
{
    using PointT = Iterator::value_type;
    using Scalar = PointT::ScalarType;
 
    // Convert the polygon represented as a sequence of vertices to a vector
    // of vectors of points. This is necessary because the earcut library
    // expects the polygon to be represented as a vector of contours, where
    // each contour is a vector of points. In this case, there is only one
    // contour, which is represented as a vector of points.
    std::vector<std::vector<Point2<Scalar>>> poly;
    poly.emplace_back(begin, end);
 
    // Use the earcut library to triangulate the polygon and return the
    // result.
    return mapbox::earcut<uint>(poly);
}
 
template<Point3IteratorConcept Iterator>
std::vector<uint> earCut(Iterator begin, Iterator end)
{
    // Project the 3D polygon onto a 2D plane defined by its normal.
    auto poly2D = project(begin, end);
 
    // Use the ear-cut algorithm to triangulate the polygon in the 2D plane
    // and return the result.
    return earCut(poly2D.begin(), poly2D.end());
}
 
template<Range R>
std::vector<uint> earCut(R&& range)
{
    return earCut(std::ranges::begin(range), std::ranges::end(range));
}
 
template<FaceConcept Face>
std::vector<uint> earCut(const Face& polygon)
{
    using CoordType = Face::VertexType::CoordType;
    return earCut(polygon.vertices() | views::coords);
}
 
} // namespace vcl
 
#endif // VCL_ALGORITHMS_CORE_POLYGON_EAR_CUT_H