Rtree and R*tree return inconsistent results

[racc]

Hi there. I've been looking for a Thread safe RTree implementation and yours is the only one I could find. However when I tried to use it in my software it failed to work. Upon further investigation I've found the R tree and R*tree appear to return inconsistent results.
Here is my test code:

import java.util.HashSet;

import java.util.Set;

import java.util.UUID;

import rx.Observable;

import com.github.davidmoten.rtree.Entry;

import com.github.davidmoten.rtree.RTree;

import com.github.davidmoten.rtree.geometry.Point;

import com.github.davidmoten.rtree.geometry.Rectangle;

public class RTreeTest {

   public static void main(String[] args) {

          RTree<UUID> tree1 = RTree.create();

          RTree<UUID> tree2 = RTree.star().create();



          Rectangle[] testRects = {

                 Rectangle.create(0, 0, 0, 0),

                 Rectangle.create(0, 0, 100, 100),

                 Rectangle.create(0, 0, 10, 10),

                 Rectangle.create(0.12, 0.25, 50.356, 50.756),

                 Rectangle.create(1, 0.252, 50, 69.23),

                 Rectangle.create(13.12, 23.123, 50.45, 80.9),

                 Rectangle.create(10, 10, 50, 50)

          };



          for (int i = 0 ; i < 50000 ; i++) {

                 Point point = nextPoint();

                 UUID randomUUID = UUID.randomUUID();

                 tree1 = tree1.add(randomUUID, point);

                 tree2 = tree2.add(randomUUID, point);

          }



          for (Rectangle r : testRects) {

                 Set<UUID> res1 = new HashSet<>();

                 Set<UUID> res2 = new HashSet<>();

                 Observable<Entry<UUID>> search1 = tree1.search(r);

                 Observable<Entry<UUID>> search2 = tree2.search(r);



                 search1.toBlocking().toIterable().forEach(u -> res1.add(u.value()));

                 search2.toBlocking().toIterable().forEach(u -> res2.add(u.value()));



                 System.out.println(r);

                 System.out.println(res1.size());

                 System.out.println(res2.size());

                 System.out.println("Trees found equal sets of stuff? " + res1.equals(res2) + "\n");

          }

   }



   private static Point nextPoint() {

          double randomX = Math.random() * 100;

          double randomY = Math.random() * 100;

          return Point.create(randomX, randomY);

   }

}

The trees should return the same set of Uuids for each test search area, but they don't on a typical run.
What am I doing wrong?

[davidmoten]

Thanks very much, I'll look at it in the next few hours

[davidmoten]

Thank you very much for your report. The cause was the Rectangle.intersects(Rectangle) method was wrong! Very embarrassing. I'll release fix in a few hours.

[davidmoten]

In addition to Rectangle unit tests I've also added a simplification of your code as a unit test adding 100,000 items to standard rtree and star rtree and checking search returns the same number of item for each of the search rectangles you specified.

[racc]

That's great David. Thanks for the prompt response. I look forward to testing it out in the new release. I will let you know if there are any issues.

[davidmoten]

0.4 is on maven central, cheers.