SuperSlicer/tests/libslic3r/test_voronoi.cpp

#include <catch2/catch.hpp>
#include <test_utils.hpp>

#include <libslic3r/Polygon.hpp>
#include <libslic3r/Polyline.hpp>
#include <libslic3r/EdgeGrid.hpp>
#include <libslic3r/Geometry.hpp>
#include "libslic3r/Geometry/VoronoiUtilsCgal.hpp"

#include <libslic3r/Geometry/VoronoiOffset.hpp>
#include <libslic3r/Geometry/VoronoiVisualUtils.hpp>

#include <numeric>

// #define VORONOI_DEBUG_OUT

#ifdef VORONOI_DEBUG_OUT
#include <libslic3r/VoronoiVisualUtils.hpp>
#endif

using boost::polygon::voronoi_builder;
using boost::polygon::voronoi_diagram;

using namespace Slic3r;

using VD = Slic3r::VoronoiDiagram;

// https://svn.boost.org/trac10/ticket/12067
// This bug seems to be confirmed.
// Vojtech supposes that there may be no Voronoi edges produced for
// the 1st and last sweep line positions.
TEST_CASE("Voronoi missing edges - points 12067", "[Voronoi]")
{
    Points pts {
        { -10, -20 },
        {  10, -20 },
        {   5,   0 },
        {  10,  20 },
        { -10,  20 },
        {  -5,   0 }
    };

#if 0
    for (Point &p : pts) {
        Vec2d q = p.cast<double>();
        p.x() = scale_(p.x());
        p.y() = scale_(p.y());
    }
#endif

#if 0
    // Try to rotate, maybe the issue is caused by incorrect handling of vertical or horizontal edges?
    double a = 0.18764587962597876897475f;
    double c = cos(a);
    double s = sin(a);
    for (Point &p : poly.points) {
        Vec2d q = p.cast<double>();
        p.x() = coord_t(q.x() * c + q.y() * s + 0.5);
        p.y() = coord_t(- q.x() * s + q.y() * c + 0.5);
    }
#endif

    // Construction of the Voronoi Diagram.
    VD vd;
    construct_voronoi(pts.begin(), pts.end(), &vd);

#ifdef VORONOI_DEBUG_OUT
    dump_voronoi_to_svg(debug_out_path("voronoi-pts.svg").c_str(),
        vd, pts, Lines());
#endif

//    REQUIRE(closest_point.z() == Approx(1.));
}

// https://svn.boost.org/trac10/ticket/12707
// This issue is confirmed, there are no self intersections in the polygon.
// A minimal test case is created at the end of this test,
// a new issue opened with the minimal test case:
// https://github.com/boostorg/polygon/issues/43
TEST_CASE("Voronoi missing edges - Alessandro gapfill 12707", "[Voronoi]")
{
    Lines lines0 {
        { { 42127548,   699996}, { 42127548, 10135750 } },
        { { 42127548, 10135750}, { 50487352, 10135750 } },
        { { 50487352, 10135750}, { 50487352,   699995 } },
        { { 50487352,   699995}, { 51187348,        0 } },
        { { 51187348,        0}, { 64325952,        0 } },
        { { 64325952,        0}, { 64325952,   699996 } },
        { { 64325952,   699996}, { 51187348,   699996 } },
        { { 51187348,   699996}, { 51187348, 10835701 } },
        { { 51187348, 10835701}, { 41427552, 10835701 } },
        { { 41427552, 10835701}, { 41427552,   699996 } },
        { { 41427552,   699996}, { 28664848,   699996 } },
        { { 28664848,   699996}, { 28664848, 10835701 } },
        { { 28664848, 10835701}, { 19280052, 10835701 } },
        { { 19280052, 10835701}, { 27964852,   699996 } },
        { { 27964852,   699996}, { 28664848,        0 } },
        { { 28664848,        0}, { 41427551,        0 } },
        { { 41427551,        0}, { 42127548,   699996 } }
    };

    Lines lines1 {
        { { 42127548,   699996}, { 42127548, 10135750 } },
        { { 42127548, 10135750}, { 50487352, 10135750 } },
        { { 50487352, 10135750}, { 50487352,   699995 } },
        { { 50487352,   699995}, { 51187348,        0 } },
        { { 51187348,        0}, { 51187348, 10835701 } },
        { { 51187348, 10835701}, { 41427552, 10835701 } },
        { { 41427552, 10835701}, { 41427552,   699996 } },
        { { 41427552,   699996}, { 28664848,   699996 } },
        { { 28664848,   699996}, { 28664848, 10835701 } },
        { { 28664848, 10835701}, { 19280052, 10835701 } },
        { { 19280052, 10835701}, { 27964852,   699996 } },
        { { 27964852,   699996}, { 28664848,        0 } },
        { { 28664848,        0}, { 41427551,        0 } },
        { { 41427551,        0}, { 42127548,   699996 } }
    };

    Lines lines2 {
        { { 42127548,   699996}, { 42127548, 10135750 } },
        { { 42127548, 10135750}, { 50487352, 10135750 } },
        { { 50487352, 10135750}, { 50487352,   699995 } },
        { { 50487352,   699995}, { 51187348,        0 } },
        { { 51187348,        0}, { 51187348, 10835701 } },
        { { 51187348, 10835701}, { 41427552, 10835701 } },
        { { 41427552, 10835701}, { 41427552,   699996 } },
        { { 41427552,   699996}, { 28664848,   699996 } },
        { { 28664848,   699996}, { 28664848, 10835701 } },
        { { 28664848, 10835701}, { 19280052, 10835701 } },
        { { 19280052, 10835701}, { 28664848,        0 } },
        { { 28664848,        0}, { 41427551,        0 } },
        { { 41427551,        0}, { 42127548,   699996 } }
    };

    Lines lines3 {
        { { 42127548,   699996}, { 42127548, 10135750 } },
        { { 42127548, 10135750}, { 50487352, 10135750 } },
        { { 50487352, 10135750}, { 50487352,   699995 } },
        { { 50487352,   699995}, { 51187348,        0 } },
        { { 51187348,        0}, { 51187348, 10835701 } },
        { { 51187348, 10835701}, { 41427552, 10835701 } },
        { { 41427552, 10835701}, { 41427552,   699996 } },
        { { 41427552,   699996}, { 41427551,        0 } },
        { { 41427551,        0}, { 42127548,   699996 } }
    };

    Lines lines4 {
        { { 42127548,   699996}, { 42127548, 10135750 } },
        { { 42127548, 10135750}, { 50487352, 10135750 } },
        { { 50487352, 10135750}, { 50487352,   699995 } },
        { { 50487352,   699995}, { 51187348,        0 } },
        { { 51187348,        0}, { 51187348, 10835701 } },
        { { 51187348, 10835701}, { 41427552, 10835701 } },
        { { 41427552, 10835701}, { 41427551,        0 } },
        { { 41427551,        0}, { 42127548,   699996 } }
    };

    Polygon poly {
            {       0, 10000000},
            {  700000,        1}, // it has to be 1, higher number, zero or -1 work.
            {  700000,  9000000},
            { 9100000,  9000000},
            { 9100000,        0},
            {10000000, 10000000}
        };

#if 1
    // Try to rotate, maybe the issue is caused by incorrect handling of vertical or horizontal edges?
    double a = 0.18764587962597876897475f;
    double c = cos(a);
    double s = sin(a);
    for (Point &p : poly.points) {
        Vec2d q = p.cast<double>();
        p.x() = coord_t(q.x() * c + q.y() * s + 0.5);
        p.y() = coord_t(- q.x() * s + q.y() * c + 0.5);
    }
#endif

    std::mt19937 gen;
    std::uniform_int_distribution<coord_t> dist(-100, 100);
#if 0
    for (Point &p : poly.points) {
      // Wiggle the points a bit to find out whether this fixes the voronoi diagram for this particular polygon.
      p.x() = (p.x() += dist(gen));
      p.y() = (p.y() += dist(gen));
    }
#endif

    REQUIRE(intersecting_edges({ poly }).empty());

    Lines lines = to_lines(poly);
    VD vd;
    construct_voronoi(lines.begin(), lines.end(), &vd);

#ifdef VORONOI_DEBUG_OUT
    dump_voronoi_to_svg(debug_out_path("voronoi-lines.svg").c_str(),
        vd, Points(), lines);
#endif
}

TEST_CASE("Voronoi weirdness", "[Voronoi]")
{
    Polygon poly2 {
        { 0, 0 },
        { 70000000, 0 },
        { 70000000, 1300000 },
//        { 70000001, 14000000 }
        { 70700000, 14000000 }
    };

    Polygon poly5 {
        { 35058884, -25732145 },
        { 35058884, -19586070 },
        { 32753739, -20246796 },
        { 28756244, -21010725 },
        { 24657532, -21657939 },
        { 20836260, -21960233 },
        { 16115145, -22070742 },
        { 11850152, -21839761 },
        { 7646240, -21470177 },
        { 3607605, -20786940 },
        { 1280947, -20329742 },
        { -292823, -19963790 },
        { -3844469, -18809741 },
        { -7237277, -17593723 },
        { -10225900, -16143761 },
        { -13030266, -14643721 },
        { -15404294, -12977561 },
        { -17601713, -11280712 },
        { -19241930, -9435607 },
        { -20714420, -7583739 },
        { -21726144, -5664355 },
        { -22579294, -3741947 },
        { -22966684, -1786321 },
        { -23200322, 170140 },
        { -22966684, 2126602 },
        { -22579296, 4082227 },
        { -21726148, 6004637 },
        { -20714424, 7924020 },
        { -19241932, 9775888 },
        { -17601717, 11620994 },
        { -15404423, 13317749 },
        { -13030276, 14984003 },
        { -10225910, 16484042 },
        { -7237288, 17934005 },
        { -3844482, 19150025 },
        { -292841, 20304074 },
        { 1280949, 20670031 },
        { 3607587, 21127226 },
        { 7646218, 21810465 },
        { 11850128, 22180055 },
        { 16115122, 22411036 },
        { 20836263, 22300531 },
        { 24657513, 21998239 },
        { 28756227, 21351025 },
        { 32753725, 20587092 },
        { 35058893, 19926309 },
        { 35058893, 35000000 },
        { -31657232, 35000000 },
        { -31657202, -35000000 },
        { 35058881, -35000000 }
    };

    Polygon poly7 {
        { 35058884, -25732145 },
        { 35058884, -19586070 },
        { -31657202, -35000000 },
        { 35058881, -35000000 }
    };

//    coord_t shift = 35058881;
//    coord_t shift_ok = 17000000;
    coord_t shift = 35058881;
    Polygon poly {
        // <-4, 0>: bug
        // -5: ok
        // 1 - ok
        { 0 + shift, -35000000 },
        { 0 + shift, -25732145 },
        { 0 + shift, -19586070 },
        { -66716086 + shift, -35000000 }
    };

    REQUIRE(intersecting_edges({ poly }).empty());
    REQUIRE(poly.area() > 0.);

#if 0
    // Try to rotate, maybe the issue is caused by incorrect handling of vertical or horizontal edges?
    double a = 0.18764587962597876897475f;
    double c = cos(a);
    double s = sin(a);
    for (Point &p : poly.points) {
        Vec2d q = p.cast<double>();
        p.x() = coord_t(q.x() * c + q.y() * s + 0.5);
        p.y() = coord_t(- q.x() * s + q.y() * c + 0.5);
    }
#endif

    VD vd;
    Lines lines = to_lines(poly);
    construct_voronoi(lines.begin(), lines.end(), &vd);

#ifdef VORONOI_DEBUG_OUT
    dump_voronoi_to_svg(debug_out_path("voronoi-weirdness.svg").c_str(),
        vd, Points(), lines);
#endif
}

// https://svn.boost.org/trac10/ticket/12903
// division by zero reported, but this issue is most likely a non-issue, as it produces an infinity for the interval of validity
// of the floating point calculation, therefore forcing a recalculation with extended accuracy.
TEST_CASE("Voronoi division by zero 12903", "[Voronoi]")
{
    Points pts { { 1, 1 }, { 3, 1 }, { 1, 3 }, { 3, 3 },
                 { -1, 1 }, { 1, -1 }, { 5, 1 }, { 3, -1 },
                 { -1, 3 }, { 1, 5 }, { 5, 3 }, { 3, 5 } };
    {
        auto pts2 { pts };
        std::sort(pts2.begin(), pts2.end(), [](auto &l, auto &r) { return (l.x() == r.x()) ? l.y() < r.y() : l.x() < r.x(); });
        // No point removed -> no duplicate.
        REQUIRE(std::unique(pts2.begin(), pts2.end()) == pts2.end());
    }

    VD vd;
    construct_voronoi(pts.begin(), pts.end(), &vd);

#ifdef VORONOI_DEBUG_OUT
    // Scale the voronoi vertices and input points, so that the dump_voronoi_to_svg will display them correctly.
    for (auto &pt : vd.vertices()) {
        const_cast<double&>(pt.x()) = scale_(pt.x());
        const_cast<double&>(pt.y()) = scale_(pt.y());
    }
    for (auto &pt : pts)
        pt = Point::new_scale(pt.x(), pt.y());
    dump_voronoi_to_svg(debug_out_path("voronoi-div-by-zero.svg").c_str(), vd, pts, Lines());
#endif
}

