<commit_before>#include <cmath> // isfinite
#include <sstream> // ostream

#include "PolygonProximityLinker.h"

#include "AABB.h" // for debug output svg html
#include "SVG.h"

namespace cura 
{

PolygonProximityLinker::PolygonProximityLinker(Polygons& polygons, int proximity_distance)
 : polygons(polygons)
 , proximity_distance(proximity_distance) 
{ 
    unsigned int n_points = 0;
    for (PolygonRef poly : polygons)
    {
        n_points += poly.size();
    }

    // reserve enough elements so that iterators don't get invalidated
    proximity_point_links.reserve(n_points * 2); // generally enough, unless there are a lot of 3-way intersections in the model
    proximity_point_links_endings.reserve(n_points * 2); // any point can at most introduce two endings

    // convert to list polygons for insertion of points
    ListPolyIt::convertPolygonsToLists(polygons, list_polygons); 

    findProximatePoints();
    addProximityEndings();
    // TODO: add sharp corners

    // convert list polygons back
    ListPolyIt::convertListPolygonsToPolygons(list_polygons, polygons);
//     wallOverlaps2HTML("output/output.html");
}

bool PolygonProximityLinker::isLinked(Point from)
{
    return point_to_link.count(from) > 0;
}


std::pair<PolygonProximityLinker::Point2Link::iterator, PolygonProximityLinker::Point2Link::iterator> PolygonProximityLinker::getLinks(Point from)
{
    std::pair<Point2Link::iterator, Point2Link::iterator> from_link_pair = point_to_link.equal_range(from);
    return from_link_pair;
}


void PolygonProximityLinker::findProximatePoints()
{
    // link each vertex of each polygon to each proximate line segment of any polygon
    // in order to avoid checking polygons twice, only compare each polygon to each previous polygon
    // and when comparing one polygon with itseld compare each vertex to each previously processed line segment
    for (unsigned int poly_idx = 0; poly_idx < list_polygons.size(); poly_idx++)
    {
        ListPolygon& poly = list_polygons[poly_idx];
        for (unsigned int poly2_idx = 0; poly2_idx <= poly_idx; poly2_idx++)
        {
            for (ListPolygon::iterator it = poly.begin(); it != poly.end(); ++it)
            {
                ListPolyIt lpi(poly, it);
                if (poly_idx == poly2_idx)
                {
//                     ListPolygon::iterator it2(it);
//                     ++it2;
//                     if (it2 != poly.end())
                    {
                        findProximatePoints(lpi, poly2_idx, it);
                    }
                }
                else 
                {
                    findProximatePoints(lpi, poly2_idx);
                }
            }
        }
    }
}

void PolygonProximityLinker::findProximatePoints(ListPolyIt from, unsigned int to_list_poly_idx)
{
    findProximatePoints(from, to_list_poly_idx, list_polygons[to_list_poly_idx].begin());
}

void PolygonProximityLinker::findProximatePoints(ListPolyIt from_it, unsigned int to_list_poly_idx, const ListPolygon::iterator start)
{
    ListPolygon& to_list_poly = list_polygons[to_list_poly_idx];
    Point& from = from_it.p();
    ListPolygon::iterator last_it = --to_list_poly.end();
    for (ListPolygon::iterator it = start; it != to_list_poly.end(); ++it)
    {
        Point& last_point = *last_it;
        Point& point = *it;

        if (&from_it.poly == &to_list_poly 
            && (
                (from_it.it == last_it || from_it.it == it) // we currently consider a linesegment directly connected to [from]
                || (from_it.prev().it == it || from_it.next().it == last_it) // line segment from [last_point] to [point] is connected to line segment of which [from] is the other end
                ) 
           )
        { 
            last_it = it;
            continue;
        }
        Point closest = LinearAlg2D::getClosestOnLineSegment(from, last_point, point);

        int64_t dist2 = vSize2(closest - from);

        if (dist2 > proximity_distance * proximity_distance
            || (&from_it.poly == &to_list_poly 
                && dot(from_it.next().p() - from, point - last_point) > 0 
                && dot(from - from_it.prev().p(), point - last_point) > 0  ) // line segments are likely connected, because the winding order is in the same general direction
        )
        { // line segment too far away to be proximate
            last_it = it;
            continue;
        }

        int64_t dist = sqrt(dist2);

        if (shorterThen(closest - last_point, 10))
        {
            addProximityLink(from_it, ListPolyIt(to_list_poly, last_it), dist);
        }
        else if (shorterThen(closest - point, 10))
        {
            addProximityLink(from_it, ListPolyIt(to_list_poly, it), dist);
        }
        else 
        {
            ListPolygon::iterator new_it = to_list_poly.insert(it, closest);
            addProximityLink(from_it, ListPolyIt(to_list_poly, new_it), dist);
        }

        last_it = it;
    }
}


bool PolygonProximityLinker::addProximityLink(ListPolyIt from, ListPolyIt to, int64_t dist)
{
    ProximityPointLink link(from, to, dist);
    std::pair<ProximityPointLinks::iterator, bool> result =
        proximity_point_links.emplace(link);

    ProximityPointLinks::iterator it = result.first;
    addToPoint2LinkMap(*it->a.it, it);
    addToPoint2LinkMap(*it->b.it, it);

    return result.second;
}

bool PolygonProximityLinker::addProximityLink_endings(ListPolyIt from, ListPolyIt to, int64_t dist)
{
    ProximityPointLink link(from, to, dist);
    std::pair<ProximityPointLinks::iterator, bool> result =
        proximity_point_links_endings.emplace(link);

//     if (! result.second)
//     {
//         DEBUG_PRINTLN("couldn't emplace in overlap_point_links! : ");
//         result.first->second = attr;
//     }

    ProximityPointLinks::iterator it = result.first;
    addToPoint2LinkMap(*it->a.it, it);
    addToPoint2LinkMap(*it->b.it, it);<commit_msg>lil optimization for wall overlap compensation (CURA-1911)<commit_after>#include <cmath> // isfinite
#include <sstream> // ostream

#include "PolygonProximityLinker.h"

#include "AABB.h" // for debug output svg html
#include "SVG.h"

namespace cura 
{

PolygonProximityLinker::PolygonProximityLinker(Polygons& polygons, int proximity_distance)
 : polygons(polygons)
 , proximity_distance(proximity_distance) 
{ 
    unsigned int n_points = 0;
    for (PolygonRef poly : polygons)
    {
        n_points += poly.size();
    }

    // reserve enough elements so that iterators don't get invalidated
    proximity_point_links.reserve(n_points * 2); // generally enough, unless there are a lot of 3-way intersections in the model
    proximity_point_links_endings.reserve(n_points * 2); // any point can at most introduce two endings

    // convert to list polygons for insertion of points
    ListPolyIt::convertPolygonsToLists(polygons, list_polygons); 

    findProximatePoints();
    addProximityEndings();
    // TODO: add sharp corners

    // convert list polygons back
    ListPolyIt::convertListPolygonsToPolygons(list_polygons, polygons);
//     wallOverlaps2HTML("output/output.html");
}

bool PolygonProximityLinker::isLinked(Point from)
{
    return point_to_link.count(from) > 0;
}


std::pair<PolygonProximityLinker::Point2Link::iterator, PolygonProximityLinker::Point2Link::iterator> PolygonProximityLinker::getLinks(Point from)
{
    std::pair<Point2Link::iterator, Point2Link::iterator> from_link_pair = point_to_link.equal_range(from);
    return from_link_pair;
}


void PolygonProximityLinker::findProximatePoints()
{
    // link each vertex of each polygon to each proximate line segment of any polygon
    // in order to avoid checking polygons twice, only compare each polygon to each previous polygon
    // and when comparing one polygon with itseld compare each vertex to each previously processed line segment
    for (unsigned int poly_idx = 0; poly_idx < list_polygons.size(); poly_idx++)
    {
        ListPolygon& poly = list_polygons[poly_idx];
        for (unsigned int poly2_idx = 0; poly2_idx <= poly_idx; poly2_idx++)
        {
            for (ListPolygon::iterator it = poly.begin(); it != poly.end(); ++it)
            {
                ListPolyIt lpi(poly, it);
                if (poly_idx == poly2_idx)
                {
//                     ListPolygon::iterator it2(it);
//                     ++it2;
//                     if (it2 != poly.end())
                    {
                        findProximatePoints(lpi, poly2_idx, it);
                    }
                }
                else 
                {
                    findProximatePoints(lpi, poly2_idx);
                }
            }
        }
    }
}

void PolygonProximityLinker::findProximatePoints(ListPolyIt from, unsigned int to_list_poly_idx)
{
    findProximatePoints(from, to_list_poly_idx, list_polygons[to_list_poly_idx].begin());
}

void PolygonProximityLinker::findProximatePoints(ListPolyIt from_it, unsigned int to_list_poly_idx, const ListPolygon::iterator start)
{
    ListPolygon& to_list_poly = list_polygons[to_list_poly_idx];
    Point& from = from_it.p();
    ListPolygon::iterator last_it = --to_list_poly.end();
    for (ListPolygon::iterator it = start; it != to_list_poly.end(); ++it)
    {
        Point& last_point = *last_it;
        Point& point = *it;

        if (&from_it.poly == &to_list_poly 
            && (
                (from_it.it == last_it || from_it.it == it) // we currently consider a linesegment directly connected to [from]
                || (from_it.prev().it == it || from_it.next().it == last_it) // line segment from [last_point] to [point] is connected to line segment of which [from] is the other end
                ) 
           )
        { 
            last_it = it;
            continue;
        }
        Point closest = LinearAlg2D::getClosestOnLineSegment(from, last_point, point);

        int64_t dist2 = vSize2(closest - from);

        if (dist2 > proximity_distance * proximity_distance
            || (&from_it.poly == &to_list_poly 
                && dot(from_it.next().p() - from, point - last_point) > 0 
                && dot(from - from_it.prev().p(), point - last_point) > 0  ) // line segments are likely connected, because the winding order is in the same general direction
        )
        { // line segment too far away to be proximate
            last_it = it;
            continue;
        }

        int64_t dist = sqrt(dist2);

        if (shorterThen(closest - last_point, 10))
        {
            addProximityLink(from_it, ListPolyIt(to_list_poly, last_it), dist);
        }
        else if (shorterThen(closest - point, 10))
        {
            addProximityLink(from_it, ListPolyIt(to_list_poly, it), dist);
        }
        else 
        {
            ListPolygon::iterator new_it = to_list_poly.insert(it, closest);
            addProximityLink(from_it, ListPolyIt(to_list_poly, new_it), dist);
        }

        last_it = it;
    }
}


bool PolygonProximityLinker::addProximityLink(ListPolyIt from, ListPolyIt to, int64_t dist)
{
    std::pair<ProximityPointLinks::iterator, bool> result =
        proximity_point_links.emplace(from, to, dist);

    ProximityPointLinks::iterator it = result.first;
    addToPoint2LinkMap(*it->a.it, it);
    addToPoint2LinkMap(*it->b.it, it);

    return result.second;
}

bool PolygonProximityLinker::addProximityLink_endings(ListPolyIt from, ListPolyIt to, int64_t dist)
{
    std::pair<ProximityPointLinks::iterator, bool> result =
        proximity_point_links_endings.emplace(from, to, dist);

//     if (! result.second)
//     {
//         DEBUG_PRINTLN("couldn't emplace in overlap_point_links! : ");
//         result.first->second = attr;
//     }

    ProximityPointLinks::iterator it = result.first;
    addToPoint2LinkMap(*it->a.it, it);
    addToPoint2LinkMap(*it->b.it, it);
{'fraction_non_alphanumeric': 0.10518792567056251, 'fraction_numerical': 0.00773564281510132, 'mean_word_length': 2.6462293071735132, 'pattern_counts': {'":': 0, '<': 19, '<?xml version=': 0, '>': 33, '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': '3852282', 'n_tokens_mistral': 3852, 'n_tokens_neox': 3657, 'n_words': 833}