SuperSlicer/tests/libslic3r/test_geometry.cpp

#include <catch2/catch.hpp>

#include "libslic3r/Point.hpp"
#include "libslic3r/BoundingBox.hpp"
#include "libslic3r/Polygon.hpp"
#include "libslic3r/Polyline.hpp"
#include "libslic3r/Line.hpp"
#include "libslic3r/Geometry.hpp"
#include "libslic3r/Geometry/Circle.hpp"
#include "libslic3r/Geometry/ConvexHull.hpp"
#include "libslic3r/ClipperUtils.hpp"
#include "libslic3r/ShortestPath.hpp"

//#include <random>
//#include "libnest2d/tools/benchmark.h"
#include "libslic3r/SVG.hpp"

#include "../libnest2d/printer_parts.hpp"

#include <unordered_set>

using namespace Slic3r;

ExtrusionPath* createEP(std::initializer_list<Point> vec) {
    ExtrusionPath *ep = new ExtrusionPath{ ExtrusionRole::erNone };
    ep->polyline = vec;
    return ep;
}
ExtrusionEntityCollection* createEC(std::initializer_list<ExtrusionEntity*> vec, bool no_sort = false) {
    ExtrusionEntityCollection *ec = new ExtrusionEntityCollection{};
    ec->set_can_sort_reverse(!no_sort, !no_sort);
    ec->entities = vec;
    return ec;
}
ExtrusionLoop* createEL(std::vector<std::initializer_list<Point>> vec) {
    ExtrusionLoop *el = new ExtrusionLoop{};
    for (std::initializer_list<Point> &path : vec) {
        el->paths.emplace_back(ExtrusionRole::erNone);
        el->paths.back().polyline = path;
    }
    return el;
}

