m_KdTree Module

  1. m_KdTree.f90
  2. m_KdTree
module~~m_kdtree~~UsesGraph module~m_kdtree m_KdTree module~idynamicarray_class iDynamicArray_Class module~idynamicarray_class->module~m_kdtree module~dargdynamicarray_class dArgDynamicArray_Class module~idynamicarray_class->module~dargdynamicarray_class module~variablekind variableKind module~variablekind->module~m_kdtree module~variablekind->module~idynamicarray_class module~variablekind->module~dargdynamicarray_class module~m_array1d m_array1D module~variablekind->module~m_array1d module~m_strings m_strings module~variablekind->module~m_strings module~m_errors m_errors module~variablekind->module~m_errors module~m_allocate m_allocate module~variablekind->module~m_allocate module~m_select m_select module~variablekind->module~m_select module~m_deallocate m_deallocate module~variablekind->module~m_deallocate module~m_maths m_maths module~variablekind->module~m_maths module~m_sort m_sort module~variablekind->module~m_sort module~m_searching m_searching module~variablekind->module~m_searching module~m_reallocate m_reallocate module~variablekind->module~m_reallocate module~ddynamicarray_class dDynamicArray_Class module~variablekind->module~ddynamicarray_class module~m_random m_random module~variablekind->module~m_random module~m_swap m_swap module~variablekind->module~m_swap module~prng_class Prng_Class module~variablekind->module~prng_class module~m_unittester m_unitTester module~variablekind->module~m_unittester module~m_indexing m_indexing module~variablekind->module~m_indexing module~m_time m_time module~variablekind->module~m_time module~m_parameters m_parameters module~variablekind->module~m_parameters module~dargdynamicarray_class->module~m_kdtree module~m_array1d->module~m_kdtree module~m_array1d->module~m_maths module~m_strings->module~m_kdtree module~m_strings->module~idynamicarray_class module~m_strings->module~dargdynamicarray_class module~m_strings->module~m_array1d module~m_strings->module~ddynamicarray_class module~m_strings->module~m_random module~m_strings->module~prng_class module~m_errors->module~m_kdtree module~m_errors->module~idynamicarray_class module~m_errors->module~dargdynamicarray_class module~m_errors->module~m_array1d module~m_errors->module~m_strings module~m_errors->module~m_allocate module~m_errors->module~m_deallocate module~m_errors->module~m_maths module~m_errors->module~m_reallocate module~m_errors->module~ddynamicarray_class module~m_errors->module~m_random module~m_errors->module~prng_class module~m_errors->module~m_unittester module~m_allocate->module~m_kdtree module~m_allocate->module~idynamicarray_class module~m_allocate->module~m_array1d module~m_allocate->module~m_maths module~m_allocate->module~m_reallocate module~m_allocate->module~ddynamicarray_class module~m_allocate->module~m_random module~m_allocate->module~prng_class module~m_select->module~m_kdtree module~m_select->module~m_maths module~m_deallocate->module~m_kdtree module~m_deallocate->module~idynamicarray_class module~m_deallocate->module~m_maths module~m_deallocate->module~ddynamicarray_class module~m_deallocate->module~m_random module~m_maths->module~m_kdtree module~m_sort->module~idynamicarray_class module~m_sort->module~m_maths module~m_sort->module~ddynamicarray_class module~m_searching->module~idynamicarray_class module~m_searching->module~dargdynamicarray_class module~m_searching->module~ddynamicarray_class module~m_reallocate->module~idynamicarray_class module~m_reallocate->module~ddynamicarray_class iso_fortran_env iso_fortran_env iso_fortran_env->module~variablekind iso_fortran_env->module~dargdynamicarray_class iso_fortran_env->module~m_strings iso_fortran_env->module~m_errors iso_fortran_env->module~m_random iso_fortran_env->module~prng_class iso_fortran_env->module~m_unittester module~ddynamicarray_class->module~dargdynamicarray_class module~m_random->module~m_array1d module~m_swap->module~m_array1d module~prng_class->module~m_random module~m_unittester->module~m_allocate module~m_unittester->module~m_maths module~m_unittester->module~m_random module~m_indexing->module~prng_class module~m_time->module~prng_class module~m_parameters->module~m_strings
Help

KdTree

Build and search k-dimensional trees in 2, 3, and K dimensions. This KdTree is balanced, in that splits are made along the dimension with the largest variance. A quickselect is used to quickly find the median in each splitting dimension as the splitting value. The ends of each branch contain multiple leaves to prevent tail recursion. An in-depth example is given below on how to use all the aspects of the KdTree and KdTreeSearch classes.

