kev/Drawer/Module/GeoSigmaDraw/PolygonSnapper.h

#pragma once

#include <vector>
#include <cmath>
#include <algorithm>
#include <map>
#include "DrawOperator/CurveEx.h" // ȷ<><C8B7><EFBFBD><EFBFBD><EFBFBD><EFBFBD> CurveEx <20>Ķ<EFBFBD><C4B6><EFBFBD>

#pragma push_macro("min")
#pragma push_macro("max")

#undef min
#undef max

/**
 * \struct Vec2
 * \brief <EFBFBD><EFBFBD><EFBFBD>ڼ<EFBFBD><EFBFBD>μ<EFBFBD><EFBFBD><EFBFBD><EFBFBD>ļ򵥶<EFBFBD>ά<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ṹ<EFBFBD><EFBFBD>
 */
struct Vec2
{
    double x; ///< X <20><><EFBFBD><EFBFBD>
    double y; ///< Y <20><><EFBFBD><EFBFBD>

    /**
     * \brief <EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ӷ<EFBFBD><EFBFBD><EFBFBD>
     */
    Vec2 operator+(const Vec2& v) const
    {
        return { x + v.x, y + v.y };
    }

    /**
     * \brief <EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
     */
    Vec2 operator-(const Vec2& v) const
    {
        return { x - v.x, y - v.y };
    }

    /**
     * \brief <EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>˷<EFBFBD><EFBFBD><EFBFBD>
     */
    Vec2 operator*(double s) const
    {
        return { x * s, y * s };
    }

    /**
     * \brief <EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ĵ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
     */
    double dot(const Vec2& v) const
    {
        return x * v.x + y * v.y;
    }

    /**
     * \brief <EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ȵ<EFBFBD>ƽ<EFBFBD><EFBFBD><EFBFBD><EFBFBD>
     * \note <EFBFBD><EFBFBD> length() <EFBFBD>죬<EFBFBD><EFBFBD>Ϊ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>˿<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>㡣
     */
    double lengthSq() const
    {
        return x * x + y * y;
    }

    /**
     * \brief <EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ij<EFBFBD><EFBFBD><EFBFBD> (ģ)<EFBFBD><EFBFBD>
     */
    double length() const
    {
        return std::sqrt(lengthSq());
    }
};

/**
 * \class RigidSnapper
 * \brief ְ<EFBFBD><EFBFBD><EFBFBD><EFBFBD> 1<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ƽ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
 * \details <EFBFBD><EFBFBD><EFBFBD>ฺ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>㲢Ӧ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ƽ<EFBFBD>ƣ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ŀ<EFBFBD>ꡣ
 * <EFBFBD><EFBFBD><EFBFBD>ϸ񱣳ֶ<EFBFBD><EFBFBD><EFBFBD><EFBFBD>ε<EFBFBD>ԭʼ<EFBFBD><EFBFBD>״<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>α䣩<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ı<EFBFBD>λ<EFBFBD>á<EFBFBD>
 */
