ryanmpelletier / java-simple-quadtree

A quadtree written in Java. Supports insert, update, search, remove, and more! Plenty of unit tests and also a performance report to compare with a brute force method.
https://ryanp102694.github.io/java-simple-quadtree/
MIT License
8 stars 3 forks source link

Latitude and Longitude data #4

Open DanyaAlfageh opened 3 years ago

DanyaAlfageh commented 3 years ago

I am using this quadtree to read spatial data of Latitude and Longitude and they are not being inserted in the tree even though I changed values from int to double for x,y, w and h This is my data

-73.807029724121094,40.699657440185547

and this is my test query data

-74.98451232910156 35.04014587402344 -73.97936248779295 41.49399566650391
-74.98451232910156 35.04014587402344 -73.97936248779295 41.49399566650391

When I run PerformanceReport I get 'Queried 0 items in 0 milliseconds for the following loop'


        try {
            List<String> lines = Files.readAllLines(Paths.get("searchareas"));

            /**
             * I am going to create a bunch of SearchRectangleObjects now so that I don't need to later.
             * I don't want it to affect the query time.
             */
            SearchRectangleObject[] searchRectangleObjects = new SearchRectangleObject[lines.size()];
            for(int i = 0; i < lines.size(); i++){
                searchRectangleObjects[i] = new SearchRectangleObject(Double.parseDouble(lines.get(i).split(" ")[0]), Double.parseDouble(lines.get(i).split(" ")[1]), 
                        Double.parseDouble(lines.get(i).split(" ")[2]), Double.parseDouble(lines.get(i).split(" ")[3]));
            }

            for(int i = 0; i < searchRectangleObjects.length; i++){
                long quadTreeSearchStartTime = System.currentTimeMillis();
                List<RectangleObject> itemsFromQuadTree = quadTree.search(searchRectangleObjects[i]);
                long now = System.currentTimeMillis();
                long quadTreeQueryTime = now - quadTreeSearchStartTime;
                quadTreeTotalQueryTime = quadTreeTotalQueryTime + quadTreeQueryTime;
                quadTreeMaxQueryTime = Math.max(quadTreeMaxQueryTime, quadTreeQueryTime);

                quadTreeTotalObjectsQueriedFor = quadTreeTotalObjectsQueriedFor + itemsFromQuadTree.size();

                System.out.println(String.format("Queried %s items in %s milliseconds", itemsFromQuadTree.size(), quadTreeQueryTime));
            }
            System.out.println("***** QuadTree Performance Summary *****");
            System.out.println("Total Queries Run: " + searchRectangleObjects.length);
            System.out.println("Total Objects Queried For: " + quadTreeTotalObjectsQueriedFor);
            System.out.println("Total Query Time: " + quadTreeTotalQueryTime);
            System.out.println("Max Query Time: " + quadTreeMaxQueryTime);
            System.out.println("Average Query Time: " + ((float) quadTreeTotalQueryTime / (float) searchRectangleObjects.length));
            System.out.println("\n");

        }catch(IOException e) {
            e.printStackTrace();
            }

This is the output:

Queried 0 items in 0 milliseconds
Queried 0 items in 0 milliseconds
Queried 0 items in 0 milliseconds
Queried 0 items in 0 milliseconds
Queried 0 items in 0 milliseconds
Queried 0 items in 0 milliseconds
Queried 0 items in 0 milliseconds
Queried 0 items in 0 milliseconds
Queried 0 items in 0 milliseconds
Queried 0 items in 0 milliseconds
Queried 0 items in 0 milliseconds
Queried 0 items in 0 milliseconds
Queried 0 items in 0 milliseconds
Queried 0 items in 0 milliseconds
Queried 0 items in 0 milliseconds
Queried 0 items in 0 milliseconds
Queried 0 items in 0 milliseconds
Queried 0 items in 0 milliseconds
Queried 0 items in 0 milliseconds
Queried 0 items in 0 milliseconds
***** QuadTree Performance Summary *****
Total Queries Run: 10000
Total Objects Queried For: 1610698
Total Query Time: 9341
Max Query Time: 205
Average Query Time: 0.9341
ryanmpelletier commented 3 years ago

Hey DanyaAlfageh, glad to see you using this! One of my biggest regrets was using int instead of double for the dimensions!

I will have to look at it more closely later, but it looks like the query area you are giving is just a line? I think you'll need to make it a rectangular shape that completely overlaps the object you are querying for. I don't think that just a line will pick up anything even though it may overlap with an item in the tree.