TEST_CASE("shortest path, benchy") {
    Slic3r::Point scaledStart{ 0,0 };
    std::vector<ExtrusionEntity*> vecIn;
    vecIn.push_back(createEC({ createEP({ { 878100.000000,16525390.000000 },{ 887921.000000,16520972.000000 },{ 897742.000000,16516554.000000 } }),createEP({ { 897742.000000,16516554.000000 },{ 907564.000000,16512137.000000 } }),createEP({ { 907564.000000,16512137.000000 },{ 917385.000000,16507719.000000 } }),createEP({ { 917385.000000,16507719.000000 },{ 927207.000000,16503301.000000 } }),createEP({ { 927207.000000,16503301.000000 },{ 937028.000000,16498884.000000 } }),createEP({ { 937028.000000,16498884.000000 },{ 946850.000000,16494466.000000 } }),createEP({ { 946850.000000,16494466.000000 },{ 956671.000000,16490049.000000 } }),createEP({ { 956671.000000,16490049.000000 },{ 966493.000000,16485631.000000 } }),createEP({ { 966493.000000,16485631.000000 },{ 976314.000000,16481213.000000 } }),createEP({ { 976314.000000,16481213.000000 },{ 986136.000000,16476796.000000 } }),createEP({ { 986136.000000,16476796.000000 },{ 995957.000000,16472378.000000 } }),createEP({ { 995957.000000,16472378.000000 },{ 1005779.000000,16467961.000000 },{ 1077478.000000,16435713.000000 },{ 1092474.000000,16431277.000000 } }),createEP({ { 1092474.000000,16431277.000000 },{ 1107470.000000,16426841.000000 } }),createEP({ { 1107470.000000,16426841.000000 },{ 1122466.000000,16422405.000000 } }),createEP({ { 1122466.000000,16422405.000000 },{ 1137462.000000,16417969.000000 },{ 1158714.000000,16445714.000000 },{ 1179966.000000,16473460.000000 },{ 1189708.000000,16484103.000000 },{ 1199450.000000,16494746.000000 },{ 1221746.000000,16517199.000000 } }),createEP({ { 1221746.000000,16517199.000000 },{ 1244043.000000,16539653.000000 },{ 1246055.000000,16541104.000000 },{ 1248068.000000,16542556.000000 },{ 1319790.000000,16593937.000000 },{ 1391513.000000,16645319.000000 },{ 1414657.000000,16660688.000000 },{ 1437801.000000,16676058.000000 },{ 1450972.000000,16682278.000000 },{ 1464143.000000,16688498.000000 },{ 1539738.000000,16722501.000000 },{ 1615334.000000,16756505.000000 },{ 1661856.000000,16774140.000000 },{ 1708379.000000,16791776.000000 },{ 1720407.000000,16796112.000000 },{ 1732436.000000,16800449.000000 },{ 1761156.000000,16806673.000000 },{ 1789877.000000,16812897.000000 },{ 1878306.000000,16828588.000000 },{ 1966736.000000,16844280.000000 },{ 1999016.000000,16848610.000000 },{ 2031296.000000,16852940.000000 },{ 2058215.000000,16855401.000000 },{ 2085134.000000,16857862.000000 },{ 2147306.000000,16857126.000000 },{ 2209478.000000,16856391.000000 },{ 2242031.000000,16854630.000000 },{ 2274584.000000,16852870.000000 },{ 2315541.000000,16848917.000000 },{ 2356498.000000,16844964.000000 },{ 2404151.000000,16835862.000000 },{ 2451805.000000,16826760.000000 },{ 2484780.000000,16818950.000000 },{ 2517755.000000,16811141.000000 },{ 2573546.000000,16795317.000000 },{ 2629338.000000,16779494.000000 },{ 2658411.000000,16768255.000000 },{ 2687484.000000,16757017.000000 },{ 2717152.000000,16744106.000000 },{ 2746820.000000,16731195.000000 },{ 2809338.000000,16700838.000000 },{ 2871856.000000,16670482.000000 },{ 2888552.000000,16660119.000000 },{ 2905248.000000,16649756.000000 },{ 2934052.000000,16630045.000000 },{ 2962857.000000,16610334.000000 },{ 3033029.000000,16557557.000000 },{ 3103202.000000,16504781.000000 },{ 3120280.000000,16491182.000000 },{ 3137358.000000,16477584.000000 },{ 3146176.000000,16468067.000000 },{ 3154995.000000,16458551.000000 },{ 3213110.000000,16393738.000000 },{ 3271226.000000,16328925.000000 },{ 3293738.000000,16301440.000000 },{ 3316250.000000,16273955.000000 },{ 3320785.000000,16266275.000000 },{ 3325321.000000,16258596.000000 },{ 3384346.000000,16156053.000000 },{ 3443372.000000,16053511.000000 },{ 3448057.000000,16043151.000000 },{ 3452742.000000,16032792.000000 },{ 3469113.000000,15990341.000000 },{ 3485484.000000,15947891.000000 },{ 3507174.000000,15880460.000000 },{ 3528865.000000,15813030.000000 },{ 3532103.000000,15797974.000000 },{ 3535341.000000,15782919.000000 },{ 3541494.000000,15746060.000000 },{ 3547647.000000,15709202.000000 },{ 3556303.000000,15636725.000000 },{ 3564960.000000,15564248.000000 },{ 3731698.000000,15570949.000000 },{ 3739926.000000,15571279.000000 },{ 3748155.000000,15571610.000000 } }),createEP({ { 3748155.000000,15571610.000000 },{ 3756384.000000,15571941.000000 } }),createEP({ { 3756384.000000,15571941.000000 },{ 3764612.000000,15572271.000000 } }),createEP({ { 3764612.000000,15572271.000000 },{ 3772841.000000,15572602.000000 } }),createEP({ { 3772841.000000,15572602.000000 },{ 3781070.000000,15572933.000000 } }),createEP({ { 3781070.000000,15572933.000000 },{ 3789298.000000,15573263.000000 } }),createEP({ { 3789298.000000,15573263.000000 },{ 3797527.000000,15573594.000000 } }),createEP({ { 3797527.000000,15573594.000000 },{ 3805756.000000,15573925.000000 } }),createEP({ { 3805756.000000,15573925.000000 },{ 3813985.000000,15574256.000000 } }),createEP({ { 3813985.000000,15574256.000000 },{ 3822213.000000,15574586.000000 } }),createEP({ { 3822213.000000,15574586.000000 },{ 3830442.000000,15574917.000000 } }),createEP({ { 3830442.000000,15574917.000000 },{ 3838671.000000,15575248.000000 } }),createEP({ { 3838671.000000,15575248.000000 },{ 3846899.000000,15575578.000000 } }),createEP({ { 3846899.000000,15575578.000000 },{ 3855128.000000,15575909.000000 } }),createEP({ { 3855128.000000,15575909.000000 },{ 3863357.000000,15576240.000000 },{ 3871586.000000,15576571.000000 } }) }, true));
    vecIn.push_back(createEC({ createEP({ { 1137462.000000,16417969.000000 },{ 1123932.000000,16386612.000000 } }),createEP({ { 1123932.000000,16386612.000000 },{ 1110403.000000,16355255.000000 },{ 1107746.000000,16348720.000000 },{ 1105089.000000,16342185.000000 },{ 1094548.000000,16312674.000000 } }),createEP({ { 1094548.000000,16312674.000000 },{ 1084008.000000,16283163.000000 },{ 1070641.000000,16239737.000000 } }),createEP({ { 1070641.000000,16239737.000000 },{ 1057275.000000,16196312.000000 } }),createEP({ { 1057275.000000,16196312.000000 },{ 1043909.000000,16152886.000000 } }),createEP({ { 1043909.000000,16152886.000000 },{ 1030543.000000,16109461.000000 },{ 1022975.000000,16078734.000000 } }),createEP({ { 1022975.000000,16078734.000000 },{ 1015408.000000,16048007.000000 },{ 991511.000000,15918668.000000 } }),createEP({ { 991511.000000,15918668.000000 },{ 967614.000000,15789329.000000 },{ 964603.000000,15765409.000000 },{ 961592.000000,15741489.000000 },{ 955865.000000,15656035.000000 },{ 950139.000000,15570581.000000 },{ 949373.000000,15536454.000000 },{ 953149.000000,15365631.000000 },{ 956854.000000,15319807.000000 },{ 974852.000000,15190880.000000 } }),createEP({ { 974852.000000,15190880.000000 },{ 992850.000000,15061953.000000 },{ 998262.000000,15034726.000000 },{ 1003675.000000,15007500.000000 },{ 1025916.000000,14921296.000000 } }),createEP({ { 1025916.000000,14921296.000000 },{ 1048157.000000,14835093.000000 },{ 1056484.000000,14808044.000000 } }),createEP({ { 1056484.000000,14808044.000000 },{ 1064811.000000,14780995.000000 },{ 1080397.000000,14737420.000000 } }),createEP({ { 1080397.000000,14737420.000000 },{ 1095983.000000,14693845.000000 } }),createEP({ { 1095983.000000,14693845.000000 },{ 1111569.000000,14650270.000000 } }),createEP({ { 1111569.000000,14650270.000000 },{ 1127155.000000,14606695.000000 },{ 1128495.000000,14603006.000000 },{ 1129835.000000,14599317.000000 },{ 1140845.000000,14581392.000000 },{ 1151856.000000,14563468.000000 },{ 1157385.000000,14557229.000000 } }),createEP({ { 1157385.000000,14557229.000000 },{ 1162915.000000,14550991.000000 },{ 1188918.000000,14522285.000000 },{ 1214921.000000,14493579.000000 },{ 1251327.000000,14460342.000000 },{ 1287733.000000,14427105.000000 },{ 1289911.000000,14425132.000000 },{ 1292089.000000,14423159.000000 },{ 1325684.000000,14400767.000000 },{ 1359279.000000,14378375.000000 },{ 1396436.000000,14356276.000000 } }),createEP({ { 1396436.000000,14356276.000000 },{ 1433594.000000,14334177.000000 },{ 1513740.000000,14294019.000000 },{ 1593887.000000,14253862.000000 },{ 1603167.000000,14249363.000000 },{ 1612447.000000,14244865.000000 },{ 1642667.000000,14234572.000000 },{ 1672888.000000,14224279.000000 },{ 1737734.000000,14205110.000000 },{ 1802581.000000,14185941.000000 },{ 1823709.000000,14181212.000000 },{ 1844838.000000,14176484.000000 },{ 1876811.000000,14170718.000000 },{ 1908784.000000,14164952.000000 },{ 1955103.000000,14158584.000000 },{ 2001423.000000,14152217.000000 },{ 2044403.000000,14149242.000000 },{ 2087384.000000,14146268.000000 },{ 2128930.000000,14145624.000000 },{ 2170477.000000,14144981.000000 },{ 2190032.000000,14145725.000000 },{ 2209588.000000,14146469.000000 },{ 2322841.000000,14160132.000000 },{ 2436094.000000,14173796.000000 },{ 2465787.000000,14178549.000000 },{ 2495480.000000,14183303.000000 },{ 2506994.000000,14186952.000000 },{ 2518509.000000,14190601.000000 },{ 2602986.000000,14218819.000000 },{ 2687463.000000,14247038.000000 },{ 2717837.000000,14258610.000000 },{ 2748211.000000,14270183.000000 },{ 2750428.000000,14271135.000000 },{ 2752645.000000,14272087.000000 },{ 2828792.000000,14313453.000000 },{ 2904940.000000,14354819.000000 },{ 2934950.000000,14372905.000000 },{ 2964960.000000,14390992.000000 },{ 2974934.000000,14397627.000000 },{ 2984908.000000,14404262.000000 },{ 3043892.000000,14451946.000000 },{ 3102876.000000,14499630.000000 },{ 3128864.000000,14522603.000000 },{ 3154852.000000,14545576.000000 },{ 3170119.000000,14560315.000000 },{ 3185387.000000,14575054.000000 },{ 3228258.000000,14625106.000000 },{ 3271129.000000,14675159.000000 },{ 3298040.000000,14710383.000000 },{ 3324951.000000,14745607.000000 },{ 3333845.000000,14758698.000000 },{ 3342740.000000,14771790.000000 },{ 3397078.000000,14871864.000000 },{ 3451417.000000,14971938.000000 },{ 3463213.000000,14995473.000000 },{ 3475010.000000,15019009.000000 },{ 3480760.000000,15037411.000000 },{ 3486511.000000,15055814.000000 },{ 3510225.000000,15138646.000000 },{ 3533940.000000,15221478.000000 },{ 3540926.000000,15249696.000000 },{ 3547913.000000,15277914.000000 },{ 3548660.000000,15286274.000000 },{ 3549407.000000,15294635.000000 },{ 3556137.000000,15379967.000000 },{ 3562867.000000,15465300.000000 },{ 3564076.000000,15502110.000000 },{ 3565286.000000,15538920.000000 },{ 3587192.000000,16205638.000000 },{ 3587462.000000,16213868.000000 } }),createEP({ { 3587462.000000,16213868.000000 },{ 3587732.000000,16222099.000000 } }),createEP({ { 3587732.000000,16222099.000000 },{ 3588003.000000,16230330.000000 } }),createEP({ { 3588003.000000,16230330.000000 },{ 3588273.000000,16238561.000000 } }),createEP({ { 3588273.000000,16238561.000000 },{ 3588544.000000,16246792.000000 } }),createEP({ { 3588544.000000,16246792.000000 },{ 3588814.000000,16255023.000000 } }),createEP({ { 3588814.000000,16255023.000000 },{ 3589085.000000,16263254.000000 } }),createEP({ { 3589085.000000,16263254.000000 },{ 3589355.000000,16271485.000000 } }),createEP({ { 3589355.000000,16271485.000000 },{ 3589626.000000,16279715.000000 } }),createEP({ { 3589626.000000,16279715.000000 },{ 3589896.000000,16287946.000000 } }),createEP({ { 3589896.000000,16287946.000000 },{ 3590167.000000,16296177.000000 } }),createEP({ { 3590167.000000,16296177.000000 },{ 3590437.000000,16304408.000000 } }),createEP({ { 3590437.000000,16304408.000000 },{ 3590708.000000,16312639.000000 } }),createEP({ { 3590708.000000,16312639.000000 },{ 3590978.000000,16320870.000000 } }),createEP({ { 3590978.000000,16320870.000000 },{ 3591249.000000,16329101.000000 } }),createEP({ { 3591249.000000,16329101.000000 },{ 3591519.000000,16337332.000000 },{ 3591790.000000,16345563.000000 } }) }, true));
    // !!! BUG !! here infinite loop when creating validate_graph_and_queue at ShortestPath~221 (pt == pt_other->edge_out)
    auto out = chain_extrusion_entities(vecIn, &scaledStart);
    //if it does not trigger assert nor bugs, success
    REQUIRE(out.size() == vecIn.size());
}

