Package mgui.geometry.util

Class K3DBinaryTree

java.lang.Object
mgui.geometry.util.K3DBinaryTree
public class K3DBinaryTree
extends java.lang.Object
Implements a kd-tree for 3 dimensions; specifically Euclidian points in R3. Useful, e.g., for a binary nearest neighbour search. See http://en.wikipedia.org/wiki/kd-tree.
Since:
1.0
Version:
1.0
Author:
Andrew Reid

  • Nested Class Summary

    Nested Classes
    Modifier and Type Class Description
    static class  K3DBinaryTree.K3DNode  

  • Field Summary

    Fields
    Modifier and Type Field Description
    K3DBinaryTree.K3DNode root  
    int size  

  • Constructor Summary

    Constructors
    Constructor Description
    K3DBinaryTree​(java.util.ArrayList<org.jogamp.vecmath.Point3f> points)
    Constructor builds a k3-tree from points

  • Method Summary

    Modifier and Type Method Description
    protected K3DBinaryTree.K3DNode addNode​(java.util.List<mgui.geometry.util.K3DBinaryTree.Vertex> vertices, int depth)
    Adds nodes recursively until the entire set is assigned.
    protected float getAxisDistance​(mgui.geometry.util.K3DBinaryTree.Vertex vertex, org.jogamp.vecmath.Point3f point, int axis)  
    protected K3DBinaryTree.K3DNode getClosestChild​(K3DBinaryTree.K3DNode node, org.jogamp.vecmath.Point3f point)  
    protected K3DBinaryTree.K3DNode getFurthestChild​(K3DBinaryTree.K3DNode node, org.jogamp.vecmath.Point3f point)  
    int getNearestNeighbour​(org.jogamp.vecmath.Point3f point)
    Searches this binary tree for the nearest neighbour
    java.util.ArrayList<java.lang.Integer> getTreeValues​(int max_depth)
    Returns a list of values representing the position of each vertex in this tree.
    protected K3DBinaryTree.K3DNode searchNN​(K3DBinaryTree.K3DNode here, org.jogamp.vecmath.Point3f point, K3DBinaryTree.K3DNode best, MguiFloat current_best)
    Does a recursive search of this tree to find the nearest neighbour of point.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Field Details

  • Constructor Details

    • K3DBinaryTree

      public K3DBinaryTree​(java.util.ArrayList<org.jogamp.vecmath.Point3f> points)
      Constructor builds a k3-tree from points
      Parameters:
      points -

  • Method Details

    • addNode

      protected K3DBinaryTree.K3DNode addNode​(java.util.List<mgui.geometry.util.K3DBinaryTree.Vertex> vertices, int depth)
      Adds nodes recursively until the entire set is assigned.
      Parameters:
      vertices -
      depth -
      Returns:

    • getTreeValues

      public java.util.ArrayList<java.lang.Integer> getTreeValues​(int max_depth)
      Returns a list of values representing the position of each vertex in this tree. Values are determined as:

      All values left of the root are negative; right are positive

      The magnitude is determined as how left a node is, times its depth; all values under max_depth are assigned the value of their parents.

      Returns:

    • getNearestNeighbour

      public int getNearestNeighbour​(org.jogamp.vecmath.Point3f point)
      Searches this binary tree for the nearest neighbour
      Parameters:
      point -
      Returns:

    • searchNN

      protected K3DBinaryTree.K3DNode searchNN​(K3DBinaryTree.K3DNode here, org.jogamp.vecmath.Point3f point, K3DBinaryTree.K3DNode best, MguiFloat current_best)
      Does a recursive search of this tree to find the nearest neighbour of point.
      Parameters:
      here -
      point -
      best -
      current_best -
      Returns:

    • getClosestChild

      protected K3DBinaryTree.K3DNode getClosestChild​(K3DBinaryTree.K3DNode node, org.jogamp.vecmath.Point3f point)

    • getFurthestChild

      protected K3DBinaryTree.K3DNode getFurthestChild​(K3DBinaryTree.K3DNode node, org.jogamp.vecmath.Point3f point)

    • getAxisDistance

      protected float getAxisDistance​(mgui.geometry.util.K3DBinaryTree.Vertex vertex, org.jogamp.vecmath.Point3f point, int axis)