Package cz.fidentis.analyst.data.kdtree.impl

Class KdTreeImpl

java.lang.Object
cz.fidentis.analyst.data.kdtree.impl.KdTreeImpl
All Implemented Interfaces:
KdTree, Serializable
public class KdTreeImpl extends Object implements KdTree
Implementation of k-D trees.
See Also:

  • Constructor Details

    • KdTreeImpl

      public KdTreeImpl(Set<MeshPoint> points)
      Constructor.
      Parameters:
      points - A set of individual mesh points. If no mesh points are provided, then an empty KD-tree is constructed (with the root node set to null).

    • KdTreeImpl

      public KdTreeImpl(Collection<MeshFacet> facets)
      Constructor. If no mesh points (vertices) are provided, then an empty KD-tree is constructed (with the root node set to null). If multiple mesh facets share the same vertex, then they are stored efficiently in the same node of the KD-tree.
      Parameters:
      facets - The list of mesh facets to be stored. Facets can share vertices.

  • Method Details

    • getRoot

      public KdNode getRoot()
      Description copied from interface: KdTree
      Tree traversal - go to the "root" of the tree.
      Specified by:
      getRoot in interface KdTree
      Returns:
      root node of the tree

    • addNode

      public void addNode(MeshPoint meshPoint)
      Description copied from interface: KdTree
      Method for adding independent point to existing tree. The balance of the tree is not guaranteed after adding elements, it depends on the distribution of the added points. It can create long linear branches. In Poisson disk sub-sampling, where this method is used, it isn't a problem.
      Specified by:
      addNode in interface KdTree
      Parameters:
      meshPoint - point to add

    • toString

      public String toString()
      Overrides:
      toString in class Object

    • getNumNodes

      public int getNumNodes()
      Description copied from interface: KdTree
      Return number of nodes in the k-d tree.
      Specified by:
      getNumNodes in interface KdTree
      Returns:
      number of nodes in the k-d tree

    • getDepth

      public int getDepth()
      Description copied from interface: KdTree
      Return the length of the longest path.
      Specified by:
      getDepth in interface KdTree
      Returns:
      Return the length of the longest path.

    • accept

      public void accept(KdTreeVisitor visitor)
      Description copied from interface: KdTree
      Visits this tree.
      Specified by:
      accept in interface KdTree
      Parameters:
      visitor - Visitor

    • firstIsLessThanSecond

      protected boolean firstIsLessThanSecond(javax.vecmath.Point3d v1, javax.vecmath.Point3d v2, int level)

    • rearrangeLeafNodes

      protected KdNodeImpl rearrangeLeafNodes(javax.vecmath.Point3d point1, javax.vecmath.Point3d point2, javax.vecmath.Point3d point3, int level)