Implementing a simple quad tree for searching points within a rectangle

user_11323245 0
Viewed 58

I am trying to implement a a quad tree with the very basic functionality of inserting points and then querying it to find all points that lie within a specific rectangle.

I've referenced this for my quad tree implementation -> https://algs4.cs.princeton.edu/92search/QuadTree.java.html


import java.util.List;

public class QuadTree {
    public class Node {
        Point p;              // x- and y- coordinates
        Node NW, NE, SE, SW;   // four subtrees

        Node(Point p) {
            this.p = p;
        }
    }

    private Node root;

    public void insert(Point p){
        root = insert(root,p);
    }

    private Node insert(Node up,Point p){
        if(up == null)   return new Node(p);
        else if ( less(p.x, up.p.x) &&  less(p.y, up.p.y)) up.SW = insert(up.SW, p);
        else if ( less(p.x, up.p.x) && !less(p.y, up.p.y)) up.NW = insert(up.NW,p);
        else if (!less(p.x, up.p.x) &&  less(p.y, up.p.y)) up.SE = insert(up.SE,p);
        else if (!less(p.x, up.p.x) && !less(p.y, up.p.y)) up.NE = insert(up.NE,p);
        return up;
    }

    public void query2D(Rectangle rect, List<Node> nodeList){
        query2D(root,rect,nodeList);
    }

    private void query2D(Node n, Rectangle rect, List<Node> nodeList){
        if(n == null)   return;
        int xmin = rect.x0;
        int ymin = rect.y0;
        int xmax  = rect.x1;
        int ymax = rect.y1;

        if(rect.contains(n.p))    {nodeList.add(n);} //return n;}
        if ( less(xmin, n.p.x) &&  less(ymin, n.p.y))  query2D(n.SW, rect, nodeList);
        if ( less(xmin, n.p.x) && !less(ymax, n.p.y))  query2D(n.NW, rect, nodeList);
        if (!less(xmax, n.p.x) &&  less(ymin, n.p.y))  query2D(n.SE, rect, nodeList);
        else  query2D(n.NE, rect, nodeList);
    }
    private boolean less(int k1, int k2) {
        return k1 <= k2;
    }
}

Point class :-

public class Point {

     final int x;       // made final so that user provided input is immutable.
     final int y;

    public Point(int x, int y){
        this.x = x;
        this.y = y;
    }
}

Here is the test code :-

        Rectangle rect = new Rectangle(-3,7, -10, 10);
        QuadTree qTree = new QuadTree();
        for(Point p : pointList) {
            qTree.insert(p);
        }

        List<QuadTree.Node> nodeList = new ArrayList<>();
        qTree.query2D(rect,nodeList);

        StringBuilder ans = new StringBuilder();
        for(QuadTree.Node n : nodeList){
            ans.append(n.p.x);
            ans.append(n.p.y);
        }

        return ans.toString();

The pointList contains : -11;10;0;0;1;2; as (x,y) pairs. So ideally my output should be (0,0) ans (1,2) but I'm only getting (0,0). Could it be an error in how I'm storing the results of my recusrison ? That only one result gets stored?

Would appreciate any help here.

computational-geometry quadtree data-structures geometry java
1 Answers

on query 2D, you have used an else statement instead of an if statement. and in the case you don't use an if statement, if the node or the south east segment is contained in the rectangle, it won't search inside the north east segment. and if the south east segment is not contained in the search rectangle it will always search in the north east segment even if it is not contained inside of it.

basically use this query2D function:

private void query2D(Node n, Rectangle rect, List<Node> nodeList){
    if(n == null)   return;
    int xmin = rect.x0;
    int ymin = rect.y0;
    int xmax  = rect.x1;
    int ymax = rect.y1;

    if(rect.contains(n.p))    {nodeList.add(n);} //return n;}
    if ( less(xmin, n.p.x) &&  less(ymin, n.p.y))  query2D(n.SW, rect, nodeList);
    if ( less(xmin, n.p.x) && !less(ymax, n.p.y))  query2D(n.NW, rect, nodeList);
    if (!less(xmax, n.p.x) &&  less(ymin, n.p.y))  query2D(n.SE, rect, nodeList);
    if (!less(xmax, n.p.x) &&  !less(ymin, n.p.y))  query2D(n.NE, rect, nodeList);
}

instead of the one you have implemented and while i'm not sure it will remove your bug (i have not tried this yet), it should at least remove potential other bugs you would have in your implementation.

edit: By the way, what you have implemented and what has been implemented in your example isn't a QuadTree per see but a strange mix between a KDTree and a QuadTree in the sense that the center of the nodes of your tree is determined by the data they store like in a KDTree but you still have 4 nodes inside each nodes partitioned depending on their position compared to the center of the node, like in a QuadTree. However, I have failed to find a name for this data structure.

user_98484840
Related