class RigidSnapper
{
public:
    /**
     * \brief Ӧ<EFBFBD>ø<EFBFBD><EFBFBD><EFBFBD>ƽ<EFBFBD><EFBFBD><EFBFBD>Զ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ρ<EFBFBD>
     * \param polygons <EFBFBD><EFBFBD>Ҫ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ķ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>б<EFBFBD><EFBFBD><EFBFBD>
     * \param threshold <EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ֵ<EFBFBD><EFBFBD>
     * \param angleDeg <EFBFBD>ж<EFBFBD><EFBFBD><EFBFBD>ƽ<EFBFBD>е<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ǶȲ<EFBFBD>ȣ<EFBFBD><EFBFBD><EFBFBD>
     */
    static void Apply(std::vector<CCurveEx*>& polygons, double threshold, double angleDeg)
    {
        if (polygons.size() < 2)
        {
            return;
        }

        double angleRad = angleDeg * 3.1415926535 / 180.0;
        double minCos = std::cos(angleRad);

        for (size_t i = 0; i < polygons.size(); ++i)
        {
            CCurveEx* sourcePolygon = polygons[i];

            Vec2 bestTranslation = { 0, 0 };
            double minDistance = threshold;
            bool foundSnap = false;

            for (size_t j = 0; j < polygons.size(); ++j)
            {
                if (i == j)
                {
                    continue;
                }

                CCurveEx* targetPolygon = polygons[j];

                // <20>ȶ<EFBFBD><C8B6>Լ<EFBFBD><D4BC>飺ֻ<E9A3BA><D6BB><EFBFBD><EFBFBD><EFBFBD>Լ<EFBFBD><D4BC><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ߴ<EFBFBD><DFB4><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
                // <20><><EFBFBD><EFBFBD><EFBFBD>Է<EFBFBD>ֹС<D6B9><D0A1>м<EFBFBD>϶<EFBFBD><CFB6><EFBFBD><EFBFBD>Ľṹ<C4BD>塣
                if (GetArea(targetPolygon) < GetArea(sourcePolygon) * 0.8)
                {
                    continue;
                }

                Vec2 edgeMove;
                double edgeDistance = 0.0;
                if (FindBestEdgeSnap(sourcePolygon, targetPolygon, minCos, edgeMove, edgeDistance))
                {
                    if (edgeDistance < minDistance)
                    {
                        minDistance = edgeDistance;
                        bestTranslation = edgeMove;
                        foundSnap = true;
                    }
                }
            }

            // <20><><EFBFBD><EFBFBD><EFBFBD>ҵ<EFBFBD><D2B5><EFBFBD><EFBFBD><EFBFBD>Ч<EFBFBD><D0A7><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ŀ<EFBFBD>꣬Ӧ<EAA3AC><D3A6>ƽ<EFBFBD><C6BD>
            if (foundSnap)
            {
                for (int k = 0; k < sourcePolygon->num; ++k)
                {
                    sourcePolygon->x[k] += bestTranslation.x;
                    sourcePolygon->y[k] += bestTranslation.y;
                }
            }
        }
    }

private:
    /**
     * \brief <EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ε<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
     */
    static double GetArea(CCurveEx* polygon)
    {
        return polygon->Area();
    }

    /**
     * \brief <EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>߶<EFBFBD><EFBFBD><EFBFBD>Ŀ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ϵ<EFBFBD>ͶӰ<EFBFBD>Ƿ<EFBFBD><EFBFBD>ص<EFBFBD><EFBFBD><EFBFBD>
     * \details <EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Է<EFBFBD>ֹ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Щ<EFBFBD><EFBFBD>Ȼƽ<EFBFBD><EFBFBD><EFBFBD>Ҿ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ȫ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>߶Ρ<EFBFBD>
     */
    static bool IsLineOverlap(Vec2 a1, Vec2 a2, Vec2 b1, Vec2 b2)
    {
        Vec2 axis = b2 - b1;
        if (axis.lengthSq() < 1e-9)
        {
            return false;
        }

        auto project = [&](Vec2 p) { return p.dot(axis); };
        double minA = std::min(project(a1), project(a2));
        double maxA = std::max(project(a1), project(a2));
        double minB = std::min(project(b1), project(b2));
        double maxB = std::max(project(b1), project(b2));

        // <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ص<EFBFBD>
        return std::max(minA, minB) < std::min(maxA, maxB) - 1e-3;
    }