Important: Once a tree has been built with a set, do not change their values. The KdTree does NOT make a copy of the input values used to build it. Important: Generating the tree does not modify the values used to build it.

Building the KdTree

The KdTree object can be initialized on assignment by entering point co-ordinates. To build a 2-D tree, you can use two 1-D arrays as the x, y, co-ordinates, and optionally a third 1-D array to build a 3-D tree.

use m_KdTree
type(KdTree) :: tree
tree = KdTree(x, y, [z])

Or you can build a k-dimensional tree using a 2-D array, where the first dimension is the number of items, and the second is the number of dimensions, k.

use m_KdTree
type(KdTree) :: tree
tree = KdTree(D)

Querying the KdTree

After the tree is initialized, a search class can be used to perform search for the nearest neighbour, the k nearest neighbours, all neighbours within a radius, k nearest within a radius, and items within upper and lower bounds in each dimension. The searches are thread safe and can be used in a parallel region.

After the KdTree is built, various queries can be carried out. Searches that return multiple values are called using the argDynamicArray within coretran. The [[m_dArgDynamicArray]] contains an integer index containing the indices into the co-ordinates that are closest, and a double precision that contains the distance from the query point to those points.

use m_dArgDynamicArray
use m_KdTree
type(KdTreeSearch) :: search
integer(i32) :: i
type(dArgDynamicArray) :: da
! Nearest Neighbour to (0, 0), for 3D add z, and zQuery
i = search%nearest(tree, x, y, [z], xQuery = 0.d0, yQuery = 0.d0, [zQuery = 0.d0])
! K-Nearest to (0, 0), for 3D add z, and zQuery
da = search%kNearest(tree, x, y, [z], xQuery = 0.d0, yQuery = 0.d0, [zQuery = 0.d0], k = 10)
! Search for all points within a given distance
da = search%kNearest(tree, x, y, [z], xQuery = 0.d0, yQuery = 0.d0, [zQuery = 0.d0], radius = 10.d0)
! Search for all k points within a given distance
da = search%kNearest(tree, x, y, [z], xQuery = 0.d0, yQuery = 0.d0, [zQuery = 0.d0], k = 10, radius = 10.d0)

Full Example

program kdTree_test
use variableKind, only: i32, r64
use m_allocate, only: allocate
use m_deallocate, only: deallocate
use m_random, only: rngNormal
use m_KdTree, only: KdTree, KdTreeSearch
use m_dArgDynamicArray, only: dArgDynamicArray
use m_string, only: str
implicit none
real(r64), allocatable :: x(:), y(:), z(:), D(:,:)
integer(i32) :: ia, N
type(KdTree) :: tree
type(KdSearch) :: search
type(dArgDynamicArray) :: da

!====================================================================!
! 2D KdTree example
!====================================================================!
! Create some random points in space
N = 1d6
call allocate(x, N)
call allocate(y, N)
call rngNormal(x)
call rngNormal(y)
! Build the tree
tree = KdTree(x, y)
! Get the nearest neighbour to (0, 0)
ia = search%kNearest(tree, x, y, xQuery = 0.d0, yQuery = 0.d0)
write(*,'(a)') 'Nearest point to the query location: '//str(x(ia))//str(y(ia))
! Get the 10 nearest neighbours to the query
da = search%kNearest(tree, x, y, xQuery = 0.d0, yQuery = 0.d0, k = 10)
write(*,'(a)') 'The 10 nearest neighbour indices and distances:'
call da%print()
! Find all the points within a 1.d0
da = search%kNearest(tree, x, y, xQuery = 0.d0, yQuery = 0.d0, radius = 1.d0)
write(*,'(a)') 'The points within a distance of 1.d0'
call da%print()
Deallocate any tree memory
call tree%deallocate()

