Rounding errors (points near the mask borders). #10
Description
The bug shows when a point lies close to the mask's border.
In the following code I just move a mask so its border get closer and closer to the only point located at px,py. (Notice that the point is located in the NE corner of the mask, but the same error shows if it lies close to a border side, like so:x,y = px+dx-error_test,py or: x,y = px,py+dy-error_test.)
from smartquadtree import Quadtree
quad_tree = Quadtree(0, 0, 100, 20)
px,py = 50,10
quad_tree.insert((px,py))
dx, dy = 5,1
for error_test in [.01, .001, .0001, 0.00001]:
x,y = px+dx-error_test,py+dy-error_test
sw = (x-dx, y-dy)
nw = (x-dx, y+dy)
ne = (x+dx, y+dy)
se = (x+dx, y-dy)
quad_tree.set_mask([sw,nw,ne,se])
print("Error test={} , Qtree={}".format(error_test,quad_tree))Which outputs:
$: python3 test.py
Error test=0.01 , Qtree=<smartquadtree.Quadtree at 0x7fc23d040910>
Total number of elements: 1
Total number of elements inside mask: 1
First elements inside the mask:
(50, 10),
Error test=0.001 , Qtree=<smartquadtree.Quadtree at 0x7fc23d040910>
Total number of elements: 1
Total number of elements inside mask: 1
First elements inside the mask:
(50, 10),
Error test=0.0001 , Qtree=<smartquadtree.Quadtree at 0x7fc23d040910>
Total number of elements: 1
Total number of elements inside mask: 1
First elements inside the mask:
(50, 10),
Error test=1e-05 , Qtree=<smartquadtree.Quadtree at 0x7fc23d040910>
Total number of elements: 1
Total number of elements inside mask:
$: ...The rounding error obviously keep going on for smaller distances to the border of the mask.
This is a real problem when the mask itself is small because all values can potentially lie outside of it.
Is there a way to increase precision and what would be complexity cost for it? (I tried to increase the depth, but it seems to have no effect.)
PS I guess you know it, but this is all a question of proportions, so if the area is smaller, the error shows for smaller values:
quad_tree = Quadtree(0, 0, 1, 2)
px,py = .5,.1
quad_tree.insert((px,py))
dx, dy = .05,.01
for error_test in [.01, .001, .0001, 0.00001, 0.000001, 0.0000001]:
...Outputs:
$: python3 test.py
...
Error test=1e-05 , Qtree=<smartquadtree.Quadtree at 0x7f9ebc518150>
Total number of elements: 1
Total number of elements inside mask: 1
First elements inside the mask:
(0.5, 0.1),
Error test=1e-06 , Qtree=<smartquadtree.Quadtree at 0x7f9ebc518150>
Total number of elements: 1
Total number of elements inside mask: 1
First elements inside the mask:
(0.5, 0.1),
Error test=1e-07 , Qtree=<smartquadtree.Quadtree at 0x7f9ebc518150>
Total number of elements: 1
Total number of elements inside mask:
$: ...The largest side of the are fixes the precision, ie., if you change only its width, the error shows up at the same moment as with the 1st version.