    /**
     * \brief Ѱ<EFBFBD>ҽ<EFBFBD>Դ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>εı߶<EFBFBD><EFBFBD>뵽Ŀ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>αߵ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ƽ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
     * \return <EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ҵ<EFBFBD><EFBFBD><EFBFBD><EFBFBD>ʵı<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>򷵻<EFBFBD> true<EFBFBD><EFBFBD>
     */
    static bool FindBestEdgeSnap(CCurveEx* sourcePolygon, CCurveEx* targetPolygon, double minCos, Vec2& outMove, double& outDistance)
    {
        bool found = false;
        outDistance = 1e9;

        for (int i = 0; i < sourcePolygon->num - 1; ++i)
        {
            Vec2 sourcePoint1 = { sourcePolygon->x[i], sourcePolygon->y[i] };
            Vec2 sourcePoint2 = { sourcePolygon->x[i + 1], sourcePolygon->y[i + 1] };
            Vec2 sourceDirection = sourcePoint2 - sourcePoint1;

            if (sourceDirection.lengthSq() < 1e-9)
            {
                continue;
            }

            Vec2 sourceNormal = { sourceDirection.y, -sourceDirection.x };
            sourceNormal = sourceNormal * (1.0 / sourceDirection.length());

            for (int j = 0; j < targetPolygon->num - 1; ++j)
            {
                Vec2 targetPoint1 = { targetPolygon->x[j], targetPolygon->y[j] };
                Vec2 targetPoint2 = { targetPolygon->x[j + 1], targetPolygon->y[j + 1] };
                Vec2 targetDirection = targetPoint2 - targetPoint1;

                if (targetDirection.lengthSq() < 1e-9)
                {
                    continue;
                }

                Vec2 targetNormal = { targetDirection.y, -targetDirection.x };
                targetNormal = targetNormal * (1.0 / targetDirection.length());

                // <20><><EFBFBD><EFBFBD> 1: <20>߶<EFBFBD><DFB6>Ƿ<EFBFBD>ƽ<EFBFBD>У<EFBFBD>
                if (std::abs(sourceNormal.dot(targetNormal)) < minCos)
                {
                    continue;
                }

                // <20><><EFBFBD><EFBFBD> 2: ͶӰ<CDB6>Ƿ<EFBFBD><C7B7>ص<EFBFBD><D8B5><EFBFBD>
                if (!IsLineOverlap(sourcePoint1, sourcePoint2, targetPoint1, targetPoint2))
                {
                    continue;
                }

                // <20><><EFBFBD><EFBFBD>Դ<EFBFBD>߶<EFBFBD><DFB6><EFBFBD><EFBFBD>ĵ<EFBFBD>Ŀ<EFBFBD><C4BF>ֱ<EFBFBD>ߵĴ<DFB5>ֱ<EFBFBD><D6B1><EFBFBD><EFBFBD>
                Vec2 sourceMidPoint = (sourcePoint1 + sourcePoint2) * 0.5;
                double distance = std::abs((sourceMidPoint - targetPoint1).dot(targetNormal));

                if (distance < outDistance)
                {
                    outMove = targetNormal * (-(sourceMidPoint - targetPoint1).dot(targetNormal));
                    outDistance = distance;
                    found = true;
                }
            }
        }
        return found;
    }
};

/**
 * \class ClusterGapFiller
 * \brief ְ<EFBFBD><EFBFBD><EFBFBD><EFBFBD> 2<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ಹ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
 * \details <EFBFBD><EFBFBD><EFBFBD>ฺ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>΢С<EFBFBD><EFBFBD><EFBFBD>κͷ<EFBFBD>϶<EFBFBD>޸<EFBFBD><EFBFBD><EFBFBD>
 * <EFBFBD><EFBFBD>ʶ<EFBFBD><EFBFBD>λ<EFBFBD><EFBFBD><EFBFBD>غϵĶ<EFBFBD><EFBFBD><EFBFBD><EFBFBD>أ<EFBFBD><EFBFBD><EFBFBD>ȷ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ƶ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ͶӰ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ı<EFBFBD><EFBFBD><EFBFBD><EFBFBD>ԱպϷ<EFBFBD>϶<EFBFBD><EFBFBD>
 * ֧<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ֱ<EFBFBD>ߵ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>޸<EFBFBD><EFBFBD>˵<EFBFBD><EFBFBD><EFBFBD><EFBFBD>⡣
 */
