Infinite loop in LocatorKDTree::addPoint

[LeoPizzo1]

Ciao,

With the enclosed grid of points the kdtree insertion fails (FYI, the "old" boost::rtree was working perfectly)
CDTTessellationGrid.grid (1).txt
It runs to an infinite loop in KDTree::insert, in the while(true) loop at row 117.

To load this file you can use the visualizer modified here:
main.zip

[artem-ogre]

Ciao and thanks for the issue!

Please check the branch with the fix.
Something to be noted is that the modified main.cpp is broken, and also X, and Y ticks should be in ascending order with no duplicates.
Here are some fixes I have done to make it work for me:

void readData(const QString& file)
    {
        m_grid.clear();
        if(file.contains(".grid"))
        {
            QFile data(file);
            if(!data.open(QFile::ReadOnly))
            {
                QMessageBox::warning(
                    this, tr("CDT"), tr("Could not open file ") + file);
            }
            QTextStream inStream(&data);
            std::size_t nCols;
            inStream >> nCols;
            m_points.clear();
            m_edges.clear();
            m_grid.clear();
            m_grid.reserve(nCols);
            for(std::size_t j = 0; j < nCols; ++j)
            {
                CoordType x1, y1;
                inStream >> x1 >> y1;
                m_grid.push_back(V2d::make(x1, y1));
            }

            inStream.skipWhiteSpace();
        }
        else
        {
// ...

void updateCDT()
    {
        m_cdt = Triangulation(
            CDT::VertexInsertionOrder::AsProvided,
            CDT::IntersectingConstraintEdges::Resolve,
            1e-4);
        if(!m_grid.empty())
        {
            int nRows = m_grid.size();
            if(nRows > 0)
            {
                int nCols = m_grid.size();
                std::vector<double> X, Y;
                for(auto iCol = 0; iCol < nCols; ++iCol)
                {
                    auto pt = m_grid[iCol];
                    X.push_back(pt.x);
                    Y.push_back(pt.y);
                }
                // prepare indices
                std::sort(X.begin(), X.end());
                X.erase(std::unique(X.begin(), X.end()), X.end());
                std::sort(Y.begin(), Y.end());
                Y.erase(std::unique(Y.begin(), Y.end()), Y.end());

                CDT::initializeWithIrregularGrid(
                    X.begin(), X.end(), Y.begin(), Y.end(), m_cdt);
            }
        }
// ...

void initTransform()
    {
        if(!m_grid.empty())
            m_sceneBox = envelopBox(m_grid);
        else
            m_sceneBox = envelopBox(m_points);
// ...

[artem-ogre]

Oh, and I also changed first line in the data file from 2 125 to 250.

[LeoPizzo1]

Works perfectly! 🥇

Just a small question: do you use a local implementation of kdtree to have all the code in your library?
I actually wonder why you didn't use nanoflann (https://github.com/jlblancoc/nanoflann): maybe it would be a bit over-engineered, but at least you wouldn't have to deal with all the little problems of spatial searches.
Anyway, good idea to allow the user to provide their own NearPointLocator!

Again, thanks, it is an amazing piece of software!

[artem-ogre]

Just a small question: do you use a local implementation of kdtree to have all the code in your library? I actually wonder why you didn't use nanoflann (https://github.com/jlblancoc/nanoflann): maybe it would be a bit over-engineered, but at least you wouldn't have to deal with all the little problems of spatial searches. Anyway, good idea to allow the user to provide their own NearPointLocator!

Yes, primarily it is to minimize dependencies and to support c++98 compilation. It is also way faster than previously used Boost::RTree. Nanoflann definitely looks interesting, it would be interesting to have a PoC of another locator using nanoflann and benchmark it.

[LeoPizzo1]

If I will have some time I will do it. It could even became an optional component of your library.

Thanks again!