<commit_before>/** Copyright (C) 2016 Ultimaker - Released under terms of the AGPLv3 License */
#include <cmath> // isfinite
#include <sstream> // ostream

#include "PolygonProximityLinker.h"
#include "linearAlg2D.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)
 , proximity_distance_2(proximity_distance * proximity_distance)
 , line_grid(proximity_distance, polygons.pointCount(), 3.0f)
{
    // heuristic reserve a good amount of elements
    proximity_point_links.reserve(polygons.pointCount()); // When the whole model consists of thin walls, there will generally be a link for every point, plus some endings minus some points which map to eachother

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

    // link each corner to itself
    addSharpCorners();

    // map each vertex onto nearby line segments
    findProximatePoints();

    // add links where line segments diverge from below the proximity distance to over the proximity distance
    addProximityEndings();

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

bool PolygonProximityLinker::isLinked(Point from)
{
    return point_to_link.find(from) != point_to_link.end();
}


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);
#ifdef DEBUG
    for (Point2Link::iterator it = from_link_pair.first; it != from_link_pair.second; ++it)
    {
        if (!(it->second.a.p() == from || it->second.b.p() == from))
        {
            std::cerr << " ERROR!\n" << it->first << " == " << from << "\n";
            std::cerr << "should be either " << it->second.a.p() << " or " << it->second.b.p() << "\n";
            std::cerr << (from_link_pair.first == from_link_pair.second) << " ; " << (from_link_pair.first == point_to_link.end()) << " ; " << (from_link_pair.second == point_to_link.end()) << "\n";
            std::cerr << std::hash<Point>()(from) << " hashes " << std::hash<Point>()(it->second.a.p()) << " or " << std::hash<Point>()(it->second.b.p()) << "\n";
//             std::cerr << "ERROR! some point got mapped to a link which doesn't have the point as one of the end points!\n";
            
            std::cerr << "\n all links:\n";
            for (std::pair<const Point, const ProximityPointLink> pair : point_to_link)
            {
                std::cerr << pair.first << " : " << pair.second.a.p() << "-" <<pair.second.b.p() << "\n";
            }
            
            std::cerr << "\n link set \n";
            for (const ProximityPointLink link : proximity_point_links)
            {
                std::cerr << link.a.p() << "-" << link.b.p() << " hashes as " << std::hash<ProximityPointLink>()(link) << "\n";
            }
            assert(false && "some point got mapped to a link which doesn't have the point as one of the end points!");
        }
    }
#endif
    return from_link_pair;
}

void PolygonProximityLinker::createLineGrid()
{
    for (unsigned int poly_idx = 0; poly_idx < list_polygons.size(); poly_idx++)
    {
        ListPolygon& poly = list_polygons[poly_idx];
        for (ListPolygon::iterator it = poly.begin(); it != poly.end(); ++it)
        {
            ListPolyIt point_it(poly, it);
            line_grid.insert(point_it);
        }
    }
}

