JavaGeom: geometry with Java

Range search with kd-tree Demo

The use of a kd-tree can accelerate the range search of a set of points located in a given rectangular area.

Source code

The source code used for generating the above figure is given below.

package math.geom2d.point;

import java.awt.*;
import java.util.ArrayList;

import javax.swing.*;

import math.geom2d.*;
import math.geom2d.line.LineSegment2D;

/**
 * Demo of range search using a kd-tree in 2 dimensions.
 */
public class RangeSearchKDTree2DRandomDemo extends JPanel{

	private static final long serialVersionUID = 1L;
	
	private final static int nbPoints = 500;
	
	ArrayList<Point2D> points;
	KDTree2D tree;
	Box2D range;
	
	public RangeSearchKDTree2DRandomDemo() {
		super();
		
		// Point coordinate are multiplied by 10 for better drawing
		points = new ArrayList<Point2D>(nbPoints);
		for(int i=0; i<nbPoints; i++){
		    points.add(new Point2D(
		            Math.random()*300+50,
		            Math.random()*300+50));
		}
		
		tree = new KDTree2D(points);
		
		range = new Box2D(100, 200, 200, 300);
		
		this.setBackground(Color.WHITE);
	}
	
	public void paintComponent(Graphics g){
	    super.paintComponent(g);
		Graphics2D g2 = (Graphics2D) g;
		
		drawTree(g2, tree.getRoot(), 0, 50, 350, 50, 350);
		
		g2.setColor(Color.BLACK);
		new Box2D(50, 350, 50, 350).draw(g2);
        
        g2.setColor(Color.RED);
        for(Point2D point : tree.rangeSearch(range)){
            point.draw(g2, 1.5);
        }
        range.draw(g2);
	}

	private void drawTree(Graphics2D g2, KDTree2D.Node node, int step,
	        double xmin, double xmax, double ymin, double ymax) {
	    if(node==null)
	        return;
	    
	    int dir = step%2;
	    Point2D point = node.getPoint();
        double x = point.getX();
        double y = point.getY();
        
	    if(dir==0){
	        // Draw vertical line
	        g2.setColor(Color.BLUE);
            new LineSegment2D(x, ymin, x, ymax).draw(g2);
	        
	        // reduce x range for each sub tree
	        drawTree(g2, node.getLeftChild(), step+1, 
	                xmin, x, ymin, ymax);
	        drawTree(g2, node.getRightChild(), step+1, 
	                x, xmax, ymin, ymax);
	    } else {
	        // Draw horizontal line
	        g2.setColor(Color.BLUE);
	        new LineSegment2D(xmin, y, xmax, y).draw(g2);
	        
	        // reduce y range for each sub tree
	        drawTree(g2, node.getLeftChild(), step+1, 
	                xmin, xmax, ymin, y);
	        drawTree(g2, node.getRightChild(), step+1, 
	                xmin, xmax, y, ymax);
	    }
	    
	    g2.setColor(Color.BLACK);
        point.draw(g2, 1.5);
	}

	public final static void main(String[] args){
		JPanel panel = new RangeSearchKDTree2DRandomDemo();
		JFrame frame = new JFrame("Draw KD Tree Demo");
		frame.setContentPane(panel);
		frame.setSize(500, 400);
		frame.setVisible(true);
	}
}

back to demos page

---