TEST_CASE("shortest path, rotatated cube") {
    Slic3r::Point scaledStart{ 4624477,339410 };
    std::vector<ExtrusionEntity*> vecIn;
    vecIn.push_back(createEP({ { 7067307.000000,4796691.000000 },{ 4666869.000000,2396253.000000 },{ 4378532.000000,2684590.000000 },{ 6649218.000000,4955276.000000 },{ 6360881.000000,5243613.000000 },{ 4090195.000000,2972927.000000 },{ 3801858.000000,3261263.000000 },{ 6072544.000000,5531950.000000 },{ 5784207.000000,5820286.000000 },{ 3513521.000000,3549600.000000 },{ 3225184.000000,3837937.000000 },{ 5495870.000000,6108623.000000 },{ 5207533.000000,6396960.000000 },{ 2936847.000000,4126274.000000 },{ 2648510.000000,4414611.000000 },{ 5048948.000000,6815049.000000 } }));
    vecIn.push_back(createEC({ createEL({ { { 7458539.000000,4666904.000000 },{ 7412432.000000,4596711.000000 } },{ { 7412432.000000,4596711.000000 },{ 7366326.000000,4526519.000000 },{ 4807289.000000,1967482.000000 },{ 4737096.000000,1921375.000000 } },{ { 4737096.000000,1921375.000000 },{ 4666904.000000,1875269.000000 },{ 4596711.000000,1921375.000000 } },{ { 4596711.000000,1921375.000000 },{ 4526519.000000,1967482.000000 },{ 1967482.000000,4526519.000000 },{ 1921375.000000,4596711.000000 } },{ { 1921375.000000,4596711.000000 },{ 1875269.000000,4666904.000000 },{ 1921375.000000,4737096.000000 } },{ { 1921375.000000,4737096.000000 },{ 1967482.000000,4807289.000000 },{ 4526519.000000,7366326.000000 },{ 4596711.000000,7412432.000000 } },{ { 4596711.000000,7412432.000000 },{ 4666904.000000,7458539.000000 },{ 4737096.000000,7412432.000000 } },{ { 4737096.000000,7412432.000000 },{ 4807289.000000,7366326.000000 },{ 7366326.000000,4807289.000000 },{ 7412432.000000,4737096.000000 } },{ { 7412432.000000,4737096.000000 },{ 7458539.000000,4666904.000000 } } }) }, true));
    auto out = chain_extrusion_entities(vecIn, &scaledStart);
    //if it does not trigger assert nor bugs, success
    REQUIRE(out.size() == vecIn.size());
}