void PolygonProximityLinker::findProximatePoints()
{
    createLineGrid();

    for (unsigned int poly_idx = 0; poly_idx < list_polygons.size(); poly_idx++)
    {
        ListPolygon& poly = list_polygons[poly_idx];
        for (ListPolygon::iterator it = poly.begin(); it != poly.end(); ++it)
        {
            ListPolyIt point_it(poly, it);
            if (new_points.find(point_it) == new_points.end())
            {
                // handle new_points separately
                // to prevent this:
                //  1    3   5   7
                //  o<-.
                //  :   'o<-.
                //  :   /:   o<.
                //  :  / :  /:  'o<.
                //  : /  : / : / :
                //  :/   :/  :/  :   etc.
                //  o--->o-->o-->o->
                //  2    4   6   8
                std::unordered_set<ListPolyIt> nearby_lines;
                auto process_func = [&nearby_lines](const ListPolyIt& elem)
                {
                    nearby_lines.emplace(elem);
                };
                line_grid.processNearby(point_it.p(), proximity_distance, process_func);
                for (const ListPolyIt& nearby_line : nearby_lines)
                {
                    findProximatePoints(point_it, *nearby_line.poly, nearby_line, nearby_line.next());
                }
            }
        }
    }

    for (const ListPolyIt& new_point_it : new_points)
    {
        // link with existing points, but don't introduce new points for line segments
        // to prevent this:
        //  1    3   5   7
        //  o<-.
        //  :   'o<-.
        //  :   /:   o<.
        //  :  / :  /:  'o<.
        //  : /  : / : / :
        //  :/   :/  :/  :   etc.
        //  o--->o-->o-->o->
        //  2    4   6   8
        std::unordered_set<ListPolyIt> nearby_vert_its;
        auto process_func = [&nearby_vert_its](const ListPolyIt& elem)
        {
            nearby_vert_its.emplace(elem);
        };
        line_grid.processNearby(new_point_it.p(), proximity_distance, process_func);
        // because we use the same line_grid as before the resulting nearby_points
        // will also have points which are not nearby, (But when the line segment *is* nearby.)
        // but at least we don't have to create a whole new SparsePointGrid
        for (const ListPolyIt& nearby_vert_it : nearby_vert_its)
        {
            Point new_point = new_point_it.p();
            Point nearby_vert = nearby_vert_it.p();
            int64_t dist2 = vSize2(new_point - nearby_vert);
            if (dist2 < proximity_distance_2
                && new_point != nearby_vert // not the same point
                && new_point_it.next() != nearby_vert_it && new_point_it.prev() != nearby_vert_it // not directly connected
            )
            {
                addProximityLink(new_point_it, nearby_vert_it, sqrt(dist2), ProximityPointLinkType::NORMAL);
            }
        }
    }
}

