<commit_before>/** Copyright (C) 2013 <NAME> - Released under terms of the AGPLv3 License */
#include "pathOrderOptimizer.h"
#include "utils/logoutput.h"
#include "utils/SparsePointGridInclusive.h"
#include "utils/linearAlg2D.h"

#define INLINE static inline

namespace cura {

/**
*
*/
void PathOrderOptimizer::optimize()
{
    const EZSeamType type = (config)? config->type : EZSeamType::SHORTEST;
    bool picked[polygons.size()];
    memset(picked, false, sizeof(bool) * polygons.size());/// initialized as falses
    
    for (unsigned poly_idx = 0; poly_idx < polygons.size(); ++poly_idx) /// find closest point to initial starting point within each polygon +initialize picked
    {
        const ConstPolygonRef poly = *polygons[poly_idx];
        switch (type)
        {
            case EZSeamType::USER_SPECIFIED:
            case EZSeamType::SHARPEST_CORNER:
                polyStart.push_back(getClosestPointInPolygon(config->pos, poly_idx));
                break;
            case EZSeamType::RANDOM:
                polyStart.push_back(getRandomPointInPolygon(poly_idx));
                break;
            default:
            {
                int best_points_idx = -1;
                float bestDist = std::numeric_limits<float>::infinity();
                for (unsigned int point_idx = 0; point_idx < poly.size(); point_idx++) /// get closest point in polygon
                {
                    float dist = vSize2f(poly[point_idx] - startPoint);
                    if (dist < bestDist)
                    {
                        best_points_idx = point_idx;
                        bestDist = dist;
                    }
                }
                polyStart.push_back(best_points_idx);
                break;
            }
        }
        //picked.push_back(false); /// initialize all picked values as false
        assert(poly.size() != 2);
    }


    Point prev_point = startPoint;
    for (unsigned int poly_order_idx = 0; poly_order_idx < polygons.size(); poly_order_idx++) /// actual path order optimizer
    {
        int best_poly_idx = -1;
        float bestDist = std::numeric_limits<float>::infinity();


        for (unsigned int poly_idx = 0; poly_idx < polygons.size(); poly_idx++)
        {
            if (picked[poly_idx] || polygons[poly_idx]->size() < 1) /// skip single-point-polygons
            {
                continue;
            }

            assert (polygons[poly_idx]->size() != 2);

            float dist = vSize2f((*polygons[poly_idx])[polyStart[poly_idx]] - prev_point);
            if (dist < bestDist)
            {
                best_poly_idx = poly_idx;
                bestDist = dist;
            }

        }


        if (best_poly_idx > -1) /// should always be true; we should have been able to identify the best next polygon
        {
            assert(polygons[best_poly_idx]->size() != 2);

            prev_point = (*polygons[best_poly_idx])[polyStart[best_poly_idx]];

            picked[best_poly_idx] = true;
            polyOrder.push_back(best_poly_idx);
        }
        else
        {
            logError("Failed to find next closest polygon.\n");
        }
    }

    if (type == EZSeamType::SHORTEST)
    {
        prev_point = startPoint;
        for (unsigned int order_idx = 0; order_idx < polyOrder.size(); order_idx++) /// decide final starting points in each polygon
        {
            int poly_idx = polyOrder[order_idx];
            int point_idx = getClosestPointInPolygon(prev_point, poly_idx);
            polyStart[poly_idx] = point_idx;
            prev_point = (*polygons[poly_idx])[point_idx];
        }
    }
}

int PathOrderOptimizer::getClosestPointInPolygon(Point prev_point, int poly_idx)
{
    const EZSeamType type = (config)? config->type : EZSeamType::SHORTEST;
    ConstPolygonRef poly = *polygons[poly_idx];

    int best_point_idx = -1;
    float best_point_score = std::numeric_limits<float>::infinity();
    Point p0 = poly.back();
    for (unsigned int point_idx = 0; point_idx < poly.size(); point_idx++)
    {
        const Point& p1 = poly[point_idx];
        const Point& p2 = poly[(point_idx + 1) % poly.size()];
        // when type is SHARPEST_CORNER, actual distance is ignored, we use a fixed distance and decision is based on curvature only
        int64_t dist = (type == EZSeamType::SHARPEST_CORNER)? 100 : vSize2(p1 - prev_point);
        const float corner_angle = LinearAlg2D::getAngleLeft(p0, p1, p2) / M_PI; // 0 -> 2
        if (type == EZSeamType::USER_SPECIFIED || type == EZSeamType::SHARPEST_CORNER)
        {
            const EZSeamCornerPrefType corner_pref = (config)? config->corner_pref : EZSeamCornerPrefType::Z_SEAM_CORNER_PREF_NONE;
            const float scaling_divisor = 50;
            switch (corner_pref)
            {
                case EZSeamCornerPrefType::Z_SEAM_CORNER_PREF_INNER:
                    if (corner_angle > 1)
                    {
                        // p1 lies on a concave curve so reduce the distance to favour it
                        // the more concave the curve, the more we reduce the distance
                        dist -= (corner_angle - 1) * dist / scaling_divisor;
                    }
                    break;
                case EZSeamCornerPrefType::Z_SEAM_CORNER_PREF_OUTER:
                    if (corner_angle < 1)
                    {
                        // p1 lies on a convex curve so reduce the distance to favour it
                        // the more convex the curve, the more we reduce the distance
                        dist -= (1 - corner_angle) * dist / scaling_divisor;
                    }
                    break;
                case EZSeamCornerPrefType::Z_SEAM_CORNER_PREF_ANY:
                    // the more curved the region, the more we reduce the distance
                    dist -= fabs(corner_angle - 1) * dist / scaling_divisor;<commit_msg>Now getClosestPointInPolygon() will apply corner preference when seam type is closest.<commit_after>/** Copyright (C) 2013 <NAME> - Released under terms of the AGPLv3 License */
#include "pathOrderOptimizer.h"
#include "utils/logoutput.h"
#include "utils/SparsePointGridInclusive.h"
#include "utils/linearAlg2D.h"

#define INLINE static inline

namespace cura {

/**
*
*/
void PathOrderOptimizer::optimize()
{
    const EZSeamType type = (config)? config->type : EZSeamType::SHORTEST;
    bool picked[polygons.size()];
    memset(picked, false, sizeof(bool) * polygons.size());/// initialized as falses
    
    for (unsigned poly_idx = 0; poly_idx < polygons.size(); ++poly_idx) /// find closest point to initial starting point within each polygon +initialize picked
    {
        const ConstPolygonRef poly = *polygons[poly_idx];
        switch (type)
        {
            case EZSeamType::USER_SPECIFIED:
                polyStart.push_back(getClosestPointInPolygon(config->pos, poly_idx));
                break;
            case EZSeamType::RANDOM:
                polyStart.push_back(getRandomPointInPolygon(poly_idx));
                break;
            case EZSeamType::SHARPEST_CORNER:
            case EZSeamType::SHORTEST:
            default:
                polyStart.push_back(getClosestPointInPolygon(startPoint, poly_idx));
                break;
        }
        assert(poly.size() != 2);
    }


    Point prev_point = startPoint;
    for (unsigned int poly_order_idx = 0; poly_order_idx < polygons.size(); poly_order_idx++) /// actual path order optimizer
    {
        int best_poly_idx = -1;
        float bestDist = std::numeric_limits<float>::infinity();


        for (unsigned int poly_idx = 0; poly_idx < polygons.size(); poly_idx++)
        {
            if (picked[poly_idx] || polygons[poly_idx]->size() < 1) /// skip single-point-polygons
            {
                continue;
            }

            assert (polygons[poly_idx]->size() != 2);

            float dist = vSize2f((*polygons[poly_idx])[polyStart[poly_idx]] - prev_point);
            if (dist < bestDist)
            {
                best_poly_idx = poly_idx;
                bestDist = dist;
            }

        }


        if (best_poly_idx > -1) /// should always be true; we should have been able to identify the best next polygon
        {
            assert(polygons[best_poly_idx]->size() != 2);

            prev_point = (*polygons[best_poly_idx])[polyStart[best_poly_idx]];

            picked[best_poly_idx] = true;
            polyOrder.push_back(best_poly_idx);
        }
        else
        {
            logError("Failed to find next closest polygon.\n");
        }
    }
}

int PathOrderOptimizer::getClosestPointInPolygon(Point prev_point, int poly_idx)
{
    const EZSeamType type = (config)? config->type : EZSeamType::SHORTEST;
    ConstPolygonRef poly = *polygons[poly_idx];

    int best_point_idx = -1;
    float best_point_score = std::numeric_limits<float>::infinity();
    Point p0 = poly.back();
    for (unsigned int point_idx = 0; point_idx < poly.size(); point_idx++)
    {
        const Point& p1 = poly[point_idx];
        const Point& p2 = poly[(point_idx + 1) % poly.size()];
        // when type is SHARPEST_CORNER, actual distance is ignored, we use a fixed distance and decision is based on curvature only
        int64_t dist = (type == EZSeamType::SHARPEST_CORNER)? 100 : vSize2(p1 - prev_point);
        const float corner_angle = LinearAlg2D::getAngleLeft(p0, p1, p2) / M_PI; // 0 -> 2
        const EZSeamCornerPrefType corner_pref = (config)? config->corner_pref : EZSeamCornerPrefType::Z_SEAM_CORNER_PREF_NONE;
        if (type == EZSeamType::SHORTEST)
        {
            // the more a corner satisfies our criteria the closer it appears to be
            const int64_t corner_shift = 10000 * 10000; // shift 10mm for a very acute corner
            switch (corner_pref)
            {
                case EZSeamCornerPrefType::Z_SEAM_CORNER_PREF_INNER:
                    if (corner_angle > 1)
                    {
                        // p1 lies on a concave curve so reduce the distance to favour it
                        // the more concave the curve, the more we reduce the distance
                        dist -= (corner_angle - 1) * corner_shift;
                    }
                    break;
                case EZSeamCornerPrefType::Z_SEAM_CORNER_PREF_OUTER:
                    if (corner_angle < 1)
                    {
                        // p1 lies on a convex curve so reduce the distance to favour it
                        // the more convex the curve, the more we reduce the distance
                        dist -= (1 - corner_angle) * corner_shift;
                    }
                    break;
                case EZSeamCornerPrefType::Z_SEAM_CORNER_PREF_ANY:
                    // the more curved the region, the more we reduce the distance
                    dist -= fabs(corner_angle - 1) * corner_shift;
                    break;
                case EZSeamCornerPrefType::Z_SEAM_CORNER_PREF_NONE:
                default:
                    // do nothing
                    break;
            }
        }
        else
        {
            // the value of scaling_divisor controls how much influence corner_angle has on dist
            const float scaling_divisor = 50;
            switch (corner_pref)
            {
                case EZSeamCornerPrefType::Z_SEAM_CORNER_PREF_INNER:
                    if (corner_angle > 1)
                    {
                        // p1 lies on a concave curve so reduce the distance to favour it
                        // the more concave the curve, the more we reduce the distance
                        dist -= (corner_angle - 1) * dist / scaling_divisor;
                    }
                    break;
                case EZSeamCornerPrefType::Z_SEAM_CORNER_PREF_OUTER:
                    if (corner_angle < 1)
                    {
                        // p1 lies on a convex curve so reduce the distance to favour it
                        // the more convex the curve, the more we reduce the distance
                        dist -= (1 - corner_angle) * dist / scaling_divisor;
                    }
                    break;
                case EZSeamCornerPrefType::Z_SEAM_CORNER_PREF_ANY:
                    // the more curved the region, the more we reduce the distance
                    dist -= fabs(corner_angle - 1) * dist / scaling_divisor;
{'fraction_non_alphanumeric': 0.09125322164948453, 'fraction_numerical': 0.009101159793814434, 'mean_word_length': 1.8054676909173069, 'pattern_counts': {'":': 0, '<': 28, '<?xml version=': 0, '>': 31, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3485967', 'n_tokens_mistral': 3762, 'n_tokens_neox': 3492, 'n_words': 906}