// https://svn.boost.org/trac10/ticket/12139
// Funny sample from a dental industry?
// Vojtech confirms this test fails and rightly so, because the input data contain self intersections.
// This test is suppressed.
TEST_CASE("Voronoi NaN coordinates 12139", "[Voronoi][!hide][!mayfail]")
{
    Lines lines = {
        { {  260500,1564400 }, { 261040,1562960 } },
        { {  261040,1562960 }, { 260840,1561780 } },
        { {  260840,1561780 }, { 262620,1561480 } },
        { {  262620,1561480 }, { 263160,1561220 } },
        { {  263160,1561220 }, { 264100,1563259 } },
        { {  264100,1563259 }, { 262380,1566980 } },
        { {  262380,1566980 }, { 260500,1564400 } },
        { {  137520,1851640 }, { 132160,1851100 } },
        { {  132160,1851100 }, { 126460,1848779 } },
        { {  126460,1848779 }, { 123960,1847320 } },
        { {  123960,1847320 }, { 120960,1844559 } },
        { {  120960,1844559 }, { 119640,1843040 } },
        { {  119640,1843040 }, { 118320,1840900 } },
        { {  118320,1840900 }, { 117920,1838120 } },
        { {  117920,1838120 }, { 118219,1833340 } },
        { {  118219,1833340 }, { 116180,1835000 } },
        { {  116180,1835000 }, { 115999,1834820 } },
        { {  115999,1834820 }, { 114240,1836340 } },
        { {  114240,1836340 }, { 112719,1837260 } },
        { {  112719,1837260 }, { 109460,1838239 } },
        { {  109460,1838239 }, { 103639,1837480 } },
        { {  103639,1837480 }, { 99819,1835460 } },
        { {  99819,1835460 }, { 96320,1834260 } },
        { {  96320,1834260 }, { 95339,1834260 } },
        { {  95339,1834260 }, { 93660,1833720 } },
        { {  93660,1833720 }, { 90719,1833300 } },
        { {  90719,1833300 }, { 87860,1831660 } },
        { {  87860,1831660 }, { 84580,1830499 } },
        { {  84580,1830499 }, { 79780,1827419 } },
        { {  79780,1827419 }, { 76020,1824280 } },
        { {  76020,1824280 }, { 73680,1821180 } },
        { {  73680,1821180 }, { 72560,1818960 } },
        { {  72560,1818960 }, { 71699,1817719 } },
        { {  71699,1817719 }, { 70280,1814260 } },
        { {  70280,1814260 }, { 69460,1811060 } },
        { {  69460,1811060 }, { 69659,1807320 } },
        { {  69659,1807320 }, { 69640,1803300 } },
        { {  69640,1803300 }, { 69360,1799780 } },
        { {  69360,1799780 }, { 69320,1796720 } },
        { {  69320,1796720 }, { 69640,1793980 } },
        { {  69640,1793980 }, { 70160,1791780 } },
        { {  70160,1791780 }, { 72460,1784879 } },
        { {  72460,1784879 }, { 74420,1780780 } },
        { {  74420,1780780 }, { 76500,1772899 } },
        { {  76500,1772899 }, { 76760,1769359 } },
        { {  76760,1769359 }, { 76480,1766259 } },
        { {  76480,1766259 }, { 76839,1760360 } },
        { {  76839,1760360 }, { 77539,1756680 } },
        { {  77539,1756680 }, { 80540,1748140 } },
        { {  80540,1748140 }, { 84200,1742619 } },
        { {  84200,1742619 }, { 90900,1735220 } },
        { {  90900,1735220 }, { 94159,1732679 } },
        { {  94159,1732679 }, { 101259,1729559 } },
        { {  101259,1729559 }, { 107299,1727939 } },
        { {  107299,1727939 }, { 110979,1727919 } },
        { {  110979,1727919 }, { 113499,1727240 } },
        { {  113499,1727240 }, { 113619,1727359 } },
        { {  113619,1727359 }, { 114280,1727280 } },
        { {  114280,1727280 }, { 131440,1732560 } },
        { {  131440,1732560 }, { 118140,1727119 } },
        { {  118140,1727119 }, { 117120,1723759 } },
        { {  117120,1723759 }, { 113840,1720660 } },
        { {  113840,1720660 }, { 111399,1716760 } },
        { {  111399,1716760 }, { 109700,1712979 } },
        { {  109700,1712979 }, { 108879,1708400 } },
        { {  108879,1708400 }, { 108060,1696360 } },
        { {  108060,1696360 }, { 110040,1687760 } },
        { {  110040,1687760 }, { 112140,1682480 } },
        { {  112140,1682480 }, { 112540,1681780 } },
        { {  112540,1681780 }, { 115260,1678320 } },
        { {  115260,1678320 }, { 118720,1675320 } },
        { {  118720,1675320 }, { 126100,1670980 } },
        { {  126100,1670980 }, { 132400,1668080 } },
        { {  132400,1668080 }, { 136700,1667440 } },
        { {  136700,1667440 }, { 142440,1667159 } },
        { {  142440,1667159 }, { 143340,1666720 } },
        { {  143340,1666720 }, { 138679,1661319 } },
        { {  138679,1661319 }, { 137240,1657480 } },
        { {  137240,1657480 }, { 136760,1650739 } },
        { {  136760,1650739 }, { 136780,1647339 } },
        { {  136780,1647339 }, { 135940,1644280 } },
        { {  135940,1644280 }, { 136000,1640820 } },
        { {  136000,1640820 }, { 135480,1638020 } },
        { {  135480,1638020 }, { 137060,1634220 } },
        { {  137060,1634220 }, { 136320,1631340 } },
        { {  136320,1631340 }, { 134620,1629700 } },
        { {  134620,1629700 }, { 132460,1628199 } },
        { {  132460,1628199 }, { 132299,1627860 } },
        { {  132299,1627860 }, { 138360,1618020 } },
        { {  138360,1618020 }, { 142440,1611859 } },
        { {  142440,1611859 }, { 143180,1611299 } },
        { {  143180,1611299 }, { 144000,1611259 } },
        { {  144000,1611259 }, { 145960,1612540 } },
        { {  145960,1612540 }, { 146720,1613700 } },
        { {  146720,1613700 }, { 147700,1613539 } },
        { {  147700,1613539 }, { 148520,1614039 } },
        { {  148520,1614039 }, { 149840,1613740 } },
        { {  149840,1613740 }, { 150620,1614079 } },
        { {  150620,1614079 }, { 154760,1612740 } },
        { {  154760,1612740 }, { 159000,1608420 } },
        { {  159000,1608420 }, { 161120,1606780 } },
        { {  161120,1606780 }, { 164060,1605139 } },
        { {  164060,1605139 }, { 168079,1603620 } },
        { {  168079,1603620 }, { 170240,1603400 } },
        { {  170240,1603400 }, { 172400,1603499 } },
        { {  172400,1603499 }, { 194440,1613740 } },
        { {  194440,1613740 }, { 195880,1616460 } },
        { {  195880,1616460 }, { 197060,1618140 } },
        { {  197060,1618140 }, { 198039,1617860 } },
        { {  198039,1617860 }, { 198739,1618900 } },
        { {  198739,1618900 }, { 200259,1619200 } },
        { {  200259,1619200 }, { 201940,1618920 } },
        { {  201940,1618920 }, { 201700,1617139 } },
        { {  201700,1617139 }, { 203860,1618179 } },
        { {  203860,1618179 }, { 203500,1617540 } },
        { {  203500,1617540 }, { 205000,1616579 } },
        { {  205000,1616579 }, { 206780,1615020 } },
        { {  206780,1615020 }, { 210159,1614059 } },
        { {  210159,1614059 }, { 217080,1611080 } },
        { {  217080,1611080 }, { 219200,1611579 } },
        { {  219200,1611579 }, { 223219,1610980 } },
        { {  223219,1610980 }, { 224580,1610540 } },
        { {  224580,1610540 }, { 227460,1611440 } },
        { {  227460,1611440 }, { 229359,1611859 } },
        { {  229359,1611859 }, { 230620,1612580 } },
        { {  230620,1612580 }, { 232340,1614460 } },
        { {  232340,1614460 }, { 232419,1617040 } },
        { {  232419,1617040 }, { 231740,1619480 } },
        { {  231740,1619480 }, { 231880,1624899 } },
        { {  231880,1624899 }, { 231540,1625820 } },
        { {  231540,1625820 }, { 231700,1627079 } },
        { {  231700,1627079 }, { 231320,1628239 } },
        { {  231320,1628239 }, { 231420,1636080 } },
        { {  231420,1636080 }, { 231099,1637200 } },
        { {  231099,1637200 }, { 228660,1643280 } },
        { {  228660,1643280 }, { 227699,1644960 } },
        { {  227699,1644960 }, { 226080,1651140 } },
        { {  226080,1651140 }, { 225259,1653420 } },
        { {  225259,1653420 }, { 225159,1655399 } },
        { {  225159,1655399 }, { 223760,1659260 } },
        { {  223760,1659260 }, { 219860,1666360 } },
        { {  219860,1666360 }, { 219180,1667220 } },
        { {  219180,1667220 }, { 212580,1673680 } },
        { {  212580,1673680 }, { 207880,1676460 } },
        { {  207880,1676460 }, { 205560,1677560 } },
        { {  205560,1677560 }, { 199700,1678920 } },
        { {  199700,1678920 }, { 195280,1679420 } },
        { {  195280,1679420 }, { 193939,1679879 } },
        { {  193939,1679879 }, { 188780,1679440 } },
        { {  188780,1679440 }, { 188100,1679639 } },
        { {  188100,1679639 }, { 186680,1679339 } },
        { {  186680,1679339 }, { 184760,1679619 } },
        { {  184760,1679619 }, { 183520,1681440 } },
        { {  183520,1681440 }, { 183860,1682200 } },
        { {  183860,1682200 }, { 186620,1686120 } },
        { {  186620,1686120 }, { 190380,1688380 } },
        { {  190380,1688380 }, { 192780,1690739 } },
        { {  192780,1690739 }, { 195860,1694839 } },
        { {  195860,1694839 }, { 196620,1696539 } },
        { {  196620,1696539 }, { 197540,1701819 } },
        { {  197540,1701819 }, { 198939,1705699 } },
        { {  198939,1705699 }, { 198979,1711819 } },
        { {  198979,1711819 }, { 198240,1716900 } },
        { {  198240,1716900 }, { 197440,1720139 } },
        { {  197440,1720139 }, { 195340,1724639 } },
        { {  195340,1724639 }, { 194040,1726140 } },
        { {  194040,1726140 }, { 192559,1728239 } },
        { {  192559,1728239 }, { 187780,1732339 } },
        { {  187780,1732339 }, { 182519,1735520 } },
        { {  182519,1735520 }, { 181239,1736140 } },
        { {  181239,1736140 }, { 177340,1737619 } },
        { {  177340,1737619 }, { 175439,1738140 } },
        { {  175439,1738140 }, { 171380,1738880 } },
        { {  171380,1738880 }, { 167860,1739059 } },
        { {  167860,1739059 }, { 166040,1738920 } },
        { {  166040,1738920 }, { 163680,1738539 } },
        { {  163680,1738539 }, { 157660,1736859 } },
        { {  157660,1736859 }, { 154900,1735460 } },
        { {  154900,1735460 }, { 151420,1735159 } },
        { {  151420,1735159 }, { 142100,1736160 } },
        { {  142100,1736160 }, { 140880,1735920 } },
        { {  140880,1735920 }, { 142820,1736859 } },
        { {  142820,1736859 }, { 144080,1737240 } },
        { {  144080,1737240 }, { 144280,1737460 } },
        { {  144280,1737460 }, { 144239,1738120 } },
        { {  144239,1738120 }, { 144980,1739420 } },
        { {  144980,1739420 }, { 146340,1741039 } },
        { {  146340,1741039 }, { 147160,1741720 } },
        { {  147160,1741720 }, { 154260,1745800 } },
        { {  154260,1745800 }, { 156560,1746879 } },
        { {  156560,1746879 }, { 165180,1752679 } },
        { {  165180,1752679 }, { 168240,1755860 } },
        { {  168240,1755860 }, { 170940,1759260 } },
        { {  170940,1759260 }, { 173440,1762079 } },
        { {  173440,1762079 }, { 174540,1764079 } },
        { {  174540,1764079 }, { 176479,1766640 } },
        { {  176479,1766640 }, { 178900,1768960 } },
        { {  178900,1768960 }, { 180819,1772780 } },
        { {  180819,1772780 }, { 181479,1776859 } },
        { {  181479,1776859 }, { 181660,1788499 } },
        { {  181660,1788499 }, { 181460,1791740 } },
        { {  181460,1791740 }, { 181160,1792840 } },
        { {  181160,1792840 }, { 179580,1797180 } },
        { {  179580,1797180 }, { 174620,1808960 } },
        { {  174620,1808960 }, { 174100,1809839 } },
        { {  174100,1809839 }, { 171660,1812419 } },
        { {  171660,1812419 }, { 169639,1813840 } },
        { {  169639,1813840 }, { 168880,1814720 } },
        { {  168880,1814720 }, { 168960,1815980 } },
        { {  168960,1815980 }, { 169979,1819160 } },
        { {  169979,1819160 }, { 170080,1820159 } },
        { {  170080,1820159 }, { 168280,1830540 } },
        { {  168280,1830540 }, { 167580,1832200 } },
        { {  167580,1832200 }, { 165679,1835720 } },
        { {  165679,1835720 }, { 164720,1836819 } },
        { {  164720,1836819 }, { 161840,1841740 } },
        { {  161840,1841740 }, { 159880,1843519 } },
        { {  159880,1843519 }, { 158959,1844120 } },
        { {  158959,1844120 }, { 154960,1847500 } },
        { {  154960,1847500 }, { 152140,1848580 } },
        { {  152140,1848580 }, { 150440,1849520 } },
        { {  150440,1849520 }, { 144940,1850980 } },
        { {  144940,1850980 }, { 138340,1851700 } },
        { {  138340,1851700 }, { 137520,1851640 } },
        { {  606940,1873860 }, { 602860,1872460 } },
        { {  602860,1872460 }, { 600680,1871539 } },
        { {  600680,1871539 }, { 599300,1870640 } },
        { {  599300,1870640 }, { 598120,1869579 } },
        { {  598120,1869579 }, { 594680,1867180 } },
        { {  594680,1867180 }, { 589680,1861460 } },
        { {  589680,1861460 }, { 586300,1855020 } },
        { {  586300,1855020 }, { 584700,1848060 } },
        { {  584700,1848060 }, { 585199,1843499 } },
        { {  585199,1843499 }, { 584000,1842079 } },
        { {  584000,1842079 }, { 582900,1841480 } },
        { {  582900,1841480 }, { 581020,1839899 } },
        { {  581020,1839899 }, { 579440,1838040 } },
        { {  579440,1838040 }, { 577840,1834299 } },
        { {  577840,1834299 }, { 576160,1831859 } },
        { {  576160,1831859 }, { 574540,1828499 } },
        { {  574540,1828499 }, { 572140,1822860 } },
        { {  572140,1822860 }, { 570180,1815219 } },
        { {  570180,1815219 }, { 570080,1812280 } },
        { {  570080,1812280 }, { 570340,1808300 } },
        { {  570340,1808300 }, { 570160,1807119 } },
        { {  570160,1807119 }, { 570140,1804039 } },
        { {  570140,1804039 }, { 571640,1796660 } },
        { {  571640,1796660 }, { 571740,1794680 } },
        { {  571740,1794680 }, { 572279,1794039 } },
        { {  572279,1794039 }, { 575480,1788300 } },
        { {  575480,1788300 }, { 576379,1787419 } },
        { {  576379,1787419 }, { 577020,1786120 } },
        { {  577020,1786120 }, { 578000,1785100 } },
        { {  578000,1785100 }, { 579960,1783720 } },
        { {  579960,1783720 }, { 581420,1782079 } },
        { {  581420,1782079 }, { 585480,1778440 } },
        { {  585480,1778440 }, { 586680,1777079 } },
        { {  586680,1777079 }, { 590520,1774639 } },
        { {  590520,1774639 }, { 592440,1773199 } },
        { {  592440,1773199 }, { 595160,1772260 } },
        { {  595160,1772260 }, { 598079,1770920 } },
        { {  598079,1770920 }, { 601420,1769019 } },
        { {  601420,1769019 }, { 606400,1767280 } },
        { {  606400,1767280 }, { 607320,1766620 } },
        { {  607320,1766620 }, { 605760,1766460 } },
        { {  605760,1766460 }, { 604420,1766780 } },
        { {  604420,1766780 }, { 601660,1766579 } },
        { {  601660,1766579 }, { 597160,1766980 } },
        { {  597160,1766980 }, { 591420,1766720 } },
        { {  591420,1766720 }, { 585360,1765460 } },
        { {  585360,1765460 }, { 578540,1763680 } },
        { {  578540,1763680 }, { 574020,1761599 } },
        { {  574020,1761599 }, { 572520,1760560 } },
        { {  572520,1760560 }, { 570959,1759000 } },
        { {  570959,1759000 }, { 566580,1755620 } },
        { {  566580,1755620 }, { 563820,1752000 } },
        { {  563820,1752000 }, { 563140,1751380 } },
        { {  563140,1751380 }, { 560800,1747899 } },
        { {  560800,1747899 }, { 558640,1742280 } },
        { {  558640,1742280 }, { 557860,1741620 } },
        { {  557860,1741620 }, { 555820,1739099 } },
        { {  555820,1739099 }, { 553920,1737540 } },
        { {  553920,1737540 }, { 551900,1735179 } },
        { {  551900,1735179 }, { 551180,1733880 } },
        { {  551180,1733880 }, { 549540,1729559 } },
        { {  549540,1729559 }, { 548860,1720720 } },
        { {  548860,1720720 }, { 549080,1719099 } },
        { {  549080,1719099 }, { 548200,1714700 } },
        { {  548200,1714700 }, { 547560,1713860 } },
        { {  547560,1713860 }, { 544500,1711259 } },
        { {  544500,1711259 }, { 543939,1709780 } },
        { {  543939,1709780 }, { 544520,1705439 } },
        { {  544520,1705439 }, { 543520,1701519 } },
        { {  543520,1701519 }, { 543920,1699319 } },
        { {  543920,1699319 }, { 546360,1697440 } },
        { {  546360,1697440 }, { 546680,1695419 } },
        { {  546680,1695419 }, { 545600,1694180 } },
        { {  545600,1694180 }, { 543220,1692000 } },
        { {  543220,1692000 }, { 538260,1685139 } },
        { {  538260,1685139 }, { 537540,1683000 } },
        { {  537540,1683000 }, { 537020,1682220 } },
        { {  537020,1682220 }, { 535560,1675940 } },
        { {  535560,1675940 }, { 535940,1671220 } },
        { {  535940,1671220 }, { 536320,1669379 } },
        { {  536320,1669379 }, { 535420,1666400 } },
        { {  535420,1666400 }, { 533540,1664460 } },
        { {  533540,1664460 }, { 530720,1662860 } },
        { {  530720,1662860 }, { 529240,1662260 } },
        { {  529240,1662260 }, { 528780,1659160 } },
        { {  528780,1659160 }, { 528820,1653560 } },
        { {  528820,1653560 }, { 529779,1650900 } },
        { {  529779,1650900 }, { 536760,1640840 } },
        { {  536760,1640840 }, { 540360,1636120 } },
        { {  540360,1636120 }, { 541160,1635380 } },
        { {  541160,1635380 }, { 544719,1629480 } },
        { {  544719,1629480 }, { 545319,1626140 } },
        { {  545319,1626140 }, { 543560,1623740 } },
        { {  543560,1623740 }, { 539880,1620739 } },
        { {  539880,1620739 }, { 533400,1617300 } },
        { {  533400,1617300 }, { 527840,1613020 } },
        { {  527840,1613020 }, { 525200,1611579 } },
        { {  525200,1611579 }, { 524360,1610800 } },
        { {  524360,1610800 }, { 517320,1605739 } },
        { {  517320,1605739 }, { 516240,1604240 } },
        { {  516240,1604240 }, { 515220,1602000 } },
        { {  515220,1602000 }, { 514079,1594240 } },
        { {  514079,1594240 }, { 513740,1581460 } },
        { {  513740,1581460 }, { 514660,1577359 } },
        { {  514660,1577359 }, { 514660,1576380 } },
        { {  514660,1576380 }, { 514199,1575380 } },
        { {  514199,1575380 }, { 514680,1572860 } },
        { {  514680,1572860 }, { 513440,1573940 } },
        { {  513440,1573940 }, { 512399,1575580 } },
        { {  512399,1575580 }, { 511620,1576220 } },
        { {  511620,1576220 }, { 507840,1581880 } },
        { {  507840,1581880 }, { 504600,1584579 } },
        { {  504600,1584579 }, { 502440,1584599 } },
        { {  502440,1584599 }, { 499060,1584059 } },
        { {  499060,1584059 }, { 498019,1581960 } },
        { {  498019,1581960 }, { 497819,1581240 } },
        { {  497819,1581240 }, { 498019,1576039 } },
        { {  498019,1576039 }, { 497539,1574740 } },
        { {  497539,1574740 }, { 495459,1574460 } },
        { {  495459,1574460 }, { 492320,1575600 } },
        { {  492320,1575600 }, { 491040,1576360 } },
        { {  491040,1576360 }, { 490080,1575640 } },
        { {  490080,1575640 }, { 490020,1575040 } },
        { {  490020,1575040 }, { 490220,1574400 } },
        { {  490220,1574400 }, { 490819,1573440 } },
        { {  490819,1573440 }, { 492680,1568259 } },
        { {  492680,1568259 }, { 492920,1566799 } },
        { {  492920,1566799 }, { 495760,1563660 } },
        { {  495760,1563660 }, { 496100,1562139 } },
        { {  496100,1562139 }, { 497879,1560240 } },
        { {  497879,1560240 }, { 497059,1558020 } },
        { {  497059,1558020 }, { 495620,1557399 } },
        { {  495620,1557399 }, { 494800,1556839 } },
        { {  494800,1556839 }, { 493500,1555479 } },
        { {  493500,1555479 }, { 491860,1554100 } },
        { {  491860,1554100 }, { 487840,1552139 } },
        { {  487840,1552139 }, { 485900,1551720 } },
        { {  485900,1551720 }, { 483639,1555439 } },
        { {  483639,1555439 }, { 482080,1556480 } },
        { {  482080,1556480 }, { 480200,1556259 } },
        { {  480200,1556259 }, { 478519,1556259 } },
        { {  478519,1556259 }, { 474020,1554019 } },
        { {  474020,1554019 }, { 472660,1551539 } },
        { {  472660,1551539 }, { 471260,1549899 } },
        { {  471260,1549899 }, { 470459,1548020 } },
        { {  470459,1548020 }, { 469920,1545479 } },
        { {  469920,1545479 }, { 469079,1542939 } },
        { {  469079,1542939 }, { 469120,1541799 } },
        { {  469120,1541799 }, { 465840,1537139 } },
        { {  465840,1537139 }, { 463360,1539059 } },
        { {  463360,1539059 }, { 459680,1546900 } },
        { {  459680,1546900 }, { 458439,1547160 } },
        { {  458439,1547160 }, { 456480,1549319 } },
        { {  456480,1549319 }, { 454160,1551400 } },
        { {  454160,1551400 }, { 452819,1550820 } },
        { {  452819,1550820 }, { 451699,1549839 } },
        { {  451699,1549839 }, { 449620,1548440 } },
        { {  449620,1548440 }, { 449419,1548080 } },
        { {  449419,1548080 }, { 447879,1547720 } },
        { {  447879,1547720 }, { 446540,1546819 } },
        { {  446540,1546819 }, { 445720,1545640 } },
        { {  445720,1545640 }, { 444800,1545100 } },
        { {  444800,1545100 }, { 443500,1542899 } },
        { {  443500,1542899 }, { 443320,1541799 } },
        { {  443320,1541799 }, { 443519,1540220 } },
        { {  443519,1540220 }, { 445060,1537099 } },
        { {  445060,1537099 }, { 445840,1533040 } },
        { {  445840,1533040 }, { 442720,1529079 } },
        { {  442720,1529079 }, { 442479,1528360 } },
        { {  442479,1528360 }, { 436820,1529240 } },
        { {  436820,1529240 }, { 436279,1529200 } },
        { {  436279,1529200 }, { 433280,1529859 } },
        { {  433280,1529859 }, { 420220,1529899 } },
        { {  420220,1529899 }, { 414740,1528539 } },
        { {  414740,1528539 }, { 411340,1527960 } },
        { {  411340,1527960 }, { 406860,1524660 } },
        { {  406860,1524660 }, { 405379,1523080 } },
        { {  405379,1523080 }, { 403639,1520320 } },
        { {  403639,1520320 }, { 402040,1517220 } },
        { {  402040,1517220 }, { 400519,1517059 } },
        { {  400519,1517059 }, { 399180,1516720 } },
        { {  399180,1516720 }, { 395300,1515179 } },
        { {  395300,1515179 }, { 394780,1515080 } },
        { {  394780,1515080 }, { 394759,1515900 } },
        { {  394759,1515900 }, { 394339,1516579 } },
        { {  394339,1516579 }, { 393200,1516640 } },
        { {  393200,1516640 }, { 392599,1521799 } },
        { {  392599,1521799 }, { 391699,1525200 } },
        { {  391699,1525200 }, { 391040,1525600 } },
        { {  391040,1525600 }, { 390540,1526500 } },
        { {  390540,1526500 }, { 388999,1527939 } },
        { {  388999,1527939 }, { 387059,1531100 } },
        { {  387059,1531100 }, { 386540,1531440 } },
        { {  386540,1531440 }, { 382140,1531839 } },
        { {  382140,1531839 }, { 377360,1532619 } },
        { {  377360,1532619 }, { 375640,1532220 } },
        { {  375640,1532220 }, { 372580,1531019 } },
        { {  372580,1531019 }, { 371079,1529019 } },
        { {  371079,1529019 }, { 367280,1526039 } },
        { {  367280,1526039 }, { 366460,1521900 } },
        { {  366460,1521900 }, { 364320,1516400 } },
        { {  364320,1516400 }, { 363779,1515780 } },
        { {  363779,1515780 }, { 362220,1515320 } },
        { {  362220,1515320 }, { 361979,1515060 } },
        { {  361979,1515060 }, { 360820,1515739 } },
        { {  360820,1515739 }, { 353360,1518620 } },
        { {  353360,1518620 }, { 347840,1520080 } },
        { {  347840,1520080 }, { 342399,1521140 } },
        { {  342399,1521140 }, { 334899,1523380 } },
        { {  334899,1523380 }, { 333220,1523400 } },
        { {  333220,1523400 }, { 332599,1522919 } },
        { {  332599,1522919 }, { 329780,1521640 } },
        { {  329780,1521640 }, { 325360,1521220 } },
        { {  325360,1521220 }, { 319000,1520999 } },
        { {  319000,1520999 }, { 316180,1520240 } },
        { {  316180,1520240 }, { 312700,1518960 } },
        { {  312700,1518960 }, { 310520,1517679 } },
        { {  310520,1517679 }, { 309280,1517260 } },
        { {  309280,1517260 }, { 306440,1515040 } },
        { {  306440,1515040 }, { 304140,1512780 } },
        { {  304140,1512780 }, { 301640,1509720 } },
        { {  301640,1509720 }, { 301500,1509879 } },
        { {  301500,1509879 }, { 300320,1509059 } },
        { {  300320,1509059 }, { 299140,1507339 } },
        { {  299140,1507339 }, { 297340,1502659 } },
        { {  297340,1502659 }, { 298960,1508280 } },
        { {  298960,1508280 }, { 299120,1509299 } },
        { {  299120,1509299 }, { 298720,1510100 } },
        { {  298720,1510100 }, { 298420,1512240 } },
        { {  298420,1512240 }, { 297420,1514540 } },
        { {  297420,1514540 }, { 296900,1515340 } },
        { {  296900,1515340 }, { 294780,1517500 } },
        { {  294780,1517500 }, { 293040,1518380 } },
        { {  293040,1518380 }, { 289140,1521360 } },
        { {  289140,1521360 }, { 283600,1523300 } },
        { {  283600,1523300 }, { 280140,1525220 } },
        { {  280140,1525220 }, { 279620,1525679 } },
        { {  279620,1525679 }, { 274960,1527379 } },
        { {  274960,1527379 }, { 273440,1528819 } },
        { {  273440,1528819 }, { 269840,1532840 } },
        { {  269840,1532840 }, { 264800,1536240 } },
        { {  264800,1536240 }, { 261199,1540419 } },
        { {  261199,1540419 }, { 257359,1541400 } },
        { {  257359,1541400 }, { 250460,1539299 } },
        { {  250460,1539299 }, { 250240,1539400 } },
        { {  250240,1539400 }, { 249840,1540460 } },
        { {  249840,1540460 }, { 249779,1541140 } },
        { {  249779,1541140 }, { 248482,1539783 } },
        { {  248482,1539783 }, { 251320,1544120 } },
        { {  251320,1544120 }, { 252500,1548320 } },
        { {  252500,1548320 }, { 252519,1549740 } },
        { {  252519,1549740 }, { 253000,1553140 } },
        { {  253000,1553140 }, { 252920,1556539 } },
        { {  252920,1556539 }, { 253160,1556700 } },
        { {  253160,1556700 }, { 254019,1558220 } },
        { {  254019,1558220 }, { 253039,1559339 } },
        { {  253039,1559339 }, { 252300,1561920 } },
        { {  252300,1561920 }, { 251080,1565260 } },
        { {  251080,1565260 }, { 251120,1566160 } },
        { {  251120,1566160 }, { 249979,1570240 } },
        { {  249979,1570240 }, { 248799,1575380 } },
        { {  248799,1575380 }, { 247180,1579520 } },
        { {  247180,1579520 }, { 243380,1588440 } },
        { {  243380,1588440 }, { 241700,1591780 } },
        { {  241700,1591780 }, { 240280,1593080 } },
        { {  240280,1593080 }, { 231859,1598380 } },
        { {  231859,1598380 }, { 228840,1600060 } },
        { {  228840,1600060 }, { 226420,1601080 } },
        { {  226420,1601080 }, { 223620,1601940 } },
        { {  223620,1601940 }, { 220919,1603819 } },
        { {  220919,1603819 }, { 219599,1604420 } },
        { {  219599,1604420 }, { 218380,1605200 } },
        { {  218380,1605200 }, { 213219,1607260 } },
        { {  213219,1607260 }, { 210040,1607740 } },
        { {  210040,1607740 }, { 186439,1596440 } },
        { {  186439,1596440 }, { 185159,1594559 } },
        { {  185159,1594559 }, { 182239,1588300 } },
        { {  182239,1588300 }, { 181040,1585380 } },
        { {  181040,1585380 }, { 180380,1578580 } },
        { {  180380,1578580 }, { 180679,1573220 } },
        { {  180679,1573220 }, { 181220,1568539 } },
        { {  181220,1568539 }, { 181859,1565020 } },
        { {  181859,1565020 }, { 184499,1555500 } },
        { {  184499,1555500 }, { 183480,1558160 } },
        { {  183480,1558160 }, { 182600,1561700 } },
        { {  182600,1561700 }, { 171700,1554359 } },
        { {  171700,1554359 }, { 176880,1545920 } },
        { {  176880,1545920 }, { 189940,1529000 } },
        { {  189940,1529000 }, { 200040,1535759 } },
        { {  200040,1535759 }, { 207559,1531660 } },
        { {  207559,1531660 }, { 218039,1527520 } },
        { {  218039,1527520 }, { 222360,1526640 } },
        { {  222360,1526640 }, { 225439,1526440 } },
        { {  225439,1526440 }, { 231160,1527079 } },
        { {  231160,1527079 }, { 232300,1527399 } },
        { {  232300,1527399 }, { 236579,1529140 } },
        { {  236579,1529140 }, { 238139,1529120 } },
        { {  238139,1529120 }, { 238799,1529319 } },
        { {  238799,1529319 }, { 240999,1531780 } },
        { {  240999,1531780 }, { 238280,1528799 } },
        { {  238280,1528799 }, { 236900,1523840 } },
        { {  236900,1523840 }, { 236800,1522700 } },
        { {  236800,1522700 }, { 235919,1518880 } },
        { {  235919,1518880 }, { 236080,1514299 } },
        { {  236080,1514299 }, { 238260,1508380 } },
        { {  238260,1508380 }, { 240119,1505159 } },
        { {  240119,1505159 }, { 233319,1496360 } },
        { {  233319,1496360 }, { 239140,1490759 } },
        { {  239140,1490759 }, { 258760,1478080 } },
        { {  258760,1478080 }, { 263940,1484760 } },
        { {  263940,1484760 }, { 263460,1485159 } },
        { {  263460,1485159 }, { 265960,1483519 } },
        { {  265960,1483519 }, { 270380,1482020 } },
        { {  270380,1482020 }, { 272880,1481420 } },
        { {  272880,1481420 }, { 275700,1481400 } },
        { {  275700,1481400 }, { 278380,1481740 } },
        { {  278380,1481740 }, { 281220,1482979 } },
        { {  281220,1482979 }, { 284680,1484859 } },
        { {  284680,1484859 }, { 285979,1486140 } },
        { {  285979,1486140 }, { 290220,1489100 } },
        { {  290220,1489100 }, { 292680,1489520 } },
        { {  292680,1489520 }, { 293280,1490240 } },
        { {  293280,1490240 }, { 293140,1489160 } },
        { {  293140,1489160 }, { 293280,1488580 } },
        { {  293280,1488580 }, { 294100,1486980 } },
        { {  294100,1486980 }, { 294580,1484960 } },
        { {  294580,1484960 }, { 295680,1481660 } },
        { {  295680,1481660 }, { 297840,1477339 } },
        { {  297840,1477339 }, { 302240,1472280 } },
        { {  302240,1472280 }, { 307120,1469000 } },
        { {  307120,1469000 }, { 314500,1466340 } },
        { {  314500,1466340 }, { 324979,1464740 } },
        { {  324979,1464740 }, { 338999,1462059 } },
        { {  338999,1462059 }, { 345599,1461579 } },
        { {  345599,1461579 }, { 349020,1461620 } },
        { {  349020,1461620 }, { 353420,1461160 } },
        { {  353420,1461160 }, { 357000,1461500 } },
        { {  357000,1461500 }, { 359860,1461579 } },
        { {  359860,1461579 }, { 364520,1462740 } },
        { {  364520,1462740 }, { 367280,1464000 } },
        { {  367280,1464000 }, { 372020,1467560 } },
        { {  372020,1467560 }, { 373999,1469980 } },
        { {  373999,1469980 }, { 375580,1472240 } },
        { {  375580,1472240 }, { 376680,1474460 } },
        { {  376680,1474460 }, { 377259,1478620 } },
        { {  377259,1478620 }, { 379279,1480880 } },
        { {  379279,1480880 }, { 379260,1481600 } },
        { {  379260,1481600 }, { 378760,1482000 } },
        { {  378760,1482000 }, { 379300,1482040 } },
        { {  379300,1482040 }, { 380220,1482460 } },
        { {  380220,1482460 }, { 380840,1483020 } },
        { {  380840,1483020 }, { 385519,1482600 } },
        { {  385519,1482600 }, { 386019,1482320 } },
        { {  386019,1482320 }, { 386499,1481600 } },
        { {  386499,1481600 }, { 386540,1480139 } },
        { {  386540,1480139 }, { 387500,1478220 } },
        { {  387500,1478220 }, { 388280,1476100 } },
        { {  388280,1476100 }, { 390060,1473000 } },
        { {  390060,1473000 }, { 393659,1469460 } },
        { {  393659,1469460 }, { 396540,1467860 } },
        { {  396540,1467860 }, { 401260,1466040 } },
        { {  401260,1466040 }, { 406200,1465100 } },
        { {  406200,1465100 }, { 410920,1465439 } },
        { {  410920,1465439 }, { 420659,1467399 } },
        { {  420659,1467399 }, { 433500,1471480 } },
        { {  433500,1471480 }, { 441340,1473540 } },
        { {  441340,1473540 }, { 448620,1475139 } },
        { {  448620,1475139 }, { 450720,1475880 } },
        { {  450720,1475880 }, { 453299,1477059 } },
        { {  453299,1477059 }, { 456620,1478940 } },
        { {  456620,1478940 }, { 458480,1480399 } },
        { {  458480,1480399 }, { 461100,1482780 } },
        { {  461100,1482780 }, { 463820,1486519 } },
        { {  463820,1486519 }, { 464780,1488199 } },
        { {  464780,1488199 }, { 466579,1493960 } },
        { {  466579,1493960 }, { 467120,1497700 } },
        { {  467120,1497700 }, { 466999,1500280 } },
        { {  466999,1500280 }, { 467300,1502580 } },
        { {  467300,1502580 }, { 467399,1505280 } },
        { {  467399,1505280 }, { 466979,1506920 } },
        { {  466979,1506920 }, { 467920,1504780 } },
        { {  467920,1504780 }, { 468159,1505040 } },
        { {  468159,1505040 }, { 469400,1504859 } },
        { {  469400,1504859 }, { 470300,1505540 } },
        { {  470300,1505540 }, { 471240,1505200 } },
        { {  471240,1505200 }, { 471579,1504280 } },
        { {  471579,1504280 }, { 473939,1502379 } },
        { {  473939,1502379 }, { 476860,1500200 } },
        { {  476860,1500200 }, { 479800,1498620 } },
        { {  479800,1498620 }, { 480840,1498120 } },
        { {  480840,1498120 }, { 485220,1497480 } },
        { {  485220,1497480 }, { 489979,1497460 } },
        { {  489979,1497460 }, { 494899,1498700 } },
        { {  494899,1498700 }, { 500099,1501320 } },
        { {  500099,1501320 }, { 501439,1501839 } },
        { {  501439,1501839 }, { 503400,1502939 } },
        { {  503400,1502939 }, { 510760,1508340 } },
        { {  510760,1508340 }, { 513640,1510920 } },
        { {  513640,1510920 }, { 518579,1514599 } },
        { {  518579,1514599 }, { 519020,1515260 } },
        { {  519020,1515260 }, { 520700,1516480 } },
        { {  520700,1516480 }, { 524960,1521480 } },
        { {  524960,1521480 }, { 526820,1524820 } },
        { {  526820,1524820 }, { 528280,1527820 } },
        { {  528280,1527820 }, { 529120,1533120 } },
        { {  529120,1533120 }, { 528820,1537139 } },
        { {  528820,1537139 }, { 527020,1543920 } },
        { {  527020,1543920 }, { 526959,1546780 } },
        { {  526959,1546780 }, { 526420,1548060 } },
        { {  526420,1548060 }, { 527020,1547919 } },
        { {  527020,1547919 }, { 527620,1548160 } },
        { {  527620,1548160 }, { 528980,1548020 } },
        { {  528980,1548020 }, { 535180,1544980 } },
        { {  535180,1544980 }, { 540860,1542979 } },
        { {  540860,1542979 }, { 546480,1542720 } },
        { {  546480,1542720 }, { 547420,1542860 } },
        { {  547420,1542860 }, { 551800,1544140 } },
        { {  551800,1544140 }, { 558740,1547939 } },
        { {  558740,1547939 }, { 569920,1556259 } },
        { {  569920,1556259 }, { 573660,1560220 } },
        { {  573660,1560220 }, { 573040,1559500 } },
        { {  573040,1559500 }, { 574740,1559220 } },
        { {  574740,1559220 }, { 588480,1562899 } },
        { {  588480,1562899 }, { 585180,1576019 } },
        { {  585180,1576019 }, { 583440,1577979 } },
        { {  583440,1577979 }, { 584280,1582399 } },
        { {  584280,1582399 }, { 584520,1588960 } },
        { {  584520,1588960 }, { 583420,1601620 } },
        { {  583420,1601620 }, { 582840,1603880 } },
        { {  582840,1603880 }, { 579860,1611400 } },
        { {  579860,1611400 }, { 577980,1614579 } },
        { {  577980,1614579 }, { 577380,1616080 } },
        { {  577380,1616080 }, { 563800,1621579 } },
        { {  563800,1621579 }, { 561320,1622320 } },
        { {  561320,1622320 }, { 565080,1621960 } },
        { {  565080,1621960 }, { 571680,1620780 } },
        { {  571680,1620780 }, { 583260,1628340 } },
        { {  583260,1628340 }, { 583100,1630399 } },
        { {  583100,1630399 }, { 582200,1632160 } },
        { {  582200,1632160 }, { 595380,1627020 } },
        { {  595380,1627020 }, { 597400,1627320 } },
        { {  597400,1627320 }, { 602240,1628459 } },
        { {  602240,1628459 }, { 605660,1630260 } },
        { {  605660,1630260 }, { 610319,1634140 } },
        { {  610319,1634140 }, { 612340,1636319 } },
        { {  612340,1636319 }, { 614820,1638020 } },
        { {  614820,1638020 }, { 616460,1638740 } },
        { {  616460,1638740 }, { 620420,1639500 } },
        { {  620420,1639500 }, { 623000,1639280 } },
        { {  623000,1639280 }, { 624459,1639359 } },
        { {  624459,1639359 }, { 626180,1640159 } },
        { {  626180,1640159 }, { 627279,1640940 } },
        { {  627279,1640940 }, { 629980,1643759 } },
        { {  629980,1643759 }, { 632380,1648000 } },
        { {  632380,1648000 }, { 635020,1654800 } },
        { {  635020,1654800 }, { 636320,1659140 } },
        { {  636320,1659140 }, { 636680,1663620 } },
        { {  636680,1663620 }, { 636180,1665780 } },
        { {  636180,1665780 }, { 630620,1669720 } },
        { {  630620,1669720 }, { 628760,1672979 } },
        { {  628760,1672979 }, { 627540,1676859 } },
        { {  627540,1676859 }, { 627040,1680699 } },
        { {  627040,1680699 }, { 624700,1686500 } },
        { {  624700,1686500 }, { 623260,1688799 } },
        { {  623260,1688799 }, { 619620,1693799 } },
        { {  619620,1693799 }, { 621720,1694859 } },
        { {  621720,1694859 }, { 624940,1694379 } },
        { {  624940,1694379 }, { 627120,1695600 } },
        { {  627120,1695600 }, { 627740,1696120 } },
        { {  627740,1696120 }, { 631120,1697460 } },
        { {  631120,1697460 }, { 633980,1698340 } },
        { {  633980,1698340 }, { 638380,1700460 } },
        { {  638380,1700460 }, { 642660,1703300 } },
        { {  642660,1703300 }, { 643620,1704140 } },
        { {  643620,1704140 }, { 646300,1707000 } },
        { {  646300,1707000 }, { 649060,1710880 } },
        { {  649060,1710880 }, { 651160,1714879 } },
        { {  651160,1714879 }, { 651740,1716559 } },
        { {  651740,1716559 }, { 653139,1722619 } },
        { {  653139,1722619 }, { 653020,1728320 } },
        { {  653020,1728320 }, { 652719,1731420 } },
        { {  652719,1731420 }, { 651619,1736360 } },
        { {  651619,1736360 }, { 649819,1743160 } },
        { {  649819,1743160 }, { 646440,1749059 } },
        { {  646440,1749059 }, { 645219,1750399 } },
        { {  645219,1750399 }, { 643959,1752679 } },
        { {  643959,1752679 }, { 643959,1753740 } },
        { {  643959,1753740 }, { 642140,1754240 } },
        { {  642140,1754240 }, { 643760,1754099 } },
        { {  643760,1754099 }, { 644320,1754280 } },
        { {  644320,1754280 }, { 645000,1754879 } },
        { {  645000,1754879 }, { 646940,1755620 } },
        { {  646940,1755620 }, { 654779,1757820 } },
        { {  654779,1757820 }, { 661100,1761559 } },
        { {  661100,1761559 }, { 664099,1763980 } },
        { {  664099,1763980 }, { 668220,1768480 } },
        { {  668220,1768480 }, { 671920,1773640 } },
        { {  671920,1773640 }, { 674939,1779540 } },
        { {  674939,1779540 }, { 677760,1782440 } },
        { {  677760,1782440 }, { 679080,1785739 } },
        { {  679080,1785739 }, { 678780,1788100 } },
        { {  678780,1788100 }, { 678020,1791500 } },
        { {  678020,1791500 }, { 677120,1793600 } },
        { {  677120,1793600 }, { 676860,1795800 } },
        { {  676860,1795800 }, { 676440,1797320 } },
        { {  676440,1797320 }, { 676459,1798519 } },
        { {  676459,1798519 }, { 675620,1800159 } },
        { {  675620,1800159 }, { 675520,1801019 } },
        { {  675520,1801019 }, { 673360,1804899 } },
        { {  673360,1804899 }, { 672740,1807079 } },
        { {  672740,1807079 }, { 673300,1809260 } },
        { {  673300,1809260 }, { 674539,1811019 } },
        { {  674539,1811019 }, { 675499,1812020 } },
        { {  675499,1812020 }, { 677660,1817240 } },
        { {  677660,1817240 }, { 679659,1824280 } },
        { {  679659,1824280 }, { 680380,1828779 } },
        { {  680380,1828779 }, { 679519,1837999 } },
        { {  679519,1837999 }, { 677940,1844379 } },
        { {  677940,1844379 }, { 676940,1846900 } },
        { {  676940,1846900 }, { 675479,1849379 } },
        { {  675479,1849379 }, { 674000,1851200 } },
        { {  674000,1851200 }, { 671380,1853480 } },
        { {  671380,1853480 }, { 667019,1855240 } },
        { {  667019,1855240 }, { 662540,1856060 } },
        { {  662540,1856060 }, { 660960,1856599 } },
        { {  660960,1856599 }, { 656240,1857020 } },
        { {  656240,1857020 }, { 655600,1856960 } },
        { {  655600,1856960 }, { 652839,1855880 } },
        { {  652839,1855880 }, { 652019,1855840 } },
        { {  652019,1855840 }, { 651459,1855060 } },
        { {  651459,1855060 }, { 652179,1854359 } },
        { {  652179,1854359 }, { 652019,1849919 } },
        { {  652019,1849919 }, { 650620,1846920 } },
        { {  650620,1846920 }, { 647299,1844540 } },
        { {  647299,1844540 }, { 644500,1843819 } },
        { {  644500,1843819 }, { 641860,1844859 } },
        { {  641860,1844859 }, { 641059,1845340 } },
        { {  641059,1845340 }, { 638860,1845820 } },
        { {  638860,1845820 }, { 638000,1845820 } },
        { {  638000,1845820 }, { 636340,1845479 } },
        { {  636340,1845479 }, { 634980,1844800 } },
        { {  634980,1844800 }, { 632660,1842979 } },
        { {  632660,1842979 }, { 631140,1841120 } },
        { {  631140,1841120 }, { 629140,1839520 } },
        { {  629140,1839520 }, { 626640,1839540 } },
        { {  626640,1839540 }, { 624159,1840739 } },
        { {  624159,1840739 }, { 623820,1841380 } },
        { {  623820,1841380 }, { 622440,1842719 } },
        { {  622440,1842719 }, { 622100,1843680 } },
        { {  622100,1843680 }, { 623780,1846100 } },
        { {  623780,1846100 }, { 624580,1846920 } },
        { {  624580,1846920 }, { 626120,1856720 } },
        { {  626120,1856720 }, { 627440,1860000 } },
        { {  627440,1860000 }, { 628000,1864299 } },
        { {  628000,1864299 }, { 627380,1865999 } },
        { {  627380,1865999 }, { 626260,1867580 } },
        { {  626260,1867580 }, { 623660,1869520 } },
        { {  623660,1869520 }, { 618680,1872780 } },
        { {  618680,1872780 }, { 617699,1873140 } },
        { {  617699,1873140 }, { 612000,1874160 } },
        { {  612000,1874160 }, { 609840,1874220 } },
        { {  609840,1874220 }, { 606940,1873860 } },
        { {  136680,1926960 }, { 135500,1926360 } },
        { {  135500,1926360 }, { 137360,1923060 } },
        { {  137360,1923060 }, { 139500,1918559 } },
        { {  139500,1918559 }, { 140780,1913239 } },
        { {  140780,1913239 }, { 139600,1913020 } },
        { {  139600,1913020 }, { 127380,1923600 } },
        { {  127380,1923600 }, { 122800,1926059 } },
        { {  122800,1926059 }, { 118879,1927719 } },
        { {  118879,1927719 }, { 114420,1928300 } },
        { {  114420,1928300 }, { 111480,1927020 } },
        { {  111480,1927020 }, { 110619,1925399 } },
        { {  110619,1925399 }, { 109620,1924200 } },
        { {  109620,1924200 }, { 108860,1922780 } },
        { {  108860,1922780 }, { 108479,1920999 } },
        { {  108479,1920999 }, { 106600,1918080 } },
        { {  106600,1918080 }, { 106220,1917740 } },
        { {  106220,1917740 }, { 105199,1916960 } },
        { {  105199,1916960 }, { 101460,1914859 } },
        { {  101460,1914859 }, { 99480,1914379 } },
        { {  99480,1914379 }, { 97179,1913499 } },
        { {  97179,1913499 }, { 94900,1911100 } },
        { {  94900,1911100 }, { 94100,1909639 } },
        { {  94100,1909639 }, { 93379,1907740 } },
        { {  93379,1907740 }, { 93960,1898259 } },
        { {  93960,1898259 }, { 93739,1896460 } },
        { {  93739,1896460 }, { 94299,1893080 } },
        { {  94299,1893080 }, { 97240,1883440 } },
        { {  97240,1883440 }, { 99799,1879780 } },
        { {  99799,1879780 }, { 100400,1878120 } },
        { {  100400,1878120 }, { 100199,1877200 } },
        { {  100199,1877200 }, { 98940,1877460 } },
        { {  98940,1877460 }, { 96320,1878480 } },
        { {  96320,1878480 }, { 86020,1881039 } },
        { {  86020,1881039 }, { 84340,1881080 } },
        { {  84340,1881080 }, { 76780,1882600 } },
        { {  76780,1882600 }, { 74380,1883580 } },
        { {  74380,1883580 }, { 72679,1884019 } },
        { {  72679,1884019 }, { 70900,1885940 } },
        { {  70900,1885940 }, { 71240,1888340 } },
        { {  71240,1888340 }, { 72720,1889940 } },
        { {  72720,1889940 }, { 74640,1891360 } },
        { {  74640,1891360 }, { 75620,1893179 } },
        { {  75620,1893179 }, { 77140,1895340 } },
        { {  77140,1895340 }, { 81040,1899500 } },
        { {  81040,1899500 }, { 82760,1900380 } },
        { {  82760,1900380 }, { 83720,1902300 } },
        { {  83720,1902300 }, { 85459,1903700 } },
        { {  85459,1903700 }, { 86960,1905940 } },
        { {  86960,1905940 }, { 88280,1913020 } },
        { {  88280,1913020 }, { 88160,1913539 } },
        { {  88160,1913539 }, { 88020,1913860 } },
        { {  88020,1913860 }, { 86080,1915200 } },
        { {  86080,1915200 }, { 85660,1916740 } },
        { {  85660,1916740 }, { 83899,1918799 } },
        { {  83899,1918799 }, { 79360,1921160 } },
        { {  79360,1921160 }, { 76400,1923140 } },
        { {  76400,1923140 }, { 70800,1926180 } },
        { {  70800,1926180 }, { 64460,1927659 } },
        { {  64460,1927659 }, { 60880,1927820 } },
        { {  60880,1927820 }, { 55780,1925580 } },
        { {  55780,1925580 }, { 54940,1925040 } },
        { {  54940,1925040 }, { 52199,1921700 } },
        { {  52199,1921700 }, { 49680,1916579 } },
        { {  49680,1916579 }, { 48719,1914180 } },
        { {  48719,1914180 }, { 48620,1913080 } },
        { {  48620,1913080 }, { 47640,1909120 } },
        { {  47640,1909120 }, { 48280,1899319 } },
        { {  48280,1899319 }, { 49140,1895600 } },
        { {  49140,1895600 }, { 50320,1892899 } },
        { {  50320,1892899 }, { 51559,1890640 } },
        { {  51559,1890640 }, { 52140,1889960 } },
        { {  52140,1889960 }, { 54640,1887999 } },
        { {  54640,1887999 }, { 55639,1886500 } },
        { {  55639,1886500 }, { 55720,1885080 } },
        { {  55720,1885080 }, { 55439,1883220 } },
        { {  55439,1883220 }, { 54640,1882159 } },
        { {  54640,1882159 }, { 54100,1880300 } },
        { {  54100,1880300 }, { 52479,1874079 } },
        { {  52479,1874079 }, { 51700,1869000 } },
        { {  51700,1869000 }, { 51600,1865419 } },
        { {  51600,1865419 }, { 51720,1859820 } },
        { {  51720,1859820 }, { 52160,1857260 } },
        { {  52160,1857260 }, { 52539,1856120 } },
        { {  52539,1856120 }, { 57240,1845720 } },
        { {  57240,1845720 }, { 58280,1844400 } },
        { {  58280,1844400 }, { 60639,1840820 } },
        { {  60639,1840820 }, { 65580,1835540 } },
        { {  65580,1835540 }, { 68340,1833340 } },
        { {  68340,1833340 }, { 71660,1831480 } },
        { {  71660,1831480 }, { 73460,1829960 } },
        { {  73460,1829960 }, { 75200,1829319 } },
        { {  75200,1829319 }, { 77200,1828960 } },
        { {  77200,1828960 }, { 78640,1828920 } },
        { {  78640,1828920 }, { 111780,1842700 } },
        { {  111780,1842700 }, { 112800,1843480 } },
        { {  112800,1843480 }, { 113879,1844879 } },
        { {  113879,1844879 }, { 116379,1847379 } },
        { {  116379,1847379 }, { 116360,1847580 } },
        { {  116360,1847580 }, { 117100,1848799 } },
        { {  117100,1848799 }, { 120160,1851799 } },
        { {  120160,1851799 }, { 121860,1852320 } },
        { {  121860,1852320 }, { 124280,1852679 } },
        { {  124280,1852679 }, { 128920,1854659 } },
        { {  128920,1854659 }, { 130840,1856360 } },
        { {  130840,1856360 }, { 133520,1859460 } },
        { {  133520,1859460 }, { 135079,1860860 } },
        { {  135079,1860860 }, { 137280,1864440 } },
        { {  137280,1864440 }, { 142980,1872899 } },
        { {  142980,1872899 }, { 144600,1875840 } },
        { {  144600,1875840 }, { 147240,1883480 } },
        { {  147240,1883480 }, { 147460,1886539 } },
        { {  147460,1886539 }, { 147660,1886920 } },
        { {  147660,1886920 }, { 148399,1891720 } },
        { {  148399,1891720 }, { 148820,1896799 } },
        { {  148820,1896799 }, { 148399,1898880 } },
        { {  148399,1898880 }, { 148799,1899420 } },
        { {  148799,1899420 }, { 150520,1898539 } },
        { {  150520,1898539 }, { 154760,1892760 } },
        { {  154760,1892760 }, { 156580,1889240 } },
        { {  156580,1889240 }, { 156940,1888900 } },
        { {  156940,1888900 }, { 157540,1889540 } },
        { {  157540,1889540 }, { 156860,1896819 } },
        { {  156860,1896819 }, { 155639,1903940 } },
        { {  155639,1903940 }, { 153679,1908100 } },
        { {  153679,1908100 }, { 152859,1909039 } },
        { {  152859,1909039 }, { 149660,1915580 } },
        { {  149660,1915580 }, { 148000,1918600 } },
        { {  148000,1918600 }, { 141640,1926980 } },
        { {  141640,1926980 }, { 140060,1927899 } },
        { {  140060,1927899 }, { 136960,1929019 } },
        { {  136960,1929019 }, { 136680,1926960 } },
        { {  627100,1941519 }, { 625120,1940060 } },
        { {  625120,1940060 }, { 614580,1934680 } },
        { {  614580,1934680 }, { 608780,1929319 } },
        { {  608780,1929319 }, { 607400,1927679 } },
        { {  607400,1927679 }, { 606160,1925920 } },
        { {  606160,1925920 }, { 604480,1922240 } },
        { {  604480,1922240 }, { 602420,1916819 } },
        { {  602420,1916819 }, { 602279,1915260 } },
        { {  602279,1915260 }, { 602880,1907960 } },
        { {  602880,1907960 }, { 604140,1902719 } },
        { {  604140,1902719 }, { 605880,1898539 } },
        { {  605880,1898539 }, { 606640,1897399 } },
        { {  606640,1897399 }, { 609680,1894420 } },
        { {  609680,1894420 }, { 611099,1893640 } },
        { {  611099,1893640 }, { 616099,1890340 } },
        { {  616099,1890340 }, { 617520,1889160 } },
        { {  617520,1889160 }, { 620220,1885540 } },
        { {  620220,1885540 }, { 624480,1882260 } },
        { {  624480,1882260 }, { 628660,1880280 } },
        { {  628660,1880280 }, { 632520,1879659 } },
        { {  632520,1879659 }, { 637760,1879859 } },
        { {  637760,1879859 }, { 640899,1881500 } },
        { {  640899,1881500 }, { 644220,1883980 } },
        { {  644220,1883980 }, { 643900,1890860 } },
        { {  643900,1890860 }, { 643060,1894160 } },
        { {  643060,1894160 }, { 642459,1900320 } },
        { {  642459,1900320 }, { 642400,1903120 } },
        { {  642400,1903120 }, { 643819,1908519 } },
        { {  643819,1908519 }, { 644700,1912560 } },
        { {  644700,1912560 }, { 644640,1916380 } },
        { {  644640,1916380 }, { 644959,1918600 } },
        { {  644959,1918600 }, { 642540,1925620 } },
        { {  642540,1925620 }, { 642439,1926640 } },
        { {  642439,1926640 }, { 641860,1928300 } },
        { {  641860,1928300 }, { 638700,1932939 } },
        { {  638700,1932939 }, { 634820,1934200 } },
        { {  634820,1934200 }, { 631980,1936539 } },
        { {  631980,1936539 }, { 630160,1940600 } },
        { {  630160,1940600 }, { 627740,1941640 } },
        { {  627740,1941640 }, { 627400,1941660 } },
        { {  627400,1941660 }, { 627100,1941519 } }
    };

#if 0
    // Verify whether two any two non-neighbor line segments intersect. They should not, otherwise the Voronoi builder
    // is not guaranteed to succeed.
    for (size_t i = 0; i < lines.size(); ++ i)
        for (size_t j = i + 1; j < lines.size(); ++ j) {
            Point &ip1 = lines[i].a;
            Point &ip2 = lines[i].b;
            Point &jp1 = lines[j].a;
            Point &jp2 = lines[j].b;
            if (&ip1 != &jp2 && &jp1 != &ip2) {
                REQUIRE(! Slic3r::Geometry::segments_intersect(ip1, ip2, jp1, jp2));
            }
        }
#endif

    VD vd;
    construct_voronoi(lines.begin(), lines.end(), &vd);

    for (const auto& edge : vd.edges())
        if (edge.is_finite()) {
            auto v0 = edge.vertex0();
            auto v1 = edge.vertex1();
            REQUIRE((v0->x() == 0 || std::isnormal(v0->x())));
            REQUIRE((v0->y() == 0 || std::isnormal(v0->y())));
            REQUIRE((v1->x() == 0 || std::isnormal(v1->x())));
            REQUIRE((v1->y() == 0 || std::isnormal(v1->y())));
        }

#ifdef VORONOI_DEBUG_OUT
    dump_voronoi_to_svg(debug_out_path("voronoi-NaNs.svg").c_str(),
        vd, Points(), lines, Polygons(), Lines(), 0.015);
#endif
}