void PolygonProximityLinker::findProximatePoints(const ListPolyIt a_from_it, ListPolygon& to_list_poly, const ListPolyIt b_from_it, const ListPolyIt b_to_it)
{
    const Point& a_from = a_from_it.p();

    const Point& b_from = b_from_it.p();
    const Point& b_to = b_to_it.p();

    if (a_from_it == b_from_it || a_from_it == b_to_it) // we currently consider a linesegment directly connected to [from]
    {
        return;
    }
    if (a_from_it.prev() == b_to_it) // [a] is connected to a line segment directly connected to the line segment [b]
    {
        // only check whether we need to link points; don't project
        int64_t dist2 = vSize2(b_from - a_from);
        if (dist2 < proximity_distance_2)
        {
            int64_t dist = sqrt(dist2);
            addProximityLink(a_from_it, b_from_it, dist, ProximityPointLinkType::NORMAL);
        }
        return;
    }
    if (a_from_it.next() == b_from_it) // [a] is connected to a line segment directly connected to the line segment [b]
    {
        // only check whether we need to link points; don't project
        int64_t dist2 = vSize2(b_to - a_from);
        if (dist2 < proximity_distance_2)
        {
            int64_t dist = sqrt(dist2);
            addProximityLink(a_from_it, b_to_it, dist, ProximityPointLinkType::NORMAL);
        }
        return;
    }



    Point closest = LinearAlg2D::getClosestOnLineSegment(a_from, b_from, b_to);

    int64_t dist2 = vSize2(closest - a_from);

    if (dist2 > proximity_distance_2
        || (a_from_it.poly == &to_list_poly
            && dot(a_from_it.next().p() - a_from, b_to - b_from) > 0 
            && dot(a_from - a_from_it.prev().p(), b_to - b_from) > 0  ) // line segments are likely connected, because the winding order is in the same general direction
    )
    { // line segment too far away to be proximate
        return;
    }

    int64_t dist = sqrt(dist2);
<commit_msg>lil doc fix (CURA-1911)<commit_after>/** Copyright (C) 2016 Ultimaker - Released under terms of the AGPLv3 License */
#include <cmath> // isfinite
#include <sstream> // ostream

#include "PolygonProximityLinker.h"
#include "linearAlg2D.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)
 , proximity_distance_2(proximity_distance * proximity_distance)
 , line_grid(proximity_distance, polygons.pointCount(), 3.0f)
{
    // heuristic reserve a good amount of elements
    proximity_point_links.reserve(polygons.pointCount()); // When the whole model consists of thin walls, there will generally be a link for every point, plus some endings minus some points which map to eachother

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

    // link each corner to itself
    addSharpCorners();

    // map each vertex onto nearby line segments
    findProximatePoints();

    // add links where line segments diverge from below the proximity distance to over the proximity distance
    addProximityEndings();

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

bool PolygonProximityLinker::isLinked(Point from)
{
    return point_to_link.find(from) != point_to_link.end();
}


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);
#ifdef DEBUG
    for (Point2Link::iterator it = from_link_pair.first; it != from_link_pair.second; ++it)
    {
        if (!(it->second.a.p() == from || it->second.b.p() == from))
        {
            std::cerr << " ERROR!\n" << it->first << " == " << from << "\n";
            std::cerr << "should be either " << it->second.a.p() << " or " << it->second.b.p() << "\n";
            std::cerr << (from_link_pair.first == from_link_pair.second) << " ; " << (from_link_pair.first == point_to_link.end()) << " ; " << (from_link_pair.second == point_to_link.end()) << "\n";
            std::cerr << std::hash<Point>()(from) << " hashes " << std::hash<Point>()(it->second.a.p()) << " or " << std::hash<Point>()(it->second.b.p()) << "\n";
//             std::cerr << "ERROR! some point got mapped to a link which doesn't have the point as one of the end points!\n";
            
            std::cerr << "\n all links:\n";
            for (std::pair<const Point, const ProximityPointLink> pair : point_to_link)
            {
                std::cerr << pair.first << " : " << pair.second.a.p() << "-" <<pair.second.b.p() << "\n";
            }
            
            std::cerr << "\n link set \n";
            for (const ProximityPointLink link : proximity_point_links)
            {
                std::cerr << link.a.p() << "-" << link.b.p() << " hashes as " << std::hash<ProximityPointLink>()(link) << "\n";
            }
            assert(false && "some point got mapped to a link which doesn't have the point as one of the end points!");
        }
    }
#endif
    return from_link_pair;
}

void PolygonProximityLinker::createLineGrid()
{
    for (unsigned int poly_idx = 0; poly_idx < list_polygons.size(); poly_idx++)
    {
        ListPolygon& poly = list_polygons[poly_idx];
        for (ListPolygon::iterator it = poly.begin(); it != poly.end(); ++it)
        {
            ListPolyIt point_it(poly, it);
            line_grid.insert(point_it);
        }
    }
}