TEST_CASE("shortest path, 30x30 cube") {
    Slic3r::Point scaledStart{ 297300,21000 };
    std::vector<ExtrusionEntity*> vecIn;
    vecIn.push_back(createEP({ { 10917563,28708043 },{ 11306585,28570993 },{ 11798176,28512033 },{ 12289767,28552082 },{ 12781357,28705331 },{ 12796742,28708043 },{ 18783013,28708043 },{ 19172036,28570993 },{ 19663627,28512033 },{ 20155217,28552082 },{ 20646808,28705331 },{ 20662193,28708043 },{ 26648464,28708043 },{ 27037487,28570993 },{ 27529078,28512033 },{ 28020668,28552082 },{ 28512259,28705331 },{ 28527644,28708043 },{ 28708043,28708043 },{ 28708043,24939938 },{ 28512259,24811452 },{ 28020668,24638268 },{ 27529078,24579308 },{ 27037487,24619357 },{ 26545896,24772606 },{ 26054306,25076003 },{ 25562715,25529067 },{ 25071124,25991364 },{ 24579534,26313978 },{ 24087943,26487162 },{ 23596352,26546122 },{ 23104762,26506073 },{ 22613171,26352824 },{ 22121580,26049427 },{ 21629990,25596363 },{ 21138399,25134066 },{ 20646808,24811452 },{ 20155217,24638268 },{ 19663627,24579308 },{ 19172036,24619357 },{ 18680445,24772606 },{ 18188855,25076003 },{ 17697264,25529067 },{ 17205673,25991364 },{ 16714083,26313978 },{ 16222492,26487162 },{ 15730901,26546122 },{ 15239311,26506073 },{ 14747720,26352824 },{ 14256129,26049427 },{ 13764539,25596363 },{ 13272948,25134066 },{ 12781357,24811452 },{ 12289767,24638268 },{ 11798176,24579308 },{ 11306585,24619357 },{ 10814995,24772606 },{ 10323404,25076003 },{ 9831813,25529067 },{ 9340222,25991364 },{ 8848632,26313978 },{ 8357041,26487162 },{ 7865450,26546122 },{ 7373860,26506073 },{ 6882269,26352824 },{ 6390678,26049427 },{ 5899088,25596363 },{ 5407497,25134066 },{ 4915906,24811452 },{ 4424316,24638268 },{ 3932725,24579308 },{ 3441134,24619357 },{ 2949544,24772606 },{ 2457953,25076003 },{ 1966362,25529067 },{ 1474772,25991364 },{ 1291956,26111340 },{ 1291956,28708043 },{ 3052112,28708043 },{ 3441134,28570993 },{ 3932725,28512033 },{ 4424316,28552082 },{ 4915906,28705331 },{ 4931291,28708043 } }));
    vecIn.push_back(createEP({ { 1291956,22229531 },{ 1474772,22116701 },{ 1966362,21663638 },{ 2457953,21201341 },{ 2949544,20878726 },{ 3441134,20705542 },{ 3932725,20646582 },{ 4424316,20686632 },{ 4915906,20839880 },{ 5407497,21143278 },{ 5899088,21596341 },{ 6390678,22058638 },{ 6882269,22381253 },{ 7373860,22554437 },{ 7865450,22613397 },{ 8357041,22573348 },{ 8848632,22420099 },{ 9340222,22116701 },{ 9831813,21663638 },{ 10323404,21201341 },{ 10814995,20878726 },{ 11306585,20705542 },{ 11798176,20646582 },{ 12289767,20686632 },{ 12781357,20839880 },{ 13272948,21143278 },{ 13764539,21596341 },{ 14256129,22058638 },{ 14747720,22381253 },{ 15239311,22554437 },{ 15730901,22613397 },{ 16222492,22573348 },{ 16714083,22420099 },{ 17205673,22116701 },{ 17697264,21663638 },{ 18188855,21201341 },{ 18680445,20878726 },{ 19172036,20705542 },{ 19663627,20646582 },{ 20155217,20686632 },{ 20646808,20839880 },{ 21138399,21143278 },{ 21629990,21596341 },{ 22121580,22058638 },{ 22613171,22381253 },{ 23104762,22554437 },{ 23596352,22613397 },{ 24087943,22573348 },{ 24579534,22420099 },{ 25071124,22116701 },{ 25562715,21663638 },{ 26054306,21201341 },{ 26545896,20878726 },{ 27037487,20705542 },{ 27529078,20646582 },{ 28020668,20686632 },{ 28512259,20839880 },{ 28708043,20960713 },{ 28708043,17074487 },{ 28512259,16946001 },{ 28020668,16772817 },{ 27529078,16713857 },{ 27037487,16753906 },{ 26545896,16907155 },{ 26054306,17210552 },{ 25562715,17663616 },{ 25071124,18125913 },{ 24579534,18448527 },{ 24087943,18621711 },{ 23596352,18680671 },{ 23104762,18640622 },{ 22613171,18487373 },{ 22121580,18183976 },{ 21629990,17730912 },{ 21138399,17268615 },{ 20646808,16946001 },{ 20155217,16772817 },{ 19663627,16713857 },{ 19172036,16753906 },{ 18680445,16907155 },{ 18188855,17210552 },{ 17697264,17663616 },{ 17205673,18125913 },{ 16714083,18448527 },{ 16222492,18621711 },{ 15730901,18680671 },{ 15239311,18640622 },{ 14747720,18487373 },{ 14256129,18183976 },{ 13764539,17730912 },{ 13272948,17268615 },{ 12781357,16946001 },{ 12289767,16772817 },{ 11798176,16713857 },{ 11306585,16753906 },{ 10814995,16907155 },{ 10323404,17210552 },{ 9831813,17663616 },{ 9340222,18125913 },{ 8848632,18448527 },{ 8357041,18621711 },{ 7865450,18680671 },{ 7373860,18640622 },{ 6882269,18487373 },{ 6390678,18183976 },{ 5899088,17730912 },{ 5407497,17268615 },{ 4915906,16946001 },{ 4424316,16772817 },{ 3932725,16713857 },{ 3441134,16753906 },{ 2949544,16907155 },{ 2457953,17210552 },{ 1966362,17663616 },{ 1474772,18125913 },{ 1291956,18245889 },{ 1291956,14364080 },{ 1474772,14251250 },{ 1966362,13798187 },{ 2457953,13335890 },{ 2949544,13013275 },{ 3441134,12840091 },{ 3932725,12781131 },{ 4424316,12821181 },{ 4915906,12974429 },{ 5407497,13277827 },{ 5899088,13730890 },{ 6390678,14193187 },{ 6882269,14515802 },{ 7373860,14688986 },{ 7865450,14747946 },{ 8357041,14707897 },{ 8848632,14554648 },{ 9340222,14251250 },{ 9831813,13798187 },{ 10323404,13335890 },{ 10814995,13013275 },{ 11306585,12840091 },{ 11798176,12781131 },{ 12289767,12821181 },{ 12781357,12974429 },{ 13272948,13277827 },{ 13764539,13730890 },{ 14256129,14193187 },{ 14747720,14515802 },{ 15239311,14688986 },{ 15730901,14747946 },{ 16222492,14707897 },{ 16714083,14554648 },{ 17205673,14251250 },{ 17697264,13798187 },{ 18188855,13335890 },{ 18680445,13013275 },{ 19172036,12840091 },{ 19663627,12781131 },{ 20155217,12821181 },{ 20646808,12974429 },{ 21138399,13277827 },{ 21629990,13730890 },{ 22121580,14193187 },{ 22613171,14515802 },{ 23104762,14688986 },{ 23596352,14747946 },{ 24087943,14707897 },{ 24579534,14554648 },{ 25071124,14251250 },{ 25562715,13798187 },{ 26054306,13335890 },{ 26545896,13013275 },{ 27037487,12840091 },{ 27529078,12781131 },{ 28020668,12821181 },{ 28512259,12974429 },{ 28708043,13095262 },{ 28708043,9209036 },{ 28512259,9080550 },{ 28020668,8907366 },{ 27529078,8848406 },{ 27037487,8888455 },{ 26545896,9041704 },{ 26054306,9345101 },{ 25562715,9798165 },{ 25071124,10260462 },{ 24579534,10583076 },{ 24087943,10756260 },{ 23596352,10815220 },{ 23104762,10775171 },{ 22613171,10621922 },{ 22121580,10318525 },{ 21629990,9865462 },{ 21138399,9403164 },{ 20646808,9080550 },{ 20155217,8907366 },{ 19663627,8848406 },{ 19172036,8888455 },{ 18680445,9041704 },{ 18188855,9345101 },{ 17697264,9798165 },{ 17205673,10260462 },{ 16714083,10583076 },{ 16222492,10756260 },{ 15730901,10815220 },{ 15239311,10775171 },{ 14747720,10621922 },{ 14256129,10318525 },{ 13764539,9865462 },{ 13272948,9403164 },{ 12781357,9080550 },{ 12289767,8907366 },{ 11798176,8848406 },{ 11306585,8888455 },{ 10814995,9041704 },{ 10323404,9345101 },{ 9831813,9798165 },{ 9340222,10260462 },{ 8848632,10583076 },{ 8357041,10756260 },{ 7865450,10815220 },{ 7373860,10775171 },{ 6882269,10621922 },{ 6390678,10318525 },{ 5899088,9865462 },{ 5407497,9403164 },{ 4915906,9080550 },{ 4424316,8907366 },{ 3932725,8848406 },{ 3441134,8888455 },{ 2949544,9041704 },{ 2457953,9345101 },{ 1966362,9798165 },{ 1474772,10260462 },{ 1291956,10380438 },{ 1291956,6498629 },{ 1474772,6385799 },{ 1966362,5932736 },{ 2457953,5470439 },{ 2949544,5147825 },{ 3441134,4974641 },{ 3932725,4915680 },{ 4424316,4955730 },{ 4915906,5108978 },{ 5407497,5412376 },{ 5899088,5865439 },{ 6390678,6327736 },{ 6882269,6650351 },{ 7373860,6823535 },{ 7865450,6882495 },{ 8357041,6842446 },{ 8848632,6689197 },{ 9340222,6385799 },{ 9831813,5932736 },{ 10323404,5470439 },{ 10814995,5147825 },{ 11306585,4974641 },{ 11798176,4915680 },{ 12289767,4955730 },{ 12781357,5108978 },{ 13272948,5412376 },{ 13764539,5865439 },{ 14256129,6327736 },{ 14747720,6650351 },{ 15239311,6823535 },{ 15730901,6882495 },{ 16222492,6842446 },{ 16714083,6689197 },{ 17205673,6385799 },{ 17697264,5932736 },{ 18188855,5470439 },{ 18680445,5147825 },{ 19172036,4974641 },{ 19663627,4915680 },{ 20155217,4955730 },{ 20646808,5108978 },{ 21138399,5412376 },{ 21629990,5865439 },{ 22121580,6327736 },{ 22613171,6650351 },{ 23104762,6823535 },{ 23596352,6882495 },{ 24087943,6842446 },{ 24579534,6689197 },{ 25071124,6385799 },{ 25562715,5932736 },{ 26054306,5470439 },{ 26545896,5147825 },{ 27037487,4974641 },{ 27529078,4915680 },{ 28020668,4955730 },{ 28512259,5108978 },{ 28708043,5229811 },{ 28708043,1291956 },{ 26358424,1291956 },{ 20763920,1291956 },{ 18492973,1291956 },{ 12898469,1291956 },{ 10627523,1291956 },{ 5033018,1291956 },{ 2762072,1291956 },{ 2457953,1479650 },{ 1966362,1932714 },{ 1474772,2395011 },{ 1291956,2514987 } }));
    vecIn.push_back(createEP({ { 10627523,1291956 },{ 10323404,1479650 },{ 9831813,1932714 },{ 9340222,2395011 },{ 8848632,2717625 },{ 8357041,2890809 },{ 7865450,2949770 },{ 7373860,2909720 },{ 6882269,2756471 },{ 6390678,2453074 },{ 5899088,2000011 },{ 5407497,1537714 },{ 5033018,1291956 } }));
    vecIn.push_back(createEP({ { 18492973,1291956 },{ 18188855,1479650 },{ 17697264,1932714 },{ 17205673,2395011 },{ 16714083,2717625 },{ 16222492,2890809 },{ 15730901,2949770 },{ 15239311,2909720 },{ 14747720,2756471 },{ 14256129,2453074 },{ 13764539,2000011 },{ 13272948,1537714 },{ 12898469,1291956 } }));
    vecIn.push_back(createEP({ { 26358424,1291956 },{ 26054306,1479650 },{ 25562715,1932714 },{ 25071124,2395011 },{ 24579534,2717625 },{ 24087943,2890809 },{ 23596352,2949770 },{ 23104762,2909720 },{ 22613171,2756471 },{ 22121580,2453074 },{ 21629990,2000011 },{ 21138399,1537714 },{ 20763920,1291956 } }));
    auto out = chain_extrusion_entities(vecIn, &scaledStart);
    //if it does not trigger assert nor bugs, success
    REQUIRE(out.size() == vecIn.size());
}

TEST_CASE("Line::parallel_to", "[Geometry]"){
    Line l{ { 100000, 0 }, { 0, 0 } };
    Line l2{ { 200000, 0 }, { 0, 0 } };
    REQUIRE(l.parallel_to(l));
    REQUIRE(l.parallel_to(l2));

    Line l3(l2);
    l3.rotate(0.9 * EPSILON, { 0, 0 });
    REQUIRE(l.parallel_to(l3));

    Line l4(l2);
    l4.rotate(1.1 * EPSILON, { 0, 0 });
    REQUIRE(! l.parallel_to(l4));

    // The angle epsilon is so low that vectors shorter than 100um rotated by epsilon radians are not rotated at all.
    Line l5{ { 20000, 0 }, { 0, 0 } };
    l5.rotate(1.1 * EPSILON, { 0, 0 });
    REQUIRE(l.parallel_to(l5));

    l.rotate(1., { 0, 0 });
    Point offset{ 342876, 97636249 };
    l.translate(offset);
    l3.rotate(1., { 0, 0 });
    l3.translate(offset);
    l4.rotate(1., { 0, 0 });
    l4.translate(offset);
    REQUIRE(l.parallel_to(l3));
    REQUIRE(!l.parallel_to(l4));
}