struct OffsetTest {
    double distance;
    size_t num_outer;
    size_t num_inner;
};

TEST_CASE("Voronoi offset", "[VoronoiOffset]")
{
  Polygons poly_with_hole = { Polygon {
        {       0, 10000000},
        {  700000,        0},
        {  700000,  9000000},
        { 9100000,  9000000},
        { 9100000,        0},
        {10000000, 10000000}
        }
  };

  double area = std::accumulate(poly_with_hole.begin(), poly_with_hole.end(), 0., [](double a, auto &poly){ return a + poly.area(); });
  REQUIRE(area > 0.);

  VD vd;
  Lines lines = to_lines(poly_with_hole);
  construct_voronoi(lines.begin(), lines.end(), &vd);

  for (const OffsetTest &ot : {
            OffsetTest { scale_(0.2), 1, 1 },
            OffsetTest { scale_(0.4), 1, 1 },
            OffsetTest { scale_(0.5), 1, 2 },
            OffsetTest { scale_(0.505), 1, 2 },
            OffsetTest { scale_(0.51), 1, 2 },
            OffsetTest { scale_(0.52), 1, 1 },
            OffsetTest { scale_(0.53), 1, 1 },
            OffsetTest { scale_(0.54), 1, 1 },
            OffsetTest { scale_(0.55), 1, 0 }
      }) {

#if 0
      Polygons offsetted_polygons_out = Slic3r::Voronoi::offset(vd, lines, ot.distance, scale_(0.005));
#ifdef VORONOI_DEBUG_OUT
      dump_voronoi_to_svg(debug_out_path("voronoi-offset-out-%lf.svg", ot.distance).c_str(),
          vd, Points(), lines, offsetted_polygons_out);
#endif
      REQUIRE(offsetted_polygons_out.size() == ot.num_outer);
#endif

      Polygons offsetted_polygons_in = Slic3r::Voronoi::offset(vd, lines, - ot.distance, scale_(0.005));
#ifdef VORONOI_DEBUG_OUT
      dump_voronoi_to_svg(debug_out_path("voronoi-offset-in-%lf.svg", ot.distance).c_str(),
          vd, Points(), lines, offsetted_polygons_in);
#endif
      REQUIRE(offsetted_polygons_in.size() == ot.num_inner);
  }
}

