polygon.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_SPACE_CORE_POLYGON_H
#define VCL_SPACE_CORE_POLYGON_H
 
#include "point.h"
#include "triangle.h"
 
#include <ranges>
#include <vector>
 
namespace vcl {
 
template<PointConcept PointT>
class Polygon
{
    std::vector<PointT> mPoints;
 
public:
    using ScalarType = PointT::ScalarType;
 
    using PointType = PointT;
 
    using Iterator = typename std::vector<PointT>::iterator;
 
    using ConstIterator = typename std::vector<PointT>::const_iterator;
 
    static const uint DIM = PointT::DIM;
 
    Polygon() {}
 
    Polygon(std::initializer_list<PointT> points) : mPoints(points) {}
 
    template<typename Iterator>
    Polygon(Iterator begin, Iterator end)
        requires (std::is_same_v<typename Iterator::value_type, PointT>)
            : mPoints(begin, end)
    {
    }
 
    template<Range R>
    Polygon(R&& range) requires (InputRange<R, PointT>)
            : mPoints(std::ranges::begin(range), std::ranges::end(range))
    {
    }
 
    uint size() const { return mPoints.size(); }
 
    void resize(uint n) { mPoints.resize(n); }
 
    void reserve(uint n) { mPoints.reserve(n); }
 
    void clear() { mPoints.clear(); }
 
    void pushBack(const PointT& point) { mPoints.push_back(point); }
 
    void pushBack(PointT&& point) { mPoints.push_back(std::move(point)); }
 
    PointT& point(uint i) { return mPoints.at(i); }
 
    const PointT& point(uint i) const { return mPoints.at(i); }
 
    ScalarType sideLength(uint i) const
    {
        return mPoints.at(i).dist(mPoints[(i + 1) % mPoints.size()]);
    }
 
    PointT normal() const requires (PointT::DIM == 3)
    {
        return normal(mPoints);
    }
 
    PointT barycenter() const { return barycenter(mPoints); }
 
    template<typename WIterator>
    PointT weightedBarycenter(WIterator wBegin) const
    {
        return weightedBarycenter(mPoints.begin(), mPoints.end(), wBegin);
    }
 
    ScalarType perimeter() const { return perimeter(mPoints); }
 
    ScalarType area() const { return area(mPoints); }
 
    PointType& operator[](uint i) { return mPoints[i]; }
 
    const PointType& operator[](uint i) const { return mPoints[i]; }
 
    Iterator begin() { return mPoints.begin(); }
 
    Iterator end() { return mPoints.end(); }
 
    ConstIterator begin() const { return mPoints.begin(); }
 
    ConstIterator end() const { return mPoints.end(); }
 
    // static member functions
 
    template<typename Iterator>
    static PointT normal(Iterator begin, Iterator end) requires (
        std::is_same_v<typename Iterator::value_type, PointT> &&
        PointT::DIM == 3)
    {
        // compute the sum of normals for each triplet of consecutive points
        PointT sum;
        sum.setZero();
        for (auto i = begin; i != end; ++i) {
            auto i1 = i;
            ++i1;
            if (i1 == end)
                i1 = begin;
 
            auto i2 = i1;
            ++i2;
            if (i2 == end)
                i2 = begin;
 
            sum += (*i1 - *i).cross(*i2 - *i);
        }
        sum.normalize();
        return sum;
    }
 
    template<Range R>
    static PointT normal(R&& range)
    {
        return normal(std::ranges::begin(range), std::ranges::end(range));
    }
 
    template<typename Iterator>
    static PointT barycenter(Iterator begin, Iterator end)
        requires (std::is_same_v<typename Iterator::value_type, PointT>)
    {
        PointT bar;
        bar.setZero();
 
        uint cnt = 0;
        for (; begin != end; ++begin) {
            bar += *begin;
            ++cnt;
        }
 
        assert(cnt);
 
        return bar / cnt;
    }
 
    template<Range R>
    static PointT barycenter(R&& range)
    {
        return barycenter(std::ranges::begin(range), std::ranges::end(range));
    }
 
    template<typename Iterator, typename WIterator>
    static PointT weightedBarycenter(
        Iterator  begin,
        Iterator  end,
        WIterator wBegin)
        requires (std::is_same_v<typename Iterator::value_type, PointT>)
    {
        using ScalarType = WIterator::value_type;
 
        PointT bar;
        bar.setZero();
        ScalarType wSum = 0;
 
        for (; begin != end; ++begin, ++wBegin) {
            bar += *begin * *wBegin;
            wSum += *wBegin;
        }
 
        return bar / wSum;
    }
 
    template<Range Rp, Range Rw>
    static PointT weightedBarycenter(Rp&& rPolygon, Rw&& rWeights)
    {
        return weightedBarycenter(
            std::ranges::begin(rPolygon),
            std::ranges::end(rPolygon),
            std::ranges::begin(rWeights));
    }
 
    template<typename Iterator>
    static ScalarType perimeter(Iterator begin, Iterator end)
        requires (std::is_same_v<typename Iterator::value_type, PointT>)
    {
        using Scalar = PointType::ScalarType;
 
        Scalar per = 0;
        for (auto i = begin; i != end; ++i) {
            const PointT& p0 = *i;
            auto          i1 = i;
            ++i;
            if (i1 == end)
                i1 = begin;
            const PointT& p1 = *i1;
            per += p0.dist(p1);
        }
        return per;
    }
 
    template<Range R>
    static ScalarType perimeter(R&& range)
    {
        return perimeter(std::ranges::begin(range), std::ranges::end(range));
    }
 
    template<typename Iterator>
    static ScalarType area(Iterator begin, Iterator end)
        requires (std::is_same_v<typename Iterator::value_type, PointT>)
    {
        using Scalar = PointType::ScalarType;
 
        PointType bar  = barycenter(begin, end);
        Scalar    area = 0;
        for (auto i = begin; i != end; ++i) {
            const PointT& p0 = *i;
            auto          i1 = i;
            ++i1;
            if (i1 == end)
                i1 = begin;
            const PointT& p1 = *i1;
 
            area += Triangle<PointT>::area(p0, p1, bar);
        }
        return area;
    }
 
    template<Range R>
    static ScalarType area(R&& range)
    {
        return area(std::ranges::begin(range), std::ranges::end(range));
    }
};
 
/* Specialization Aliases */
 
template<typename Scalar>
using Polygon2 = Polygon<Point2<Scalar>>;
 
using Polygon2f = Polygon<Point2f>;
 
using Polygon2d = Polygon<Point2d>;
 
template<typename Scalar>
using Polygon3 = Polygon<Point3<Scalar>>;
 
using Polygon3f = Polygon<Point3f>;
 
using Polygon3d = Polygon<Point3d>;
 
/* Concepts */
 
template<typename T>
concept PolygonConcept = std::derived_from< // same type or derived type
    std::remove_cvref_t<T>,
    Polygon<typename RemoveRef<T>::PointType>>;
 
template<typename T>
concept Polygon2Concept = PolygonConcept<T> && RemoveRef<T>::DIM == 2;
 
template<typename T>
concept Polygon3Concept = PolygonConcept<T> && RemoveRef<T>::DIM == 3;
 
} // namespace vcl
 
#endif // VCL_SPACE_CORE_POLYGON_H