TEST_CASE("Line::perpendicular_to", "[Geometry]") {
    Line l{ { 100000, 0 }, { 0, 0 } };
    Line l2{ { 0, 200000 }, { 0, 0 } };
    REQUIRE(! l.perpendicular_to(l));
    REQUIRE(l.perpendicular_to(l2));

    Line l3(l2);
    l3.rotate(0.9 * EPSILON, { 0, 0 });
    REQUIRE(l.perpendicular_to(l3));

    Line l4(l2);
    l4.rotate(1.1 * EPSILON, { 0, 0 });
    REQUIRE(! l.perpendicular_to(l4));

    // The angle epsilon is so low that vectors shorter than 100um rotated by epsilon radians are not rotated at all.
    Line l5{ { 0, 20000 }, { 0, 0 } };
    l5.rotate(1.1 * EPSILON, { 0, 0 });
    REQUIRE(l.perpendicular_to(l5));

    l.rotate(1., { 0, 0 });
    Point offset{ 342876, 97636249 };
    l.translate(offset);
    l3.rotate(1., { 0, 0 });
    l3.translate(offset);
    l4.rotate(1., { 0, 0 });
    l4.translate(offset);
    REQUIRE(l.perpendicular_to(l3));
    REQUIRE(! l.perpendicular_to(l4));
}

TEST_CASE("Polygon::contains works properly", "[Geometry]"){
   // this test was failing on Windows (GH #1950)
    Slic3r::Polygon polygon(std::vector<Point>({
        Point(207802834,-57084522),
        Point(196528149,-37556190),
        Point(173626821,-25420928),
        Point(171285751,-21366123),
        Point(118673592,-21366123),
        Point(116332562,-25420928),
        Point(93431208,-37556191),
        Point(82156517,-57084523),
        Point(129714478,-84542120),
        Point(160244873,-84542120)
    }));
    Point point(95706562, -57294774);
    REQUIRE(polygon.contains(point));
}

SCENARIO("Intersections of line segments", "[Geometry]"){
    GIVEN("Integer coordinates"){
        Line line1(Point(5,15),Point(30,15));
        Line line2(Point(10,20), Point(10,10));
        THEN("The intersection is valid"){
            Point point;
            line1.intersection(line2,&point);
            REQUIRE(Point(10,15) == point);
        }
    }

    GIVEN("Scaled coordinates"){
        Line line1(Point(73.6310778185108 / 0.00001, 371.74239268924 / 0.00001), Point(73.6310778185108 / 0.00001, 501.74239268924 / 0.00001));
        Line line2(Point(75/0.00001, 437.9853/0.00001), Point(62.7484/0.00001, 440.4223/0.00001));
        THEN("There is still an intersection"){
            Point point;
            REQUIRE(line1.intersection(line2,&point));
        }
    }
}

SCENARIO("polygon_is_convex works") {
    GIVEN("A square of dimension 10") {
        WHEN("Polygon is convex clockwise") {
            Polygon cw_square  { { {0, 0}, {0,10}, {10,10}, {10,0} } };
            THEN("it is not convex") {
                REQUIRE(! polygon_is_convex(cw_square));
            }
        }
        WHEN("Polygon is convex counter-clockwise") {
            Polygon ccw_square { { {0, 0}, {10,0}, {10,10}, {0,10} } };
            THEN("it is convex") {
                REQUIRE(polygon_is_convex(ccw_square));
            }
        } 
    }
    GIVEN("A concave polygon") {
        Polygon concave = { {0,0}, {10,0}, {10,10}, {0,10}, {0,6}, {4,6}, {4,4}, {0,4} };
        THEN("It is not convex") {
            REQUIRE(! polygon_is_convex(concave));
        }
    }
}

TEST_CASE("Creating a polyline generates the obvious lines", "[Geometry]"){
    Slic3r::Polyline polyline;
    polyline.points = std::vector<Point>({Point(0, 0), Point(10, 0), Point(20, 0)});
    REQUIRE(polyline.lines().at(0).a == Point(0,0));
    REQUIRE(polyline.lines().at(0).b == Point(10,0));
    REQUIRE(polyline.lines().at(1).a == Point(10,0));
    REQUIRE(polyline.lines().at(1).b == Point(20,0));
}

TEST_CASE("Splitting a Polygon generates a polyline correctly", "[Geometry]"){
    Slic3r::Polygon polygon(std::vector<Point>({Point(0, 0), Point(10, 0), Point(5, 5)}));
    Slic3r::Polyline split = polygon.split_at_index(1);
    REQUIRE(split.points[0]==Point(10,0));
    REQUIRE(split.points[1]==Point(5,5));
    REQUIRE(split.points[2]==Point(0,0));
    REQUIRE(split.points[3]==Point(10,0));
}


TEST_CASE("Bounding boxes are scaled appropriately", "[Geometry]"){
    BoundingBox bb(std::vector<Point>({Point(0, 1), Point(10, 2), Point(20, 2)}));
    bb.scale(2);
    REQUIRE(bb.min == Point(0,2));
    REQUIRE(bb.max == Point(40,4));
}


TEST_CASE("Offseting a line generates a polygon correctly", "[Geometry]"){
	Slic3r::Polyline tmp = { Point(10,10), Point(20,10) };
    Slic3r::Polygon area = offset(tmp,5).at(0);
    REQUIRE(area.area() == Slic3r::Polygon(std::vector<Point>({Point(10,5),Point(20,5),Point(20,15),Point(10,15)})).area());
}

SCENARIO("Circle Fit, TaubinFit with Newton's method", "[Geometry]") {
    GIVEN("A vector of Vec2ds arranged in a half-circle with approximately the same distance R from some point") {
        Vec2d expected_center(-6, 0);
        Pointfs sample {Vec2d(6.0, 0), Vec2d(5.1961524, 3), Vec2d(3 ,5.1961524), Vec2d(0, 6.0), Vec2d(3, 5.1961524), Vec2d(-5.1961524, 3), Vec2d(-6.0, 0)};
        std::transform(sample.begin(), sample.end(), sample.begin(), [expected_center] (const Vec2d& a) { return a + expected_center;});

        WHEN("Circle fit is called on the entire array") {
            Vec2d result_center(0,0);
            result_center = Geometry::circle_center_taubin_newton(sample);
            THEN("A center point of -6,0 is returned.") {
                REQUIRE(is_approx(result_center, expected_center));
            }
        }
        WHEN("Circle fit is called on the first four points") {
            Vec2d result_center(0,0);
            result_center = Geometry::circle_center_taubin_newton(sample.cbegin(), sample.cbegin()+4);
            THEN("A center point of -6,0 is returned.") {
                REQUIRE(is_approx(result_center, expected_center));
            }
        }
        WHEN("Circle fit is called on the middle four points") {
            Vec2d result_center(0,0);
            result_center = Geometry::circle_center_taubin_newton(sample.cbegin()+2, sample.cbegin()+6);
            THEN("A center point of -6,0 is returned.") {
                REQUIRE(is_approx(result_center, expected_center));
            }
        }
    }
    GIVEN("A vector of Vec2ds arranged in a half-circle with approximately the same distance R from some point") {
        Vec2d expected_center(-3, 9);
        Pointfs sample {Vec2d(6.0, 0), Vec2d(5.1961524, 3), Vec2d(3 ,5.1961524),
                        Vec2d(0, 6.0), 
                        Vec2d(3, 5.1961524), Vec2d(-5.1961524, 3), Vec2d(-6.0, 0)};

        std::transform(sample.begin(), sample.end(), sample.begin(), [expected_center] (const Vec2d& a) { return a + expected_center;});


        WHEN("Circle fit is called on the entire array") {
            Vec2d result_center(0,0);
            result_center = Geometry::circle_center_taubin_newton(sample);
            THEN("A center point of 3,9 is returned.") {
                REQUIRE(is_approx(result_center, expected_center));
            }
        }
        WHEN("Circle fit is called on the first four points") {
            Vec2d result_center(0,0);
            result_center = Geometry::circle_center_taubin_newton(sample.cbegin(), sample.cbegin()+4);
            THEN("A center point of 3,9 is returned.") {
                REQUIRE(is_approx(result_center, expected_center));
            }
        }
        WHEN("Circle fit is called on the middle four points") {
            Vec2d result_center(0,0);
            result_center = Geometry::circle_center_taubin_newton(sample.cbegin()+2, sample.cbegin()+6);
            THEN("A center point of 3,9 is returned.") {
                REQUIRE(is_approx(result_center, expected_center));
            }
        }
    }
    GIVEN("A vector of Points arranged in a half-circle with approximately the same distance R from some point") {
        Point expected_center { Point::new_scale(-3, 9)};
        Points sample {Point::new_scale(6.0, 0), Point::new_scale(5.1961524, 3), Point::new_scale(3 ,5.1961524), 
                        Point::new_scale(0, 6.0), 
                        Point::new_scale(3, 5.1961524), Point::new_scale(-5.1961524, 3), Point::new_scale(-6.0, 0)};

        std::transform(sample.begin(), sample.end(), sample.begin(), [expected_center] (const Point& a) { return a + expected_center;});


        WHEN("Circle fit is called on the entire array") {
            Point result_center(0,0);
            result_center = Geometry::circle_center_taubin_newton(sample);
            THEN("A center point of scaled 3,9 is returned.") {
                REQUIRE(is_approx(result_center, expected_center));
            }
        }
        WHEN("Circle fit is called on the first four points") {
            Point result_center(0,0);
            result_center = Geometry::circle_center_taubin_newton(sample.cbegin(), sample.cbegin()+4);
            THEN("A center point of scaled 3,9 is returned.") {
                REQUIRE(is_approx(result_center, expected_center));
            }
        }
        WHEN("Circle fit is called on the middle four points") {
            Point result_center(0,0);
            result_center = Geometry::circle_center_taubin_newton(sample.cbegin()+2, sample.cbegin()+6);
            THEN("A center point of scaled 3,9 is returned.") {
                REQUIRE(is_approx(result_center, expected_center));
            }
        }
    }
}