TEST_CASE("Voronoi offset 2", "[VoronoiOffset]")
{
    coord_t mm = coord_t(scale_(1.));
    Polygons poly = {
        Polygon {
            { 0, 0 },
            { 1, 0 },
            { 1, 1 },
            { 2, 1 },
            { 2, 0 },
            { 3, 0 },
            { 3, 2 },
            { 0, 2 }
        },
        Polygon {
            { 0, - 1 - 2 },
            { 3, - 1 - 2 },
            { 3, - 1 - 0 },
            { 2, - 1 - 0 },
            { 2, - 1 - 1 },
            { 1, - 1 - 1 },
            { 1, - 1 - 0 },
            { 0, - 1 - 0 }
        },
    };
    for (Polygon &p : poly)
        for (Point &pt : p.points)
            pt *= mm;

  double area = std::accumulate(poly.begin(), poly.end(), 0., [](double a, auto &poly){ return a + poly.area(); });
  REQUIRE(area > 0.);

  VD vd;
  Lines lines = to_lines(poly);
  construct_voronoi(lines.begin(), lines.end(), &vd);

  for (const OffsetTest &ot : {
            OffsetTest { scale_(0.2), 2, 2 },
            OffsetTest { scale_(0.4), 2, 2 },
            OffsetTest { scale_(0.45), 2, 2 },
            OffsetTest { scale_(0.48), 2, 2 },
            OffsetTest { scale_(0.5), 2, 4 },
            OffsetTest { scale_(0.505), 2, 4 },
            OffsetTest { scale_(0.7), 2, 0 },
            OffsetTest { scale_(0.8), 1, 0 }
      }) {

      Polygons offsetted_polygons_out = Slic3r::Voronoi::offset(vd, lines, ot.distance, scale_(0.005));
#ifdef VORONOI_DEBUG_OUT
      dump_voronoi_to_svg(debug_out_path("voronoi-offset2-out-%lf.svg", ot.distance).c_str(),
          vd, Points(), lines, offsetted_polygons_out);
#endif
      REQUIRE(offsetted_polygons_out.size() == ot.num_outer);

      Polygons offsetted_polygons_in = Slic3r::Voronoi::offset(vd, lines, - ot.distance, scale_(0.005));
#ifdef VORONOI_DEBUG_OUT
      dump_voronoi_to_svg(debug_out_path("voronoi-offset2-in-%lf.svg", ot.distance).c_str(),
          vd, Points(), lines, offsetted_polygons_in);
#endif
      REQUIRE(offsetted_polygons_in.size() == ot.num_inner);
  }
}