void PolygonProximityLinker::findProximatePoints()
{
    createLineGrid();

    for (unsigned int poly_idx = 0; poly_idx < list_polygons.size(); poly_idx++)
    {
        ListPolygon& poly = list_polygons[poly_idx];
        for (ListPolygon::iterator it = poly.begin(); it != poly.end(); ++it)
        {
            ListPolyIt point_it(poly, it);
            if (new_points.find(point_it) == new_points.end())
            {
                // handle new_points separately
                // to prevent this:
                //  1    3   5   7
                //  o<-.
                //  :   'o<-.
                //  :   /:   o<.
                //  :  / :  /:  'o<.
                //  : /  : / : / :
                //  :/   :/  :/  :   etc.
                //  o--->o-->o-->o->
                //  2    4   6   8
                std::unordered_set<ListPolyIt> nearby_lines;
                auto process_func = [&nearby_lines](const ListPolyIt& elem)
                {
                    nearby_lines.emplace(elem);
                };
                line_grid.processNearby(point_it.p(), proximity_distance, process_func);
                for (const ListPolyIt& nearby_line : nearby_lines)
                {
                    findProximatePoints(point_it, *nearby_line.poly, nearby_line, nearby_line.next());
                }
            }
        }
    }

    for (const ListPolyIt& new_point_it : new_points)
    {
        // link with existing points, but don't introduce new points for line segments
        // to prevent this:
        //  1    3   5   7
        //  o<-.
        //  :   'o<-.
        //  :   /:   o<.
        //  :  / :  /:  'o<.
        //  : /  : / : / :
        //  :/   :/  :/  :   etc.
        //  o--->o-->o-->o->
        //  2    4   6   8
        std::unordered_set<ListPolyIt> nearby_vert_its;
        auto process_func = [&nearby_vert_its](const ListPolyIt& elem)
        {
            nearby_vert_its.emplace(elem);
        };
        line_grid.processNearby(new_point_it.p(), proximity_distance, process_func);
        // because we use the same line_grid as before the resulting nearby_points
        // will also have points which are not nearby, (But when the line segment *is* nearby.)
        // but at least we don't have to create a whole new SparsePointGrid
        for (const ListPolyIt& nearby_vert_it : nearby_vert_its)
        {
            Point new_point = new_point_it.p();
            Point nearby_vert = nearby_vert_it.p();
            int64_t dist2 = vSize2(new_point - nearby_vert);
            if (dist2 < proximity_distance_2
                && new_point != nearby_vert // not the same point
                && new_point_it.next() != nearby_vert_it && new_point_it.prev() != nearby_vert_it // not directly connected
            )
            {
                addProximityLink(new_point_it, nearby_vert_it, sqrt(dist2), ProximityPointLinkType::NORMAL);
            }
        }
    }
}

void PolygonProximityLinker::findProximatePoints(const ListPolyIt a_from_it, ListPolygon& to_list_poly, const ListPolyIt b_from_it, const ListPolyIt b_to_it)
{
    const Point& a_from = a_from_it.p();

    const Point& b_from = b_from_it.p();
    const Point& b_to = b_to_it.p();

    if (a_from_it == b_from_it || a_from_it == b_to_it) // we currently consider a linesegment directly connected to [from]
    {
        return;
    }
    if (a_from_it.prev() == b_to_it) // [a] is connected to a line segment directly connected to [b]
    {
        // only check whether we need to link points; don't project
        int64_t dist2 = vSize2(b_from - a_from);
        if (dist2 < proximity_distance_2)
        {
            int64_t dist = sqrt(dist2);
            addProximityLink(a_from_it, b_from_it, dist, ProximityPointLinkType::NORMAL);
        }
        return;
    }
    if (a_from_it.next() == b_from_it) // [a] is connected to a line segment directly connected to [b]
    {
        // only check whether we need to link points; don't project
        int64_t dist2 = vSize2(b_to - a_from);
        if (dist2 < proximity_distance_2)
        {
            int64_t dist = sqrt(dist2);
            addProximityLink(a_from_it, b_to_it, dist, ProximityPointLinkType::NORMAL);
        }
        return;
    }



    Point closest = LinearAlg2D::getClosestOnLineSegment(a_from, b_from, b_to);

    int64_t dist2 = vSize2(closest - a_from);

    if (dist2 > proximity_distance_2
        || (a_from_it.poly == &to_list_poly
            && dot(a_from_it.next().p() - a_from, b_to - b_from) > 0 
            && dot(a_from - a_from_it.prev().p(), b_to - b_from) > 0  ) // line segments are likely connected, because the winding order is in the same general direction
    )
    { // line segment too far away to be proximate
        return;
    }

    int64_t dist = sqrt(dist2);

{'fraction_non_alphanumeric': 0.12805445659762624, 'fraction_numerical': 0.008377938096346288, 'mean_word_length': 2.1719874515593283, 'pattern_counts': {'":': 0, '<': 199, '<?xml version=': 0, '>': 61, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1440621', 'n_tokens_mistral': 5679, 'n_tokens_neox': 5454, 'n_words': 1279}