Bug in QuadTreeKD2

[ng-dmc]

Hello, I believe I encountered a bug in QuadTreeKD2. It's not present in QuadTreeKD or QuadTreeKD0.

reproducer (data.txt):

package bug;

import java.io.BufferedReader;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.List;

import org.tinspin.index.qthypercube.QuadTreeKD;
import org.tinspin.index.qthypercube2.QuadTreeKD2;
import org.tinspin.index.qtplain.QuadTreeKD0;

public class HelloWorld {
  public static void main(String[] args) {
    try {
      t();
    } catch (Exception e) {
    }
  }

 public static void t() throws Exception {
    BufferedReader reader = new BufferedReader(new FileReader("data.txt"));
    int n = Integer.parseInt(reader.readLine());
    QuadTreeKD2<Integer> tree = QuadTreeKD2.create(2);
    for (int i = 0; i < n; i++) {
      String[] sp = reader.readLine().split(" ");
      double d1 = Double.parseDouble(sp[0]), d2 = Double.parseDouble(sp[1]);

      tree.insert(new double[]{d1, d2}, i);
    }
    int k = Integer.parseInt(reader.readLine());
    for (int i = 0; i < k; i++) {
      String[] sp = reader.readLine().split(" ");
      double d1 = Double.parseDouble(sp[0]), d2 = Double.parseDouble(sp[1]);

      tree.remove(new double[]{d1, d2});
    }
    {
      String[] sp = reader.readLine().split(" ");
      double d1 = Double.parseDouble(sp[0]), d2 = Double.parseDouble(sp[1]);
      var node = tree.query1nn(new double[]{d1, d2});
      boolean has = tree.contains(node.point());
      System.out.println(n);

      System.out.println(has); // Should print true, but prints false with QuadTreeKD2
    }
  }
}

[tzaeschke]

Thanks for this very nice & reproducible bug report! I can reproduce this and will have a look as soon as I can.

[tzaeschke]

Analysis: this was two problems:

• remove() did not actually remove entries (i.e. set a reference to null) but only shuffled entries around and reduced an entry counter.
• kNN search did not respect the counter but searched all entries in a node's entry collection.

The combination cause kNN entries that had supposedly been deleted .

A new release 2.1.3 should be available via maven by tomorrow or so.

Thanks again for reporting this!

[ng-dmc]

Thanks for the fix, now works nicely!