TEST_CASE("Voronoi offset 3", "[VoronoiOffset]")
{
    coord_t mm = coord_t(scale_(1.));
    Polygons poly = {
        Polygon {
            { 0, 0 },
            { 2, 0 },
            { 2, 1 },
            { 3, 1 },
            { 3, 0 },
            { 5, 0 },
            { 5, 2 },
            { 4, 2 },
            { 4, 3 },
            { 1, 3 },
            { 1, 2 },
            { 0, 2 }
        },
        Polygon {
            { 0, -1 - 2 },
            { 1, -1 - 2 },
            { 1, -1 - 3 },
            { 4, -1 - 3 },
            { 4, -1 - 2 },
            { 5, -1 - 2 },
            { 5, -1 - 0 },
            { 3, -1 - 0 },
            { 3, -1 - 1 },
            { 2, -1 - 1 },
            { 2, -1 - 0 },
            { 0, -1 - 0 }
        },
    };
    for (Polygon &p : poly) {
        REQUIRE(p.area() > 0.);
        for (Point &pt : p.points)
            pt *= mm;
    }

  VD vd;
  Lines lines = to_lines(poly);
  construct_voronoi(lines.begin(), lines.end(), &vd);  

  for (const OffsetTest &ot : {
            OffsetTest { scale_(0.2), 2, 2 },
            OffsetTest { scale_(0.4), 2, 2 },
            OffsetTest { scale_(0.49), 2, 2 },
            OffsetTest { scale_(0.5), 2, 2 },
            OffsetTest { scale_(0.51), 2, 2 },
            OffsetTest { scale_(0.56), 2, 2 },
            OffsetTest { scale_(0.6), 2, 2 },
            OffsetTest { scale_(0.7), 2, 2 },
            OffsetTest { scale_(0.8), 1, 6 },
            OffsetTest { scale_(0.9), 1, 6 },
            OffsetTest { scale_(0.99), 1, 6 },
            OffsetTest { scale_(1.0), 1, 0 },
            OffsetTest { scale_(1.01), 1, 0 },
      }) {

      Polygons offsetted_polygons_out = Slic3r::Voronoi::offset(vd, lines, ot.distance, scale_(0.005));
#ifdef VORONOI_DEBUG_OUT
      dump_voronoi_to_svg(debug_out_path("voronoi-offset3-out-%lf.svg", ot.distance).c_str(),
          vd, Points(), lines, offsetted_polygons_out);
#endif
      REQUIRE(offsetted_polygons_out.size() == ot.num_outer);

      Polygons offsetted_polygons_in = Slic3r::Voronoi::offset(vd, lines, - ot.distance, scale_(0.005));
#ifdef VORONOI_DEBUG_OUT
      dump_voronoi_to_svg(debug_out_path("voronoi-offset3-in-%lf.svg", ot.distance).c_str(),
          vd, Points(), lines, offsetted_polygons_in);
#endif
      REQUIRE(offsetted_polygons_in.size() == ot.num_inner);
  }
}