TEST_CASE("smallest_enclosing_circle_welzl", "[Geometry]") {
    // Some random points in plane.
    Points pts { 
        { 89243, 4359 }, { 763465, 59687 }, { 3245, 734987 }, { 2459867, 987634 }, { 759866, 67843982 }, { 9754687, 9834658 }, { 87235089, 743984373 }, 
        { 65874456, 2987546 }, { 98234524, 657654873 }, { 786243598, 287934765 }, { 824356, 734265 }, { 82576449, 7864534 }, { 7826345, 3984765 }
    };

    const auto c = Slic3r::Geometry::smallest_enclosing_circle_welzl(pts);
    // The radius returned is inflated by SCALED_EPSILON, thus all points should be inside.
    bool all_inside = std::all_of(pts.begin(), pts.end(), [c](const Point &pt){ return c.contains(pt.cast<double>()); });
    auto c2(c);
    c2.radius -= SCALED_EPSILON * 2.1;
    auto num_on_boundary = std::count_if(pts.begin(), pts.end(), [c2](const Point& pt) { return ! c2.contains(pt.cast<double>(), SCALED_EPSILON); });

    REQUIRE(all_inside);
    REQUIRE(num_on_boundary == 3);
}

SCENARIO("Path chaining", "[Geometry][!mayfail]") {
	GIVEN("A path") {
		std::vector<Point> points = { Point(26,26),Point(52,26),Point(0,26),Point(26,52),Point(26,0),Point(0,52),Point(52,52),Point(52,0) };
		THEN("Chained with no diagonals (thus 26 units long)") { //this will fail as i deactivated the pusa traveller salesman code.
			std::vector<Points::size_type> indices = chain_points(points);
			for (Points::size_type i = 0; i + 1 < indices.size(); ++ i) {
				double dist = (points.at(indices.at(i)).cast<double>() - points.at(indices.at(i+1)).cast<double>()).norm();
                std::stringstream log;
				REQUIRE(std::abs(dist-26) <= EPSILON);
			}
		}
	}
	GIVEN("Gyroid infill end points") {
		const Polylines polylines = {
			{ {28122608, 3221037}, {27919139, 56036027} },
			{ {33642863, 3400772}, {30875220, 56450360} },
			{ {34579315, 3599827}, {35049758, 55971572} },
			{ {26483070, 3374004}, {23971830, 55763598} },
			{ {38931405, 4678879}, {38740053, 55077714} },
			{ {20311895, 5015778}, {20079051, 54551952} },
			{ {16463068, 6773342}, {18823514, 53992958} },
			{ {44433771, 7424951}, {42629462, 53346059} },
			{ {15697614, 7329492}, {15350896, 52089991} },
			{ {48085792, 10147132}, {46435427, 50792118} },
			{ {48828819, 10972330}, {49126582, 48368374} },
			{ {9654526, 12656711}, {10264020, 47691584} },
			{ {5726905, 18648632}, {8070762, 45082416} },
			{ {54818187, 39579970}, {52974912, 43271272} }, 
			{ {4464342, 37371742}, {5027890, 39106220} },
			{ {54139746, 18417661}, {55177987, 38472580} }, 
			{ {56527590, 32058461}, {56316456, 34067185} },
			{ {3303988, 29215290}, {3569863, 32985633} },
			{ {56255666, 25025857}, {56478310, 27144087} }, 
			{ {4300034, 22805361}, {3667946, 25752601} },
			{ {8266122, 14250611}, {6244813, 17751595} },
			{ {12177955, 9886741}, {10703348, 11491900} } 
		};
		const Polylines chained = chain_polylines(polylines);
        THEN("Chained taking the shortest path") {
            double connection_length = 0.;
            std::cout << "{ {" << chained[0].points.front().x() << ", " << chained[0].points.front().y() << "}, {" << chained[0].points.back().x() << ", " << chained[0].points.back().x() << "} },\n";
            for (size_t i = 1; i < chained.size(); ++i) {
                const Polyline& pl1 = chained[i - 1];
                const Polyline& pl2 = chained[i];
                connection_length += (pl2.first_point() - pl1.last_point()).cast<double>().norm();
                std::cout << "{ {" << chained[i].points.front().x() << ", " << chained[i].points.front().y() << "}, {" << chained[i].points.back().x() << ", " << chained[i].points.back().x() << "} },\n";
            }
            REQUIRE(connection_length < 85206000.);
        }
        const ExtrusionPath pattern(ExtrusionRole::erPerimeter);
        THEN("Chained taking the shortest path with extrusionpaths") {
            ExtrusionEntityCollection coll;
            for (auto poly : polylines)
                coll.entities.push_back(new ExtrusionPath(poly, pattern));
            chain_and_reorder_extrusion_entities(coll.entities, &polylines[18].points.back());
            double connection_length = 0.;
            std::cout << "{ {" << coll.entities[0]->as_polyline().points.front().x() << ", " << coll.entities[0]->as_polyline().points.front().y() << "}, {" << coll.entities[0]->as_polyline().points.back().x() << ", " << coll.entities[0]->as_polyline().points.back().y() << "} },\n";
            for (size_t i = 1; i < coll.entities.size(); ++i) {
                const Polyline& pl1 = coll.entities[i - 1]->as_polyline();
                const Polyline& pl2 = coll.entities[i]->as_polyline();
                connection_length += (pl2.first_point() - pl1.last_point()).cast<double>().norm();
                std::cout << "{ {" << coll.entities[i]->as_polyline().points.front().x() << ", " << coll.entities[i]->as_polyline().points.front().y() << "}, {" << coll.entities[i]->as_polyline().points.back().x() << ", " << coll.entities[i]->as_polyline().points.back().y() << "} },\n";
            }
            REQUIRE(connection_length < 85206000.);
        }
        THEN("Chained can't unfold a eeCollection") {
            ExtrusionEntityCollection coll;
            for (auto poly : polylines)
                coll.entities.push_back(new ExtrusionPath(poly, pattern));
            ExtrusionEntitiesPtr data{ &coll };
            chain_and_reorder_extrusion_entities(data, &polylines[18].points.back());
            double connection_length = 0.;
            for (size_t i = 1; i < coll.entities.size(); ++i) {
                const Polyline& pl1 = coll.entities[i - 1]->as_polyline();
                const Polyline& pl2 = coll.entities[i]->as_polyline();
                connection_length += (pl2.first_point() - pl1.last_point()).cast<double>().norm();
            }
            REQUIRE(connection_length > 85206000.);
            REQUIRE(polylines[18].points.front() != coll.entities[18]->first_point());
        }
        THEN("Chained does not take the shortest path with extrusionpaths if in an un-sortable un-reversable collection") {
            ExtrusionEntityCollection coll;
            for (auto poly : polylines)
                coll.entities.push_back(new ExtrusionPath(poly, pattern));
            ExtrusionEntitiesPtr data{ &coll };
            coll.set_can_sort_reverse(false, false);
            chain_and_reorder_extrusion_entities(data, &polylines[18].points.back());
            double connection_length = 0.;
            for (size_t i = 1; i < coll.entities.size(); ++i) {
                const Polyline& pl1 = coll.entities[i - 1]->as_polyline();
                const Polyline& pl2 = coll.entities[i]->as_polyline();
                connection_length += (pl2.first_point() - pl1.last_point()).cast<double>().norm();
            }
            REQUIRE(connection_length > 85206000.);
            REQUIRE(polylines[18].points.front() == coll.entities[18]->first_point());
        }
        THEN("Chained does not take the shortest path with extrusionpaths if in an un-sortable collection") {
            ExtrusionEntityCollection coll;
            for (auto poly : polylines)
                coll.entities.push_back(new ExtrusionPath(poly, pattern));
            ExtrusionEntitiesPtr data{ &coll };
            coll.set_can_sort_reverse(false, true);
            chain_and_reorder_extrusion_entities(data, &polylines[18].points.back());
            double connection_length = 0.;
            for (size_t i = 1; i < coll.entities.size(); ++i) {
                const Polyline& pl1 = coll.entities[i - 1]->as_polyline();
                const Polyline& pl2 = coll.entities[i]->as_polyline();
                connection_length += (pl2.first_point() - pl1.last_point()).cast<double>().norm();
            }
            REQUIRE(connection_length > 85206000.);
            REQUIRE(polylines[18].points.front() != coll.entities[18]->first_point());
        }
	}
	GIVEN("Loop pieces") {
		Point a { 2185796, 19058485 };
		Point b { 3957902, 18149382 };
		Point c { 2912841, 18790564 };
		Point d { 2831848, 18832390 };
		Point e { 3179601, 18627769 };
		Point f { 3137952, 18653370 };
		Polylines polylines = { { a, b },
								{ c, d },
								{ e, f },
								{ d, a },
								{ f, c },
								{ b, e } };
		Polylines chained = chain_polylines(polylines, &a);
		THEN("Connected without a gap") {
			for (size_t i = 0; i < chained.size(); ++i) {
				const Polyline &pl1 = (i == 0) ? chained.back() : chained[i - 1];
				const Polyline &pl2 = chained[i];
				REQUIRE(pl1.points.back() == pl2.points.front());
			}
		}
	}
}