!====================================================================!
! 3D KdTree example
!====================================================================!
! Create the third dimension
call allocate(z, N)
call rngNormal(z)
! Build the tree
tree = KdTree(x, y, z)
! Get the nearest neighbour to (0, 0, 0)
ia = search%kNearest(tree, x, y, z, xQuery = 0.d0, yQuery = 0.d0, zQuery = 0.d0)
write(*,'(a)')'Nearest point to the query location: '//str(x(ia))//str(y(ia))//str(z(ia))
! Get the 10 nearest neighbours to the query
da = search%kNearest(tree, x, y, z, xQuery = 0.d0, yQuery = 0.d0, zQuery = 0.d0, k = 10)
write(*,'(a)') 'The 10 nearest neighbour indices and distances:'
call da%print()
! Find all the points within a 1.d0
da = search%kNearest(tree, x, y, z, xQuery = 0.d0, yQuery = 0.d0, zQuery = 0.d0, radius = 1.d0)
write(*,'(a)') 'The points within a distance of 1.d0'
call da%print()
Deallocate any tree memory
call tree%deallocate()

!====================================================================!
! KD KdTree example
!====================================================================!
call allocate(D, [N, 3])
D(:,1) = x
D(:,2) = y
D(:,3) = z
! Build the tree
tree = KdTree(D)
! Get the nearest neighbour to (0, 0, 0)
ia = search%kNearest(tree, D, query = [0.d0, 0.d0, 0.d0])
write(*,'(a)')'Nearest point to the query location: '//str(D(ia, 1))//str(D(ia, 2))//str(D(ia, 3))
! Get the 10 nearest neighbours to the query
da = search%kNearest(tree, D, query = [0.d0, 0.d0, 0.d0], k = 10)
write(*,'(a)') 'The 10 nearest neighbour indices and distances:'
call da%print()
! Find all the points within a 1.d0
da = search%kNearest(tree, D,  query = [0.d0, 0.d0, 0.d0], radius = 1.d0)
write(*,'(a)') 'The points within a distance of 1.d0'
call da%print()
Deallocate any tree memory
call tree%deallocate()
call deallocate(x)
call deallocate(y)
call deallocate(z)
call deallocate(D)
end program

Used By

module~~m_kdtree~~UsedByGraph module~m_kdtree m_KdTree program~scaletest_coretran scaleTest_coretran module~m_kdtree->program~scaletest_coretran module~m_tests m_tests module~m_kdtree->module~m_tests program~test_coretran test_coretran module~m_tests->program~test_coretran
Help

Interfaces

Derived Types


Interfaces

public interface KdTree

Overloaded Initializer for a KdTree.

  • public function init2D_KdTree(x, y) result(this)

    Overloaded by interface KdTree

    Arguments

    Type IntentOptional AttributesName
    real(kind=r64), intent(in) :: x(:)

    x-coordinates of the points
    real(kind=r64), intent(in) :: y(:)

    y-coordinates of the points

    Return Value type(KdTree)

    KdTree Class

  • public function init3D_KdTree(x, y, z) result(this)

    Overloaded by interface KdTree

    Arguments

    Type IntentOptional AttributesName
    real(kind=r64), intent(in) :: x(:)

    x-coordinates of the points
    real(kind=r64), intent(in) :: y(:)

    y-coordinates of the points
    real(kind=r64), intent(in) :: z(:)

    z-coordinates of the points

    Return Value type(KdTree)

    KdTree Class

  • public function initKD_KdTree(D) result(this)

    Overloaded by interface KdTree

    Arguments

    Type IntentOptional AttributesName
    real(kind=r64), intent(in) :: D(:,:)

    Coordinates of the points, the k columns contain the k dimensional values.

    Return Value type(KdTree)

    KdTree Class


Derived Types

type, public :: KdTree

KdTree in 2, 3, or N dimensions. See m_KdTree for more information on how to use this class.

Constructor

Overloaded Initializer for a KdTree.

public function init2D_KdTree(x, y)

Overloaded by interface KdTree

public function init3D_KdTree(x, y, z)

Overloaded by interface KdTree

public function initKD_KdTree(D)

Overloaded by interface KdTree

Type-Bound Procedures

procedure, public :: deallocate => deallocate_KdTree

kdTree%deallocate() - deallocate the recursive pointers

type, public :: KdTreeSearch

Class to search a KdTree. See m_KdTree for more information on how to use this class.

Type-Bound Procedures

generic, public :: nearest => nearest2D, nearest3D, nearestKD

KdTreeSearch%nearest() - Perform a nearest neighbour search

generic, public :: kNearest => kNearest2D, kNearest3D, kNearestKD

KdTreeSearch%kNearest() - Perform a k nearest neighbour search or a radius search.

generic, public :: rangeSearch => rangeSearch2D, rangeSearch3D, rangeSearchKD

KdTreeSearch%rangeSearch() - Find all points within axis aligned lower and upper bounds

All Modules