TEST_CASE("Voronoi offset with edge collapse", "[VoronoiOffset4]")
{
    Polygons poly 
    {
        // Outer contour
        {
            { 434890, -64754575 },
            { 541060, -64669076 },
            { 585647, -64583538 },
            { 576999, -64484233 },
            { 485666, -64191173 },
            { 1029323, -63646261 },
            { 1416925, -63666243 },
            { 1541532, -63643075 },
            { 1541535, -63643075 },
            { 1541535, -63643074 },
            { 1552612, -63641015 },
            { 1631609, -63568270 },
            { 1678393, -63443639 },
            { 1725519, -63219942 },
            { 1770552, -62903321 },
            { 1742544, -62755934 },
            { 1758152, -62588378 },
            { 1702289, -62474826 },
            { 1638627, -62242058 },
            { 1671281, -61938568 },
            { 1792676, -61478332 },
            { 1934894, -60760597 },
            { 2160333, -60064089 },
            { 2638183, -58972890 },
            { 2933095, -58478536 },
            { 3173586, -58159527 },
            { 3557779, -57556727 },
            { 3707088, -57158174 },
            { 3758053, -56907139 },
            { 3935932, -56278649 },
            { 4077331, -56033426 },
            { 4151386, -55768739 },
            { 4293796, -55561683 },
            { 4383089, -55387391 },
            { 4614128, -55201443 },
            { 5268755, -54333831 },
            { 5547634, -53797296 },
            { 5573864, -53639250 },
            { 5736812, -53304157 },
            { 6090973, -52066302 },
            { 6148630, -51666664 },
            { 6189511, -50974991 },
            { 6244112, -50774489 },
            { 6302489, -50761556 },
            { 6511179, -50579861 },
            { 6778128, -50398667 },
            { 6896879, -50350264 },
            { 7388259, -49913262 },
            { 7630584, -49602449 },
            { 7886846, -48987881 },
            { 7871333, -48318666 },
            { 7770349, -47841179 },
            { 7570223, -47234733 },
            { 7283115, -46705503 },
            { 6842948, -46056539 },
            { 6612732, -45760004 },
            { 6150430, -44991494 },
            { 5564326, -44168114 },
            { 5193032, -43807544 },
            { 4932097, -43489047 },
            { 3857385, -42548846 },
            { 3764745, -42081468 },
            { 3539887, -41422273 },
            { 3283048, -40803856 },
            { 3005925, -40367981 },
            { 3136185, -39834533 },
            { 3333757, -38499972 },
            { 3360660, -38183895 },
            { 3353375, -38036005 },
            { 3398808, -37582504 },
            { 3604229, -37221781 },
            { 3698079, -36962934 },
            { 4000449, -36007804 },
            { 4256811, -35016707 },
            { 4405951, -34581428 },
            { 4364534, -34178439 },
            { 4124603, -33432250 },
            { 3806159, -32765167 },
            { 3359088, -32109020 },
            { 2880790, -31317192 },
            { 1548334, -30402139 },
            { -7, -30131023 },
            { -1548347, -30402139 },
            { -2880803, -31317189 },
            { -3359100, -32109018 },
            { -3806173, -32765166 },
            { -4124617, -33432248 },
            { -4364548, -34178436 },
            { -4405966, -34581423 },
            { -4256825, -35016707 },
            { -4000461, -36007800 },
            { -3698093, -36962933 },
            { -3604243, -37221781 },
            { -3398823, -37582501 },
            { -3353390, -38036003 },
            { -3360675, -38183892 },
            { -3333772, -38499972 },
            { -3136200, -39834530 },
            { -3005940, -40367980 },
            { -3283062, -40803852 },
            { -3539902, -41422273 },
            { -3764761, -42081468 },
            { -3857402, -42548846 },
            { -4932112, -43489047 },
            { -5193047, -43807544 },
            { -5564341, -44168114 },
            { -6150446, -44991494 },
            { -6612748, -45760000 },
            { -6842965, -46056536 },
            { -7283130, -46705503 },
            { -7570238, -47234733 },
            { -7770365, -47841179 },
            { -7871349, -48318666 },
            { -7886860, -48987873 },
            { -7630599, -49602451 },
            { -7388277, -49913260 },
            { -6896896, -50350264 },
            { -6778145, -50398667 },
            { -6511196, -50579862 },
            { -6302504, -50761557 },
            { -6244127, -50774488 },
            { -6189527, -50974989 },
            { -6148648, -51666664 },
            { -6090990, -52066302 },
            { -5736829, -53304157 },
            { -5573882, -53639250 },
            { -5547651, -53797296 },
            { -5268772, -54333831 },
            { -4614145, -55201443 },
            { -4383106, -55387389 },
            { -4293814, -55561683 },
            { -4151404, -55768739 },
            { -4077350, -56033423 },
            { -3935952, -56278647 },
            { -3758072, -56907137 },
            { -3707107, -57158170 },
            { -3557796, -57556727 },
            { -3173605, -58159527 },
            { -2933113, -58478536 },
            { -2638201, -58972890 },
            { -2295003, -59738435 },
            { -2160353, -60064089 },
            { -1978487, -60596626 },
            { -1792695, -61478332 },
            { -1671298, -61938574 },
            { -1638646, -62242058 },
            { -1702306, -62474826 },
            { -1758168, -62588380 },
            { -1742563, -62755934 },
            { -1770570, -62903317 },
            { -1725537, -63219946 },
            { -1678412, -63443639 },
            { -1631627, -63568270 },
            { -1553479, -63640201 },
            { -1416944, -63666243 },
            { -998854, -63645714 },
            { -485685, -64191173 },
            { -577019, -64484225 },
            { -585667, -64583538 },
            { -541079, -64669076 },
            { -434910, -64754575 },
            { -294192, -64810609 },
            { 294172, -64810609 },
        },
        // Hole 1
        {
            { -842246, -45167428 },
            { -1473641, -45154392 },
            { -2181728, -45100161 },
            { -2804308, -44985842 },
            { -3100514, -44879269 },
            { -3836807, -44802155 },
            { -4035816, -44718913 },
            { -4167175, -44583299 },
            { -4496705, -44467674 },
            { -4486674, -44382045 },
            { -4343949, -44070577 },
            { -3740991, -43494686 },
            { -2701372, -43313358 },
            { -1493599, -43312838 },
            { -8, -43352868 },
            { 1414575, -43313336 },
            { 2701358, -43313358 },
            { 3095462, -43374735 },
            { 3740975, -43494686 },
            { 4343934, -44070583 },
            { 4486657, -44382044 },
            { 4496688, -44467670 },
            { 4167159, -44583300 },
            { 4035800, -44718913 },
            { 3836792, -44802155 },
            { 3100498, -44879269 },
            { 2804292, -44985842 },
            { 2181712, -45100161 },
            { 1473625, -45154389 },
            { 842231, -45167428 },
            { -8, -45232686 },
        },
        // Hole 2
        {
            { 1657455, -63016679 },
            { 1723196, -63056286 },
            { 1541535, -63643074 },
            { 1541532, -63643075 },
            { 1030020, -63645562 },
        }
    };


  VD vd;
  Lines lines = to_lines(poly);
  construct_voronoi(lines.begin(), lines.end(), &vd);

  for (const OffsetTest &ot : {
            OffsetTest { scale_(0.2), 2, 2 },
            OffsetTest { scale_(0.4), 2, 2 },
            OffsetTest { scale_(0.49), 2, 3 },
            OffsetTest { scale_(0.51), 2, 2 },
            OffsetTest { scale_(0.56), 2, 2 },
            OffsetTest { scale_(0.6), 2, 2 },
            OffsetTest { scale_(0.7), 2, 2 },
            OffsetTest { scale_(0.8), 2, 2 },
            OffsetTest { scale_(0.9), 2, 2 },
            OffsetTest { scale_(0.99), 1, 2 },
            OffsetTest { scale_(1.0), 1, 2 },
            OffsetTest { scale_(1.01), 1, 2 },
      }) {

      Polygons offsetted_polygons_out = Slic3r::Voronoi::offset(vd, lines, ot.distance, scale_(0.005));
#ifdef VORONOI_DEBUG_OUT
      dump_voronoi_to_svg(debug_out_path("voronoi-offset3-out-%lf.svg", ot.distance).c_str(),
          vd, Points(), lines, offsetted_polygons_out);
#endif
      REQUIRE(offsetted_polygons_out.size() == ot.num_outer);

      Polygons offsetted_polygons_in = Slic3r::Voronoi::offset(vd, lines, - ot.distance, scale_(0.005));
#ifdef VORONOI_DEBUG_OUT
      dump_voronoi_to_svg(debug_out_path("voronoi-offset3-in-%lf.svg", ot.distance).c_str(),
          vd, Points(), lines, offsetted_polygons_in);
#endif
      REQUIRE(offsetted_polygons_in.size() == ot.num_inner);
  }
}