SCENARIO("Line distances", "[Geometry]"){
    GIVEN("A line"){
        Line line(Point(0, 0), Point(20, 0));
        THEN("Points on the line segment have 0 distance"){
            REQUIRE(line.distance_to(Point(0, 0))  == 0);
            REQUIRE(line.distance_to(Point(20, 0)) == 0);
            REQUIRE(line.distance_to(Point(10, 0)) == 0);
        
        }
        THEN("Points off the line have the appropriate distance"){
            REQUIRE(line.distance_to(Point(10, 10)) == 10);
            REQUIRE(line.distance_to(Point(50, 0)) == 30);
        }
    }
}

SCENARIO("Polygon convex/concave detection", "[Geometry]"){
    GIVEN(("A Square with dimension 100")){
        auto square = Slic3r::Polygon /*new_scale*/(std::vector<Point>({
            Point(100,100),
            Point(200,100),
            Point(200,200),
            Point(100,200)}));
        THEN("It has 4 convex points counterclockwise"){
            REQUIRE(square.concave_points(PI*4/3).size() == 0);
            REQUIRE(square.convex_points(PI*2/3).size() == 4);
        }
        THEN("It has 4 concave points clockwise"){
            square.make_clockwise();
            REQUIRE(square.concave_points(PI*4/3).size() == 4);
            REQUIRE(square.convex_points(PI*2/3).size() == 0);
        }
    }
    GIVEN("A Square with an extra colinearvertex"){
        auto square = Slic3r::Polygon /*new_scale*/(std::vector<Point>({
            Point(150,100),
            Point(200,100),
            Point(200,200),
            Point(100,200),
            Point(100,100)}));
        THEN("It has 4 convex points counterclockwise"){
            REQUIRE(square.concave_points(PI*4/3).size() == 0);
            REQUIRE(square.convex_points(PI*2/3).size() == 4);
        }
    }
    GIVEN("A Square with an extra collinear vertex in different order"){
        auto square = Slic3r::Polygon /*new_scale*/(std::vector<Point>({
            Point(200,200),
            Point(100,200),
            Point(100,100),
            Point(150,100),
            Point(200,100)}));
        THEN("It has 4 convex points counterclockwise"){
            REQUIRE(square.concave_points(PI*4/3).size() == 0);
            REQUIRE(square.convex_points(PI*2/3).size() == 4);
        }
    }

    GIVEN("A triangle"){
        auto triangle = Slic3r::Polygon(std::vector<Point>({
            Point(16000170,26257364),
            Point(714223,461012),
            Point(31286371,461008)
        }));
        THEN("it has three convex vertices"){
            REQUIRE(triangle.concave_points(PI*4/3).size() == 0);
            REQUIRE(triangle.convex_points(PI*2/3).size() == 3);
        }
    }

    GIVEN("A triangle with an extra collinear point"){
        auto triangle = Slic3r::Polygon(std::vector<Point>({
            Point(16000170,26257364),
            Point(714223,461012),
            Point(20000000,461012),
            Point(31286371,461012)
        }));
        THEN("it has three convex vertices"){
            REQUIRE(triangle.concave_points(PI*4/3).size() == 0);
            REQUIRE(triangle.convex_points(PI*2/3).size() == 3);
        }
    }
    GIVEN("A polygon with concave vertices with angles of specifically 4/3pi"){
        // Two concave vertices of this polygon have angle = PI*4/3, so this test fails
        // if epsilon is not used.
        auto polygon = Slic3r::Polygon(std::vector<Point>({
            Point(60246458,14802768),Point(64477191,12360001),
            Point(63727343,11060995),Point(64086449,10853608),
            Point(66393722,14850069),Point(66034704,15057334),
            Point(65284646,13758387),Point(61053864,16200839),
            Point(69200258,30310849),Point(62172547,42483120),
            Point(61137680,41850279),Point(67799985,30310848),
            Point(51399866,1905506),Point(38092663,1905506),
            Point(38092663,692699),Point(52100125,692699)
        }));
        THEN("the correct number of points are detected"){
            REQUIRE(polygon.concave_points(PI*4/3).size() == 6);
            REQUIRE(polygon.convex_points(PI*2/3).size() == 10);
        }
    }
}

TEST_CASE("Triangle Simplification does not result in less than 3 points", "[Geometry]"){
    auto triangle = Slic3r::Polygon(std::vector<Point>({
        Point(16000170,26257364), Point(714223,461012), Point(31286371,461008)
    }));
    REQUIRE(triangle.simplify(250000).at(0).points.size() == 3);
}

SCENARIO("Ported from xs/t/14_geometry.t", "[Geometry]"){
    GIVEN(("square")){
    	Slic3r::Points points { { 100, 100 }, {100, 200 }, { 200, 200 }, { 200, 100 }, { 150, 150 } };
		Slic3r::Polygon hull = Slic3r::Geometry::convex_hull(points);
		SECTION("convex hull returns the correct number of points") { REQUIRE(hull.points.size() == 4); }
    }
	SECTION("arrange returns expected number of positions") {
		Pointfs positions;
		Slic3r::Geometry::arrange(4, Vec2d(20, 20), 5, nullptr, positions);
    	REQUIRE(positions.size() == 4);
    }
	SECTION("directions_parallel") {
    	REQUIRE(Slic3r::Geometry::directions_parallel(0, 0, 0)); 
    	REQUIRE(Slic3r::Geometry::directions_parallel(0, M_PI, 0)); 
    	REQUIRE(Slic3r::Geometry::directions_parallel(0, 0, M_PI / 180));
    	REQUIRE(Slic3r::Geometry::directions_parallel(0, M_PI, M_PI / 180));
    	REQUIRE(! Slic3r::Geometry::directions_parallel(M_PI /2, M_PI, 0));
    	REQUIRE(! Slic3r::Geometry::directions_parallel(M_PI /2, PI, M_PI /180));
    }
}

