1. Introduction

A Quadtree is a tree data structure used to efficiently represent a two-dimensional space divided into four quadrants. It is primarily used for spatial partitioning, where it is beneficial to decompose a space into smaller parts, such as in computer graphics, image processing, and geographical information systems (GIS). Each node in a Quadtree represents a rectangular region, and it has either four children nodes (each representing a quadrant of the parent region) or no children (making it a leaf node).

2. Program Steps

1. Define a Point class to represent coordinates (x, y).

2. Define the Quadtree class with a Node inner class.

3. Implement the methods insert, query, and divide for the Quadtree.

4. Test the Quadtree with sample points.

3. Code Program

class Quadtree {

    private class Node {
        Point point;
        Node NW, NE, SW, SE;
        int x1, y1, x2, y2;

        public Node(int x1, int y1, int x2, int y2) {
            this.x1 = x1;
            this.y1 = y1;
            this.x2 = x2;
            this.y2 = y2;
        }
    }

    private Node root;

    public Quadtree(int width, int height) {
        root = new Node(0, 0, width, height);
    }

    class Point {
        int x, y;

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

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

    private Node insert(Node node, Point p) {
        if (node == null) return null;

        if (p.x < node.x1 || p.x > node.x2 || p.y < node.y1 || p.y > node.y2) return node;

        if (node.point == null && node.NW == null) {
            node.point = p;
            return node;
        }

        if (node.point != null) {
            Point existingPoint = node.point;
            node.point = null;
            divide(node);
            insert(node, existingPoint);
        }

        divide(node);
        insert(node, p);

        return node;
    }

    private void divide(Node node) {
        int xMid = (node.x1 + node.x2) / 2;
        int yMid = (node.y1 + node.y2) / 2;

        node.NW = new Node(node.x1, node.y1, xMid, yMid);
        node.NE = new Node(xMid, node.y1, node.x2, yMid);
        node.SW = new Node(node.x1, yMid, xMid, node.y2);
        node.SE = new Node(xMid, yMid, node.x2, node.y2);
    }

    public boolean query(Point p) {
        return query(root, p);
    }

    private boolean query(Node node, Point p) {
        if (node == null) return false;

        if (p.x < node.x1 || p.x > node.x2 || p.y < node.y1 || p.y > node.y2) return false;

        if (node.point != null && node.point.x == p.x && node.point.y == p.y) return true;

        return query(node.NW, p) || query(node.NE, p) || query(node.SW, p) || query(node.SE, p);
    }

    public static void main(String[] args) {
        Quadtree qt = new Quadtree(10, 10);
        Point p1 = new Quadtree(5, 5).new Point(5, 5);
        qt.insert(p1);

        Point p2 = new Quadtree(5, 5).new Point(3, 3);
        qt.insert(p2);

        System.out.println(qt.query(p1));
        System.out.println(qt.query(p2));
    }
}

Output:

true
true

4. Step By Step Explanation

1. The Quadtree class contains an inner Node class that represents a node in the quadtree. Each node contains pointers to its NW, NE, SW, and SE children, which correspond to the four quadrants. Additionally, a node may contain a Point, if it's a leaf node.

2. The Point class represents a (x, y) coordinate in the quadtree.

3. The insert method is used to add a point to the quadtree. If the point exists within the boundary of a node, the method checks if the node is a leaf. If it is, the point is added; otherwise, the node is subdivided further using the divide method.

4. The query method checks if a given point exists in the quadtree.

5. The divide method is used to subdivide a node into its four child quadrants. This is done by calculating the midpoint of the current node's boundaries and using them to define the boundaries of the four children.

6. In the main method, a quadtree is created with a boundary of