core2.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_CORE2_H
#define VCL_ALGORITHMS_CORE_POLYGON_CORE2_H
 
#include <vclib/space/core/polygon.h>
 
namespace vcl {
 
template<Point2Concept PointType>
auto collinearityTest(
    const PointType& p0,
    const PointType& p1,
    const PointType& p2)
{
    return (
        (p1.x() - p0.x()) * (p2.y() - p0.y()) -
        (p2.x() - p0.x()) * (p1.y() - p0.y()));
}
 
template<Point2Concept PointType>
bool areCounterClockwise(
    const PointType& p0,
    const PointType& p1,
    const PointType& p2)
{
    return collinearityTest(p0, p1, p2) > 0;
}
 
template<Point2IteratorConcept Iterator>
bool isCounterClockWise(Iterator begin, Iterator end)
{
    using PointType  = std::decay_t<decltype(*begin)>;
    using ScalarType = PointType::ScalarType;
 
    if (begin == end)
        return false;
 
    auto       latest = begin;
    auto       it     = begin;
    ScalarType sum    = 0;
    for (++it; it != end; ++it) {
        sum += (it->x() - latest->x()) * (it->y() + latest->y());
        latest = it;
    }
 
    sum += (latest->x() - begin->x()) * (latest->y() + begin->y());
 
    return sum < 0;
}
 
template<Point2IteratorConcept Iterator>
void sortConvexPolygonVertices(Iterator begin, Iterator end)
{
    using PointType = std::decay_t<decltype(*begin)>;
 
    // Find the point with the lowest x-coordinate
    PointType minPoint = *std::min_element(
        begin, end, [](const PointType& a, const PointType& b) {
            return a.y() < b.y();
        });
 
    // Sort the points based on the angle with respect to minPoint
    std::sort(begin, end, [minPoint](const PointType& a, const PointType& b) {
        double angleA = std::atan2(a.y() - minPoint.y(), a.x() - minPoint.x());
        double angleB = std::atan2(b.y() - minPoint.y(), b.x() - minPoint.x());
        return angleA < angleB;
    });
}
 
} // namespace vcl
 
#endif // VCL_ALGORITHMS_CORE_POLYGON_CORE2_H