TEST_CASE("Convex polygon intersection on two disjoint squares", "[Geometry][Rotcalip]") {
    Polygon A{{0, 0}, {10, 0}, {10, 10}, {0, 10}};
    A.scale(1. / SCALING_FACTOR);

    Polygon B = A;
    B.translate(20 / SCALING_FACTOR, 0);

    bool is_inters = Geometry::convex_polygons_intersect(A, B);

    REQUIRE(is_inters == false);
}

TEST_CASE("Convex polygon intersection on two intersecting squares", "[Geometry][Rotcalip]") {
    Polygon A{{0, 0}, {10, 0}, {10, 10}, {0, 10}};
    A.scale(1. / SCALING_FACTOR);

    Polygon B = A;
    B.translate(5 / SCALING_FACTOR, 5 / SCALING_FACTOR);

    bool is_inters = Geometry::convex_polygons_intersect(A, B);

    REQUIRE(is_inters == true);
}

TEST_CASE("Convex polygon intersection on two squares touching one edge", "[Geometry][Rotcalip]") {
    Polygon A{{0, 0}, {10, 0}, {10, 10}, {0, 10}};
    A.scale(1. / SCALING_FACTOR);

    Polygon B = A;
    B.translate(10 / SCALING_FACTOR, 0);

    bool is_inters = Geometry::convex_polygons_intersect(A, B);

    REQUIRE(is_inters == false);
}

TEST_CASE("Convex polygon intersection on two squares touching one vertex", "[Geometry][Rotcalip]") {
    Polygon A{{0, 0}, {10, 0}, {10, 10}, {0, 10}};
    A.scale(1. / SCALING_FACTOR);

    Polygon B = A;
    B.translate(10 / SCALING_FACTOR, 10 / SCALING_FACTOR);

    SVG svg{std::string("one_vertex_touch") + ".svg"};
    svg.draw(A, "blue");
    svg.draw(B, "green");
    svg.Close();

    bool is_inters = Geometry::convex_polygons_intersect(A, B);

    REQUIRE(is_inters == false);
}

TEST_CASE("Convex polygon intersection on two overlapping squares", "[Geometry][Rotcalip]") {
    Polygon A{{0, 0}, {10, 0}, {10, 10}, {0, 10}};
    A.scale(1. / SCALING_FACTOR);

    Polygon B = A;

    bool is_inters = Geometry::convex_polygons_intersect(A, B);

    REQUIRE(is_inters == true);
}

//// Only for benchmarking
//static Polygon gen_convex_poly(std::mt19937_64 &rg, size_t point_cnt)
//{
//    std::uniform_int_distribution<coord_t> dist(0, 100);

//    Polygon out;
//    out.points.reserve(point_cnt);

//    coord_t tr = dist(rg) * 2 / SCALING_FACTOR;

//    for (size_t i = 0; i < point_cnt; ++i)
//        out.points.emplace_back(tr + dist(rg) / SCALING_FACTOR,
//                                tr + dist(rg) / SCALING_FACTOR);

//    return Geometry::convex_hull(out.points);
//}
//TEST_CASE("Convex polygon intersection test on random polygons", "[Geometry]") {
//    constexpr size_t TEST_CNT = 1000;
//    constexpr size_t POINT_CNT = 1000;

//    auto seed = std::random_device{}();
////    unsigned long seed = 2525634386;
//    std::mt19937_64 rg{seed};
//    Benchmark bench;

//    auto tests = reserve_vector<std::pair<Polygon, Polygon>>(TEST_CNT);
//    auto results = reserve_vector<bool>(TEST_CNT);
//    auto expects = reserve_vector<bool>(TEST_CNT);

//    for (size_t i = 0; i < TEST_CNT; ++i) {
//        tests.emplace_back(gen_convex_poly(rg, POINT_CNT), gen_convex_poly(rg, POINT_CNT));
//    }

//    bench.start();
//    for (const auto &test : tests)
//        results.emplace_back(Geometry::convex_polygons_intersect(test.first, test.second));
//    bench.stop();

//    std::cout << "Test time: " << bench.getElapsedSec() << std::endl;

//    bench.start();
//    for (const auto &test : tests)
//        expects.emplace_back(!intersection(test.first, test.second).empty());
//    bench.stop();

//    std::cout << "Clipper time: " << bench.getElapsedSec() << std::endl;

//    REQUIRE(results.size() == expects.size());

//    auto seedstr = std::to_string(seed);
//    for (size_t i = 0; i < results.size(); ++i) {
//        // std::cout << expects[i] << " ";

//        if (results[i] != expects[i]) {
//            SVG svg{std::string("fail_seed") + seedstr + "_" + std::to_string(i) + ".svg"};
//            svg.draw(tests[i].first, "blue");
//            svg.draw(tests[i].second, "green");
//            svg.Close();

//            // std::cout << std::endl;
//        }
//        REQUIRE(results[i] == expects[i]);
//    }
//    std::cout << std::endl;

//}

struct Pair
{
    size_t first, second;
    bool operator==(const Pair &b) const { return first == b.first && second == b.second; }
};

template<> struct std::hash<Pair> {
    size_t operator()(const Pair &c) const
    {
        return c.first * PRINTER_PART_POLYGONS.size() + c.second;
    }
};

TEST_CASE("Convex polygon intersection test prusa polygons", "[Geometry][Rotcalip]") {

    // Overlap of the same polygon should always be an intersection
    for (size_t i = 0; i < PRINTER_PART_POLYGONS.size(); ++i) {
        Polygon P = PRINTER_PART_POLYGONS[i];
        P = Geometry::convex_hull(P.points);
        bool res = Geometry::convex_polygons_intersect(P, P);
        if (!res) {
            SVG svg{std::string("fail_self") + std::to_string(i) + ".svg"};
            svg.draw(P, "green");
            svg.Close();
        }
        REQUIRE(res == true);
    }

    std::unordered_set<Pair> combos;
    for (size_t i = 0; i < PRINTER_PART_POLYGONS.size(); ++i) {
        for (size_t j = 0; j < PRINTER_PART_POLYGONS.size(); ++j) {
            if (i != j) {
                size_t a = std::min(i, j), b = std::max(i, j);
                combos.insert(Pair{a, b});
            }
        }
    }

    // All disjoint
    for (const auto &combo : combos) {
        Polygon A = PRINTER_PART_POLYGONS[combo.first], B = PRINTER_PART_POLYGONS[combo.second];
        A = Geometry::convex_hull(A.points);
        B = Geometry::convex_hull(B.points);

        auto bba = A.bounding_box();
        auto bbb = B.bounding_box();

        A.translate(-bba.center());
        B.translate(-bbb.center());

        B.translate(bba.size() + bbb.size());

        bool res = Geometry::convex_polygons_intersect(A, B);
        bool ref = !intersection(A, B).empty();

        if (res != ref) {
            SVG svg{std::string("fail") + std::to_string(combo.first) + "_" + std::to_string(combo.second) + ".svg"};
            svg.draw(A, "blue");
            svg.draw(B, "green");
            svg.Close();
        }

        REQUIRE(res == ref);
    }

    // All intersecting
    for (const auto &combo : combos) {
        Polygon A = PRINTER_PART_POLYGONS[combo.first], B = PRINTER_PART_POLYGONS[combo.second];
        A = Geometry::convex_hull(A.points);
        B = Geometry::convex_hull(B.points);

        auto bba = A.bounding_box();
        auto bbb = B.bounding_box();

        A.translate(-bba.center());
        B.translate(-bbb.center());

        bool res = Geometry::convex_polygons_intersect(A, B);
        bool ref = !intersection(A, B).empty();

        if (res != ref) {
            SVG svg{std::string("fail") + std::to_string(combo.first) + "_" + std::to_string(combo.second) + ".svg"};
            svg.draw(A, "blue");
            svg.draw(B, "green");
            svg.Close();
        }

        REQUIRE(res == ref);
    }
}