class ClusterGapFiller
{
public:
    /**
     * \brief Ӧ<EFBFBD>ò<EFBFBD><EFBFBD><EFBFBD><EFBFBD>߼<EFBFBD><EFBFBD><EFBFBD>
     * \param polygons Ҫ<EFBFBD>޸ĵĶ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>б<EFBFBD><EFBFBD><EFBFBD>
     * \param snapRadius Ѱ<EFBFBD><EFBFBD>Ŀ<EFBFBD><EFBFBD><EFBFBD>ߵ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>뾶<EFBFBD><EFBFBD>
     * \param maxExtension <EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ֱ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>췽<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>롣
     */
    static void Apply(std::vector<CCurveEx*>& polygons, double snapRadius, double maxExtension)
    {
        if (polygons.empty())
        {
            return;
        }

        // 1. <20><><EFBFBD><EFBFBD><EFBFBD>׶<EFBFBD> (Clustering Phase)
        // <20>ҳ<EFBFBD><D2B3><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>λ<EFBFBD><CEBB><EFBFBD>غϵĶ<CFB5><C4B6>㣬<EFBFBD><E3A3AC><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>DZ<EFBFBD><C7B1><EFBFBD>Ϊ<EFBFBD><CEAA><EFBFBD>ء<EFBFBD><D8A1><EFBFBD>
        // <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD>֤<EFBFBD><D6A4><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD> A <20>Ͷ<EFBFBD><CDB6><EFBFBD><EFBFBD><EFBFBD> C <20><><EFBFBD><EFBFBD>һ<EFBFBD><D2BB><EFBFBD><EFBFBD><EFBFBD>㣬<EFBFBD><E3A3AC><EFBFBD>ǻ<EFBFBD>һ<EFBFBD><D2BB><EFBFBD>ƶ<EFBFBD><C6B6><EFBFBD>
        auto clusters = BuildClusters(polygons);

        // 2. <20><><EFBFBD><EFBFBD><EFBFBD>׶<EFBFBD> (Snapping Phase)
        // <20><>ÿ<EFBFBD><C3BF><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ϊһ<CEAA><D2BB><EFBFBD><EFBFBD><EFBFBD>崦<EFBFBD><E5B4A6><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ѵ<EFBFBD>Ŀ<EFBFBD><C4BF><EFBFBD><EFBFBD><EFBFBD>ϡ<EFBFBD>
        ApplySnapToClusters(polygons, clusters, snapRadius, maxExtension);

        // 3. <20><><EFBFBD><EFBFBD><EFBFBD>׶<EFBFBD> (Cleanup Phase)
        // ȷ<><C8B7><EFBFBD>պ϶<D5BA><CFB6><EFBFBD><EFBFBD>α<EFBFBD><CEB1>ֱպϣ<D5BA><CFA3><EFBFBD>β<EFBFBD><CEB2>һ<EFBFBD>£<EFBFBD><C2A3><EFBFBD>
        EnsureClosure(polygons);
    }

private:
    /**
     * \struct VertexReference
     * \brief ָ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>б<EFBFBD><EFBFBD><EFBFBD><EFBFBD>ض<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ľ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
     */
    struct VertexReference
    {
        int polygonIndex;
        int vertexIndex;
    };

    /**
     * \brief <EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>б<EFBFBD><EFBFBD><EFBFBD>
     * \details <EFBFBD><EFBFBD><EFBFBD><EFBFBD>ָ<EFBFBD><EFBFBD><EFBFBD>Բ<EFBFBD>ͬ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ε<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ͬ<EFBFBD><EFBFBD><EFBFBD>򼫽<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>һ<EFBFBD>鶥<EFBFBD>㡣
     */
    static std::vector<std::vector<VertexReference>> BuildClusters(const std::vector<CCurveEx*>& polygons)
    {
        std::vector<std::vector<VertexReference>> clusters;
        std::vector<std::vector<bool>> visited(polygons.size());

        for (size_t i = 0; i < polygons.size(); ++i)
        {
            visited[i].resize(polygons[i]->num, false);
        }

        double weldToleranceSq = 1e-4 * 1e-4; // <20>ж<EFBFBD><D0B6><EFBFBD><EFBFBD>㡰<EFBFBD>غϡ<D8BA><CFA1><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ƽ<EFBFBD><C6BD>

        for (size_t i = 0; i < polygons.size(); ++i)
        {
            for (int k = 0; k < polygons[i]->num; ++k)
            {
                if (visited[i][k])
                {
                    continue;
                }

                std::vector<VertexReference> cluster;
                Vec2 vertex1 = { polygons[i]->x[k], polygons[i]->y[k] };

                // <20><><EFBFBD>Լ<EFBFBD><D4BC><EFBFBD><EFBFBD><EFBFBD><EFBFBD>´<EFBFBD>
                cluster.push_back({ (int)i, k });
                visited[i][k] = true;

                // <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ѱ<EFBFBD>ҡ<EFBFBD><D2A1>ֵܡ<D6B5>
                for (size_t j = 0; j < polygons.size(); ++j)
                {
                    for (int m = 0; m < polygons[j]->num; ++m)
                    {
                        if (i == j && k == m) continue;
                        if (visited[j][m]) continue;

                        Vec2 vertex2 = { polygons[j]->x[m], polygons[j]->y[m] };
                        if ((vertex1 - vertex2).lengthSq() < weldToleranceSq)
                        {
                            cluster.push_back({ (int)j, m });
                            visited[j][m] = true;
                        }
                    }
                }
                clusters.push_back(cluster);
            }
        }
        return clusters;
    }

