Closed ng-dmc closed 1 month ago
@ng-dmc Thanks, I will have a look. Do you happen to have a test case?
Here it is:
package com.example;
import java.util.Arrays;
import org.tinspin.index.qthypercube2.QuadTreeKD2;
public class Main {
static void test(double[][] data) {
QuadTreeKD2<Integer> tree = QuadTreeKD2.create(2);
for (int i = 0; i < data.length; i++) {
if (data[i][3] == 0) {
tree.insert(Arrays.copyOf(data[i], 2), (int)data[i][2]);
} else {
tree.remove(Arrays.copyOf(data[i], 2), (int)data[i][2]);
}
}
}
public static void main(String[] args) {
double[][] data = new double[][] {
new double[]{-49.0949020385742, -2.05027413368225, 819588127, 0},
new double[]{-49.0949020385742, -2.05027389526367, 819588127, 0},
new double[]{-45.6938514709473, 32.9847145080566, -2056090140, 0},
new double[]{-45.6938514709473, 32.9847145080566, -2056090140, 0},
new double[]{-1.7595032453537, 112.097793579102, -267989921, 0},
new double[]{-1.75950336456299, 112.097793579102, -267989921, 0},
new double[]{45.6938438415527, 32.9847145080566, 1591613824, 0},
new double[]{45.6938438415527, 32.9847145080566, 1591613824, 0},
new double[]{49.0948944091797, -2.05027413368225, 14481734, 0},
new double[]{49.0948944091797, -2.05027389526367, 14481734, 0},
new double[]{-49.0949020385742, -2.05027413368225, 819588127, 1},
new double[]{-49.0949020385742, -2.05027389526367, 819588127, 1},
new double[]{-49.0949020385742, -2.05027413368225, 916603126, 0},
};
test(data);
}
}
@ng-dmc Thanks, excellent test!
I found at least two problems, a logical one and a precision problem.
I fill first fix the logical problem (should be easy enough) and then, in a separate patch, fix the precision problem. This may take a few days to resolve.
As a workaround I can suggest using the PH-tree instead (which doesn't have precision problems like quadtrees do).
Alternatively if you want to use the qt2 index, you could
Also, in case you are using the PH-Tree, and in case you want to store duplicate points (as in the unit test), make sure to use the PointMultiMap
version.
@ng-dmc I just merged #41 which should fix the array out of bounds issue. Feel free to try it out (from master
).
The precision problem (that I mentioned above) is tracked in #42. It will not cause any exception and I don't think it can cause any correctness problems.
Thanks! I will check it out.
I'll close the issue. Let me know if the problem occurs again.
Hi,
I believe it's possible to get OOB if
values.length == 0
here: https://github.com/tzaeschke/tinspin-indexes/blob/fc9e7fdd8ae17d8d922e11a7a16983952147394d/src/main/java/org/tinspin/index/qthypercube2/QNode.java#L116-L123 And the empty array could be created here: https://github.com/tzaeschke/tinspin-indexes/blob/fc9e7fdd8ae17d8d922e11a7a16983952147394d/src/main/java/org/tinspin/index/qthypercube2/QNode.java#L335