// A sample extracted from file medallion_printable_fixed-teeth.stl from https://www.thingiverse.com/thing:1347129
// This test for offset scale_(2.9) and bigger
// triggers assert(r < std::max(d0, d1) + EPSILON) in function first_circle_segment_intersection_parameter.
TEST_CASE("Voronoi offset 5", "[VoronoiOffset5]")
{
    Polygons poly = {
        Polygon {
            {        0 , -16077501 },
            {  3015222 , -16142836 },
            {  3072642 , -16138163 },
            {  3094279 , -16105662 },
            {  3110660 , -15140728 },
            {  3157438 , -14105326 },
            {  3338367 , -11081394 },
            {  3443412 ,  -8381621 },
            {  3472489 ,  -6084497 },
            {  3445790 ,  -5962924 },
            {  3061725 ,  -6003484 },
            {  3030326 ,  -6030622 },
            {  2989343 ,  -6270378 },
            {  2903752 ,  -7368176 },
            {  2856704 ,  -7740619 },
            {  2795743 ,  -7978809 },
            {  2729231 ,  -8098866 },
            {  2666509 ,  -8131138 },
            {  2614169 ,  -8112308 },
            {  2561157 ,  -8032014 },
            {  2488290 ,  -7479351 },
            {  2453360 ,  -6911556 },
            {  2456148 ,  -6463146 },
            {  2546029 ,  -4580396 },
            {  2688181 ,  -2593262 },
            {  2717617 ,  -1700519 },
            {  2682232 ,  -1128411 },
            {  2631029 ,   -832886 },
            {  2535941 ,   -504483 },
            {  2399115 ,   -199303 },
            {  2290997 ,   -171213 },
            {   611824 ,   -132865 },
            {     6419 ,   -375849 },
            {  -611825 ,   -132865 },
            { -2377355 ,   -185241 },
            { -2420740 ,   -231171 },
            { -2535942 ,   -504484 },
            { -2631030 ,   -832887 },
            { -2684831 ,  -1150821 },
            { -2714840 ,  -1586454 },
            { -2688181 ,  -2593262 },
            { -2546030 ,  -4580396 },
            { -2456149 ,  -6463145 },
            { -2453361 ,  -6911557 },
            { -2488291 ,  -7479352 },
            { -2561159 ,  -8032018 },
            { -2614171 ,  -8112309 },
            { -2666509 ,  -8131138 },
            { -2729233 ,  -8098868 },
            { -2795744 ,  -7978809 },
            { -2856706 ,  -7740619 },
            { -2903752 ,  -7368176 },
            { -2989345 ,  -6270378 },
            { -3030327 ,  -6030622 },
            { -3061726 ,  -6003484 },
            { -3445790 ,  -5962924 },
            { -3472490 ,  -6084498 },
            { -3468804 ,  -7244095 },
            { -3399287 ,  -9714025 },
            { -3338368 , -11081395 },
            { -3141015 , -14446051 },
            { -3094280 , -16105662 },
            { -3072643 , -16138163 },
            { -3008836 , -16143225 }
        }
    };
    double area = std::accumulate(poly.begin(), poly.end(), 0., [](double a, auto &poly){ return a + poly.area(); });
    REQUIRE(area > 0.);

    VD vd;
    Lines lines = to_lines(poly);
    construct_voronoi(lines.begin(), lines.end(), &vd);

    for (const OffsetTest &ot : {
            OffsetTest { scale_(2.8), 1, 1 },
            OffsetTest { scale_(2.9), 1, 1 },
            OffsetTest { scale_(3.0), 1, 1 },
    }) {

        Polygons offsetted_polygons_out = Slic3r::Voronoi::offset(vd, lines, ot.distance, scale_(0.005));
#ifdef VORONOI_DEBUG_OUT
        dump_voronoi_to_svg(debug_out_path("voronoi-offset5-out-%lf.svg", ot.distance).c_str(),
            vd, Points(), lines, offsetted_polygons_out);
#endif
        REQUIRE(offsetted_polygons_out.size() == ot.num_outer);

        Polygons offsetted_polygons_in = Slic3r::Voronoi::offset(vd, lines, - ot.distance, scale_(0.005));
#ifdef VORONOI_DEBUG_OUT
        dump_voronoi_to_svg(debug_out_path("voronoi-offset5-in-%lf.svg", ot.distance).c_str(),
            vd, Points(), lines, offsetted_polygons_in);
#endif
        REQUIRE(offsetted_polygons_in.size() == ot.num_inner);
    }
}