    /**
     * \brief Ϊÿ<EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ѱ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ߣ<EFBFBD><EFBFBD><EFBFBD><EFBFBD>ƶ<EFBFBD><EFBFBD><EFBFBD><EFBFBD>е<EFBFBD><EFBFBD><EFBFBD><EFBFBD>ж<EFBFBD><EFBFBD>㡣
     */
    static void ApplySnapToClusters(std::vector<CCurveEx*>& polygons,
        const std::vector<std::vector<VertexReference>>& clusters,
        double snapRadius,
        double maxExtension)
    {
        double snapRadiusSq = snapRadius * snapRadius;

        for (const auto& cluster : clusters)
        {
            // ʹ<>ô<EFBFBD><C3B4>еĵ<D0B5>һ<EFBFBD><D2BB><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ϊ<EFBFBD><CEAA><EFBFBD><EFBFBD>λ<EFBFBD><CEBB>
            const auto& representative = cluster[0];
            Vec2 point = { polygons[representative.polygonIndex]->x[representative.vertexIndex],
                           polygons[representative.polygonIndex]->y[representative.vertexIndex] };

            Vec2 bestPosition = point;
            double minDistanceSquared = snapRadiusSq;
            bool found = false;

            // <20><><EFBFBD><EFBFBD>Ѱ<EFBFBD><D1B0><EFBFBD><EFBFBD><EFBFBD><EFBFBD>DZ<EFBFBD>ڵ<EFBFBD>Ŀ<EFBFBD><C4BF><EFBFBD><EFBFBD>
            for (size_t j = 0; j < polygons.size(); ++j)
            {
                CCurveEx* targetPolygon = polygons[j];
                if (targetPolygon->num < 2)
                {
                    continue;
                }

                // <20><><EFBFBD>ˣ<EFBFBD><CBA3><EFBFBD>Ҫ<EFBFBD><D2AA><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ڸô<DAB8>һ<EFBFBD><D2BB><EFBFBD>ֵĶ<D6B5><C4B6><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ϡ<EFBFBD>
                // <20><><EFBFBD><EFBFBD>ֹ<EFBFBD><D6B9><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ͼ<EFBFBD><CDBC><EFBFBD><EFBFBD><EFBFBD>ݡ<EFBFBD>
                bool isSelf = false;
                for (const auto& member : cluster)
                {
                    if (member.polygonIndex == (int)j)
                    {
                        isSelf = true;
                        break;
                    }
                }

                if (isSelf)
                {
                    continue;
                }

                for (int m = 0; m < targetPolygon->num - 1; ++m)
                {
                    Vec2 linePointA = { targetPolygon->x[m], targetPolygon->y[m] };
                    Vec2 linePointB = { targetPolygon->x[m + 1], targetPolygon->y[m + 1] };

                    Vec2 segmentVector = linePointB - linePointA;
                    Vec2 pointToStartVector = point - linePointA;
                    double lengthSquared = segmentVector.lengthSq();

                    if (lengthSquared < 1e-9)
                    {
                        continue;
                    }

                    // <20><><EFBFBD><EFBFBD>ͶӰϵ<D3B0><CFB5> t
                    double t = pointToStartVector.dot(segmentVector) / lengthSquared;

                    // <20><>׳<EFBFBD>߼<EFBFBD><DFBC><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ֱ<EFBFBD><D6B1><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ϣ<EFBFBD>maxExtension <20><>Χ<EFBFBD>ڣ<EFBFBD><DAA3><EFBFBD>
                    // <20><><EFBFBD>޸<EFBFBD><DEB8>˵<EFBFBD><CBB5><EFBFBD>΢<EFBFBD><CEA2><EFBFBD><EFBFBD><EFBFBD>߶ζ˵<CEB6><CBB5>ķ<EFBFBD>϶<EFBFBD><CFB6><EFBFBD>⡣
                    double segmentLength = std::sqrt(lengthSquared);
                    double distanceAlongLine = t * segmentLength;

                    if (distanceAlongLine < -maxExtension || distanceAlongLine > segmentLength + maxExtension)
                    {
                        continue;
                    }

                    // <20><><EFBFBD><EFBFBD>ͶӰ<CDB6><D3B0><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
                    Vec2 projectionPoint = linePointA + segmentVector * t;
                    double currentDistanceSquared = (point - projectionPoint).lengthSq();

                    if (currentDistanceSquared < minDistanceSquared)
                    {
                        minDistanceSquared = currentDistanceSquared;
                        bestPosition = projectionPoint;
                        found = true;
                    }
                }
            }

            // ͬʱ<CDAC><CAB1><EFBFBD>ƶ<EFBFBD>Ӧ<EFBFBD>õ<EFBFBD><C3B5><EFBFBD><EFBFBD>е<EFBFBD><D0B5><EFBFBD><EFBFBD>г<EFBFBD>Ա
            if (found)
            {
                for (const auto& member : cluster)
                {
                    polygons[member.polygonIndex]->x[member.vertexIndex] = bestPosition.x;
                    polygons[member.polygonIndex]->y[member.vertexIndex] = bestPosition.y;
                }
            }
        }
    }

