tsearch: Point not inserted

[Jean-Romain]

Reproducible example given by email:

library(geometry)
source("dumpdata.txt")
D = delaunayn(cbind(x,y))
tsearch(x,y,D,x1,y1)
#> Error in C_tsearch(x, y, t, xi, yi, bary): Failed to insert point into QuadTree.
#> Please post input to tsearch  (or tsearchn at
#> https://github.com/davidcsterratt/geometry/issues
#> or email the maintainer.

🔖 dumpdata.txt

[Jean-Romain]

As expected it is a problem of computer precision. At the level 6 the quadrants are no longer aligned with the main bounding box of the quadtree because of the successive division by 2. There is nothing to do but increasing the default epsilon to 1.0e-10. I think epsilon should be a parameter modifiable by the user.

geometry/pkg/src/Rtsearch.cpp

Line 59 in 192fc01

SEXP C_tsearch(NumericVector x, NumericVector y, IntegerMatrix elem, NumericVector xi, NumericVector yi, bool bary = false, double eps = 1.0e-12)

Another option is to expend a bit the bounding box of the quadtree. This also fix this issue without changing epsilon but I can't swear we won't have potential computer precision issues in other quadrants.

geometry/pkg/src/QuadTree.cpp

Line 101 in 192fc01

double range = xrange > yrange ? xrange/2 : yrange/2;

Add L202

range *= 1.01;

[Toby-Stegman-cbec]

Greetings,

I have run into this same issue ("Failed to insert point into QuadTree."), and have tried to edit Rtsearch.cpp function as stated above and reinstall the package to no avail. If I use the "orig" method in place of the "quadtree" method the function appears to work very well. I will try and work up a smaller example dataset to share. The code as it stands would need some simplification to share.

Thanks for all your work on this!