TEST_CASE("Voronoi skeleton", "[VoronoiSkeleton]")
{
    coord_t mm = coord_t(scale_(1.));
    Polygons poly = {
        Polygon {
            { 0, 0 },
            { 1, 0 },
            { 1, 1 },
            { 2, 1 },
            { 2, 0 },
            { 3, 0 },
            { 3, 2 },
            { 0, 2 }
        },
        Polygon {
            { 0, - 1 - 2 },
            { 3, - 1 - 2 },
            { 3, - 1 - 0 },
            { 2, - 1 - 0 },
            { 2, - 1 - 1 },
            { 1, - 1 - 1 },
            { 1, - 1 - 0 },
            { 0, - 1 - 0 }
        },
    };
    for (Polygon &p : poly)
        for (Point &pt : p.points)
            pt *= mm;

    double area = std::accumulate(poly.begin(), poly.end(), 0., [](double a, auto &poly){ return a + poly.area(); });
    REQUIRE(area > 0.);

    VD vd;
    Lines lines = to_lines(poly);
    construct_voronoi(lines.begin(), lines.end(), &vd);
    Slic3r::Voronoi::annotate_inside_outside(vd, lines);
    Slic3r::Voronoi::annotate_inside_outside(vd, lines);
    static constexpr double threshold_alpha = M_PI / 12.; // 30 degrees
    std::vector<Vec2d> skeleton_edges = Slic3r::Voronoi::skeleton_edges_rough(vd, lines, threshold_alpha);

    REQUIRE(! skeleton_edges.empty());
}

// Simple detection with complexity N^2 if there is any point in the input polygons that doesn't have Voronoi vertex.
[[maybe_unused]] static bool has_missing_voronoi_vertices(const Polygons &polygons, const VD &vd)
{
    auto are_equal = [](const VD::vertex_type v, const Point &p) { return (Vec2d(v.x(), v.y()) - p.cast<double>()).norm() <= SCALED_EPSILON; };

    Points            poly_points = to_points(polygons);
    std::vector<bool> found_vertices(poly_points.size());
    for (const Point &point : poly_points)
        for (const auto &vertex : vd.vertices())
            if (are_equal(vertex, point)) {
                found_vertices[&point - &poly_points.front()] = true;
                break;
            }

    return std::find(found_vertices.begin(), found_vertices.end(), false) != found_vertices.end();
}

// This case is composed of one square polygon, and one of the edges is divided into two parts by a point that lies on this edge.
// In some applications, this point is unnecessary and can be removed (merge two parts to one edge). But for the case of
// multi-material segmentation, these points are necessary. In this case, Voronoi vertex for the point, which divides the edge
// into two parts. Even we add more points to the edge, and then for these points, the Voronoin vertex is also missing. An
// infinity-edge passes through the missing Voronoi vertex. Therefore, this missing Voronoi vertex and edge can be reconstructed
// using the intersection between the infinity-edge with the input polygon.
// Rotation of the polygon solves this problem.
TEST_CASE("Voronoi missing vertex 1", "[VoronoiMissingVertex1]")
{
    Polygon poly = {
        { 25000000,  25000000},
        {-25000000,  25000000},
        {-25000000, -25000000},
        {-12412500, -25000000},
//        {- 1650000, -25000000},
        { 25000000, -25000000}
    };

//    poly.rotate(PI / 6);

    REQUIRE(poly.area() > 0.);
    REQUIRE(intersecting_edges({poly}).empty());

    VD    vd;
    Lines lines = to_lines(poly);
    construct_voronoi(lines.begin(), lines.end(), &vd);
#ifdef VORONOI_DEBUG_OUT
    dump_voronoi_to_svg(debug_out_path("voronoi-missing-vertex1-out.svg").c_str(), vd, Points(), lines);
#endif

//    REQUIRE(!has_missing_voronoi_vertices({poly}, vd));
}

// This case is composed of two square polygons (contour and hole), and again one of the edges is divided into two parts by a
// point that lies on this edge, and for this point is Voronoi vertex missing. A difference between the previous and this case is
// that for this case, through the missing Voronoi vertex is passing a finite edge between two internal Voronoin vertices.
// Therefore, this missing Voronoi vertex and edge can be reconstructed using the intersection between the finite edge with the
// input polygon.
// Rotation of the polygons solves this problem.
TEST_CASE("Voronoi missing vertex 2", "[VoronoiMissingVertex2]")
{
    Polygons poly = {
        Polygon {
            { 50000000,  50000000},
            {-50000000,  50000000},
            {-50000000, -50000000},
            { 50000000, -50000000},
        },
        Polygon {
            {-45000000, -45000000},
            {-45000000,  45000000},
            { 45000000,  45000000},
            { 45000000,   8280000},
            { 45000000, -45000000},
        }
    };

//    polygons_rotate(poly, PI / 6);

    double area = std::accumulate(poly.begin(), poly.end(), 0., [](double a, auto &poly) { return a + poly.area(); });
    REQUIRE(area > 0.);
    REQUIRE(intersecting_edges(poly).empty());

    VD    vd;
    Lines lines = to_lines(poly);
    construct_voronoi(lines.begin(), lines.end(), &vd);
#ifdef VORONOI_DEBUG_OUT
    dump_voronoi_to_svg(debug_out_path("voronoi-missing-vertex2-out.svg").c_str(), vd, Points(), lines);
#endif

//    REQUIRE(!has_missing_voronoi_vertices(poly, vd));
}

// This case is composed of two polygons, and again one of the edges is divided into two parts by a point that lies on this edge,
// and for this point is Voronoi vertex missing. A difference between the previous cases and this case through the missing
// Voronoi vertex is passing finite edge between one inner Voronoi vertex and one outer Voronoi vertex.
// Rotating the polygon also help solve this problem.
TEST_CASE("Voronoi missing vertex 3", "[VoronoiMissingVertex3]")
{
    Polygons poly = {
        Polygon	{
            {-29715088, -29310899},
            {-29022573, -28618384},
            {-27771147, -27366958},
            {-28539221, -26519393},
            {-30619013, -28586348},
            {-29812018, -29407830},
        },
        Polygon	{
            {-27035112, -28071875},
            {-27367482, -27770679},
            {-28387008, -28790205},
            {-29309438, -29712635},
            {-29406319, -29809515},
            {-29032985, -30179156},
        }
    };
    double area = std::accumulate(poly.begin(), poly.end(), 0., [](double a, auto &poly){ return a + poly.area(); });
    REQUIRE(area > 0.);
    REQUIRE(intersecting_edges(poly).empty());

    //    polygons_rotate(poly, PI/180);
    //    polygons_rotate(poly, PI/6);

    VD vd;
    Lines lines = to_lines(poly);
    construct_voronoi(lines.begin(), lines.end(), &vd);
#ifdef VORONOI_DEBUG_OUT
    dump_voronoi_to_svg(debug_out_path("voronoi-missing-vertex3-out.svg").c_str(), vd, Points(), lines);
#endif

//    REQUIRE(!has_missing_voronoi_vertices(poly, vd));
}

// In this case, the Voronoi vertex (146873, -146873) is included twice.
// Also, near to those duplicate Voronoi vertices is another Voronoi vertex (146872, -146872).
// Rotating the polygon will help solve this problem, but then there arise three very close Voronoi vertices.
// Rotating of the input polygon will help solve this problem.
TEST_CASE("Duplicate Voronoi vertices", "[Voronoi]")
{
    Polygon poly = {
        { 25000000,  25000000},
        {-25000000,  25000000},
        {-25000000, -25000000},
        {   146872, -25000000},
        {  9912498, -25000000},
        { 25000000, -25000000},
        { 25000000, - 8056252},
        { 25000000, -  146873},
        { 25000000,  10790627},
    };

//    poly.rotate(PI / 6);

    REQUIRE(poly.area() > 0.);
    REQUIRE(intersecting_edges({poly}).empty());

    VD    vd;
    Lines lines = to_lines(poly);
    construct_voronoi(lines.begin(), lines.end(), &vd);
#ifdef VORONOI_DEBUG_OUT
    dump_voronoi_to_svg(debug_out_path("voronoi-duplicate-vertices-out.svg").c_str(), vd, Points(), lines);
#endif

    [[maybe_unused]] auto has_duplicate_vertices = [](const VD &vd) -> bool {
        std::vector<Vec2d> vertices;
        for (const auto &vertex : vd.vertices())
            vertices.emplace_back(Vec2d(vertex.x(), vertex.y()));

        std::sort(vertices.begin(), vertices.end(), [](const Vec2d &l, const Vec2d &r) { return l.x() < r.x() || (l.x() == r.x() && l.y() < r.y()); });
        return std::unique(vertices.begin(), vertices.end()) != vertices.end();
    };

//    REQUIRE(!has_duplicate_vertices(vd));
}

// In this case, there are three very close Voronoi vertices like in the previous test case after rotation. There is also one
// missing Voronoi vertex. One infinity-edge (after clip [(146872, -70146871), (146872, -146871)]) passes through this missing
// Voronoi vertex. This infinite edge [(146872, -70146871), (146872, -146871)] and edge [(146873, -146873), (0, 0)] are intersecting.
// They intersect probably because the three points are very close to each other, with a combination of the missing Voronoi vertex.
// Rotating of the input polygon will help solve this problem.
TEST_CASE("Intersecting Voronoi edges", "[Voronoi]")
{
    Polygon poly = {
        { 25000000,  25000000},
        {-25000000,  25000000},
        {-25000000, -25000000},
        {   146872, -25000000},
        { 25000000, -25000000},
        { 25000000, -  146873},
    };

//    poly.rotate(PI / 6);

    REQUIRE(poly.area() > 0.);
    REQUIRE(intersecting_edges({poly}).empty());

    VD    vd;
    Lines lines = to_lines(poly);
    construct_voronoi(lines.begin(), lines.end(), &vd);
#ifdef VORONOI_DEBUG_OUT
    dump_voronoi_to_svg(debug_out_path("voronoi-intersecting-edges-out.svg").c_str(), vd, Points(), lines);
#endif

    [[maybe_unused]] auto has_intersecting_edges = [](const Polygon &poly, const VD &vd) -> bool {
        BoundingBox  bbox         = get_extents(poly);
        const double bbox_dim_max = double(std::max(bbox.size().x(), bbox.size().y()));

        std::vector<Voronoi::Internal::segment_type> segments;
        for (const Line &line : to_lines(poly))
            segments.emplace_back(Voronoi::Internal::point_type(double(line.a.x()), double(line.a.y())),
                                  Voronoi::Internal::point_type(double(line.b.x()), double(line.b.y())));

        Lines edges;
        for (const auto &edge : vd.edges())
            if (edge.cell()->source_index() < edge.twin()->cell()->source_index()) {
                if (edge.is_finite()) {
                    edges.emplace_back(Point(coord_t(edge.vertex0()->x()), coord_t(edge.vertex0()->y())),
                                       Point(coord_t(edge.vertex1()->x()), coord_t(edge.vertex1()->y())));
                } else if (edge.is_infinite()) {
                    std::vector<Voronoi::Internal::point_type> samples;
                    Voronoi::Internal::clip_infinite_edge(poly.points, segments, edge, bbox_dim_max, &samples);
                    if (!samples.empty())
                        edges.emplace_back(Point(coord_t(samples[0].x()), coord_t(samples[0].y())), Point(coord_t(samples[1].x()), coord_t(samples[1].y())));
                }
            }

        Point intersect_point;
        for (auto first_it = edges.begin(); first_it != edges.end(); ++first_it)
            for (auto second_it = first_it + 1; second_it != edges.end(); ++second_it)
                if (first_it->intersection(*second_it, &intersect_point) && first_it->a != intersect_point && first_it->b != intersect_point)
                    return true;
        return false;
    };

//    REQUIRE(!has_intersecting_edges(poly, vd));
}

// In this case resulting Voronoi diagram is not planar. This case was distilled from GH issue #8474.
// Also, in GH issue #8514, a non-planar Voronoi diagram is generated for several polygons.
// Rotating the input polygon will solve this issue.
TEST_CASE("Non-planar voronoi diagram", "[VoronoiNonPlanar]")
{
    Polygon poly {
        { 5500000, -42000000},
        { 8000000, -17000000},
        { 8000000,  40000000},
        { 7500000,  40000000},
        { 7500000, -18000000},
        { 6000001, -18000000},
        { 6000000,  40000000},
        { 5500000,  40000000},
    };

//    poly.rotate(PI / 6);

    REQUIRE(poly.area() > 0.);
    REQUIRE(intersecting_edges({poly}).empty());

    VD    vd;
    Lines lines = to_lines(poly);
    construct_voronoi(lines.begin(), lines.end(), &vd);
#ifdef VORONOI_DEBUG_OUT
    dump_voronoi_to_svg(debug_out_path("voronoi-non-planar-out.svg").c_str(), vd, Points(), lines);
#endif

//    REQUIRE(Geometry::VoronoiUtilsCgal::is_voronoi_diagram_planar_intersection(vd));
}