    /**
     * \brief ȷ<EFBFBD><EFBFBD><EFBFBD>պ϶<EFBFBD><EFBFBD><EFBFBD><EFBFBD>α<EFBFBD><EFBFBD>ֱպ<EFBFBD>״̬<EFBFBD><EFBFBD>
     */
    static void EnsureClosure(std::vector<CCurveEx*>& polygons)
    {
        for (auto* polygon : polygons)
        {
            if (polygon->num > 2)
            {
                polygon->x[polygon->num - 1] = polygon->x[0];
                polygon->y[polygon->num - 1] = polygon->y[0];
            }
        }
    }
};

/**
 * \class PolygonSnapper
 * \brief <EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ϵͳ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ģʽ<EFBFBD><EFBFBD> (Facade)<EFBFBD><EFBFBD>
 * \details Э<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>׶ε<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>̣<EFBFBD>
 * 1. <EFBFBD><EFBFBD><EFBFBD><EFBFBD>ƽ<EFBFBD><EFBFBD> (Rigid Translation)<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>룬<EFBFBD><EFBFBD><EFBFBD>ı<EFBFBD><EFBFBD><EFBFBD>״<EFBFBD><EFBFBD>
 * 2. <EFBFBD><EFBFBD><EFBFBD>ಹ<EFBFBD><EFBFBD> (Cluster Gap Filling)<EFBFBD><EFBFBD><EFBFBD>ֲ<EFBFBD>΢<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ԱպϷ<EFBFBD>϶<EFBFBD><EFBFBD>
 */
class PolygonSnapper
{
public:
    /**
     * \brief ִ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ڡ<EFBFBD>
     * \param polygons <EFBFBD><EFBFBD>Ҫ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ķ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>б<EFBFBD><EFBFBD><EFBFBD>
     * \param rigidThreshold <EFBFBD>׶<EFBFBD> 1 <EFBFBD><EFBFBD><EFBFBD><EFBFBD>ֵ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ƽ<EFBFBD>ƣ<EFBFBD><EFBFBD><EFBFBD>
     * \param angleThresholdDeg <EFBFBD>׶<EFBFBD> 1 <EFBFBD>ĽǶ<EFBFBD><EFBFBD>ݲ<EFBFBD>ȣ<EFBFBD><EFBFBD><EFBFBD>
     * \param snapRadius <EFBFBD>׶<EFBFBD> 2 <EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>뾶<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>죩<EFBFBD><EFBFBD>
     * \param maxExtension <EFBFBD>׶<EFBFBD> 2 <EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ֱ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>󳤶ȣ<EFBFBD>Ĭ<EFBFBD><EFBFBD> 100.0<EFBFBD><EFBFBD><EFBFBD><EFBFBD>
     */
    static void Snap(std::vector<CCurveEx*>& polygons,
        double rigidThreshold,
        double angleThresholdDeg,
        double snapRadius,
        double maxExtension = 100.0)
    {
        // 1. <20><><EFBFBD><EFBFBD>ƽ<EFBFBD>ƽ׶<C6BD>
        // <20>ƶ<EFBFBD><C6B6><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ŀ<EFBFBD><C4BF><EFBFBD><EFBFBD><EFBFBD>룬<EFBFBD><EBA3AC><EFBFBD><EFBFBD>ԭʼ<D4AD><CABC>״<EFBFBD><D7B4>
        RigidSnapper::Apply(polygons, rigidThreshold, angleThresholdDeg);

        // 2. <20><><EFBFBD><EFBFBD><EFBFBD>׶<EFBFBD>
        // ΢<><CEA2><EFBFBD><EFBFBD><EFBFBD>㣨<EFBFBD><E3A3A8><EFBFBD>ط<EFBFBD><D8B7>飩<EFBFBD>Ապ<D4B1>΢С<CEA2><D0A1>϶<EFBFBD><CFB6>
        ClusterGapFiller::Apply(polygons, snapRadius, maxExtension);
    }
};

#pragma pop_macro("min")
#pragma pop_macro("max")