Finding points in 3D space using point quad tree – java sources

Solved problem

This post introduces an working algoritm that can be used for searching through a 3D space filled with 3D points. Each point is represented by its x, y, z coordinates. Search is performed using search rectangular box, specified by its left bottom back and right top front corners.

As a result, all points from 3D space that belong to the search box are returned. See this demo live:

See video of the demo:

Work on it is done as part of my Phd studies at University of Pardubice under supervision of my teacher, Kavička Antonín, prof. Ing. Ph.D. .

Demo demonstrating the algoritm implementation

  • Demo first generates fixed number of 3D points in the working area between -100,-100,-100 and 100, 100, 100. These points are added to the QuadTree3D instance using add method. This is the part when quad tree is built in memory:

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

    int x = random.nextInt(quadrantWidth+1) - quadrantWidth/2;

    int y = random.nextInt(quadrantWidth+1) - quadrantWidth/2;

    int z = random.nextInt(quadrantWidth+1) - quadrantWidth/2;

    quad.addPoint(new Point(x,y,z));

}
  • Next step is performing a search in this 3D space, using search method. It accepts two arguments defining a search box, leftBottomBack and rightTopFront points:
Point searchFrom = new Point(fromX, fromY, fromZ);

Point searchTo = new Point(toX, toY, toZ);

List<Point> found = quad.search(searchFrom, searchTo);
  • Finally, 3D space is rendered on the OpenGL canvas. Found points are displayed as white, other points are green. Quadrant’s cubes are rendered as cyan and search box is transparent purple.

How to execute demo

If you are running Windows, just download and extract the zip file, execute bin/go.bat from command line. On other OS you can run is as standard java application:

java -Djava.library.path=. -DnumberOfPoints=%POINTS% -DfromX=%fromX% -DfromY=%fromY% -DfromZ=%fromZ% -DtoX=%toX% -DtoY=%toY% -DtoZ=%toZ% -DshowQuadCubes=%showQuadCubes% -classpath quadtree3ddemo.jar;timer.jar;jogl.jar net.jetensky.quadtree3d.QuadTree3DDemo

Just replace the %% variables with desired values. You can use the default settings:

SET POINTS=30
# Whole searchable region is from -100,-100,-100 to 100,100,100, FROM and TO search window should be subset of this
SET fromX=-100
SET fromY=-50
SET fromZ=-0
SET toX=-50
SET toY=110
SET toZ=70
SET showQuadCubes=false

Technical background – Region Point Quad Tree

At the core of the demo is implementation of PR Quadtree (Point Region Quad Tree), as defined by Hanan Samet in Foundations of Multidimensional and Metric Data Structures in chapter 1.4.2.2 PR Quadtrees. There is a slight difference in the implementation of logic behind choosing, wheter actual quadrant should be searched:

  • Samet (in figure 1.27) suggests to compare the root of the quadrant to the position of the search box and enumerates all the options.
  • My implementation simplifies the solution to answering, whether the search box and actual quadrant intersects. If there is no intersection, whole quadrant can be skipped as it is completely outside the search box
        public boolean intersects(Point leftBottomBack, Point rightTopFront) {
            return !(
                    center.getX() - halfWidth > rightTopFront.getX() ||
                    center.getX() + halfWidth < leftBottomBack.getX() ||
                    center.getY() - halfWidth > rightTopFront.getY() ||
                    center.getY() + halfWidth < leftBottomBack.getY() ||
                    center.getZ() - halfWidth > rightTopFront.getZ() ||
                    center.getZ() + halfWidth < leftBottomBack.getZ()
            );
        }

Used technologies

Algoritm and demo is implemented in Java. Graphical representation of points is rendered using Java OpenGL library (jogl). Whole demo, including sources and working executable, can be downloaded:

Please feel free to use the source code for your needs, however I would be glad if you let me know how you use it by writing a comment to this post.

1 Star2 Stars3 Stars4 Stars5 Stars (No Ratings Yet)
Loading ... Loading ...

3 Comments so far

  1. Jety on Červenec 8th, 2011

    I fixed the link to 3DQuadTree.zip (file containing the sources and working executable), it was broken till now.

  2. Tibo on Leden 11th, 2016

    Hi Jety,

    I like the idea of demonstrating the Quadtree in this nice graphic.
    I am looking for Java implementation for 3D quadtree where x and y are the lat and long of locations and z will be a time stamp of the day. I am not if your implementation can fit here.
    I also tried your exe file but did not work and I imported the source code into eclipse but was not able to compile it.
    It will be great if you can provide some guidelines here.
    Thanks in advance.

  3. Jety on Leden 13th, 2016

    Hi Tibo, I have created the project in Intellij Idea and to my surprise, I did not include Maven build pom.xml file. To solve your compilation problem you need to put all the jars and dlls from lib folder to your classpath. I believe that Quad tree is OK for your usecase.