kdTree2_mod

link to source code

Dependency Diagrams:

kdTree2_mod.svg

Direct Dependency Diagram

kdTree2_mod_rev.svg

Reverse Dependency Diagram

Description

MODULE kdTree2_mod (prefix=’kdtree2’ category=’8. Low-level utilities and constants’)

Purpose

An implementation of the kdtree algorithm for efficiently finding nearby locations (first used in LETKF to find all obs near an analysis grid point). Written by Matt Kennel.

Quick access

Types

interval

Variables

kdkind, kdtree2, tree_node

Routines

box_in_search_range(), build_tree(), build_tree_for_range(), dis2_from_bnd(), heapsort(), heapsort_struct(), kdtree2_3dposition(), kdtree2_create(), kdtree2_destroy(), kdtree2_n_nearest(), kdtree2_n_nearest_around_point(), kdtree2_n_nearest_brute_force(), kdtree2_r_count(), kdtree2_r_count_around_point(), kdtree2_r_nearest(), kdtree2_r_nearest_around_point(), kdtree2_r_nearest_brute_force(), kdtree2_sort_results(), process_terminal_node(), process_terminal_node_fixedball(), search(), select_on_coordinate(), select_on_coordinate_value(), spread_in_coordinate(), square_distance(), validate_query_storage()

Needed modules

  • utilities_mod: MODULE utilities_mod (prefix=’utl’ category=’8. Low-level utilities and constants’)

  • kdtree2_precision_mod: MODULE kdtree2_precision_mod (prefix=’none’ category=’8. Low-level utilities and constants’)

  • kdtree2_priority_queue_mod: MODULE kdtree2_priority_queue_mod (prefix=’none’ category=’8. Low-level utilities and constants’)

  • earthconstants_mod: MODULE earthConstants_mod (prefix=’ec’ category=’8. Low-level utilities and constants’)

Types

  • type  kdtree2_mod/interval
    Type fields

    • % lower [real ]

    • % upper [real ]

  • type  kdtree2_mod/unknown_type
  • type  kdtree2_mod/unknown_type
    Type fields

    • % dimen [integer ]

    • % ind (*) [integer ,pointer]

    • % n [integer ]

    • % null [real ,pointer]

    • % rearrange [logical ]

    • % rearranged_data (*,*) [real ,pointer]

    • % root [tree_node ,pointer]

    • % sort [logical ]

    • % the_data (*,*) [real ,pointer]

  • type  kdtree2_mod/unknown_type

Variables

  • kdtree2_mod/kdkind [integer,public]
  • kdtree2_mod/kdtree2 [integer,public]
  • kdtree2_mod/tree_node [real,public]

Subroutines and functions

function  kdtree2_mod/kdtree2_create(input_data[, dim[, sort[, rearrange]]])
Purpose

Create the actual tree structure, given an input array of data.

Arguments

input_data (*,*) [real ,target]

Options

  • dim [integer ,in,]

  • sort [logical ,in,]

  • rearrange [logical ,in,]

Return

mr [kdtree2 ,pointer]

Called from

findobs(), brpr_updateburp(), eob_getlocalbodyindices(), gpos_xyfll_unstructgrid(), int_sintcloudtogrid_gsv(), ocm_farfromland(), sstb_getgriddedobs(), sstb_getgriddedbias(), s2c_setupinterpinfo()

Call to

utl_abort(), build_tree()

subroutine  kdtree2_mod/build_tree(tp)
Arguments

tp [kdtree2 ,pointer]

Called from

kdtree2_create()

Call to

build_tree_for_range()

function  kdtree2_mod/build_tree_for_range(tp, l, u, parent)
Arguments

  • tp [kdtree2 ,pointer]

  • l [integer ,in]

  • u [integer ,in]

  • parent [tree_node ,pointer]

Return

res [tree_node ,pointer]

Called from

build_tree()

function  kdtree2_mod/select_on_coordinate_value(v, ind, c, alpha, li, ui)
Purpose

Move elts of ind around between l and u, so that all points <= than alpha (in c cooordinate) are first, and then all points > alpha are second.

Arguments

  • v (,) [real ]

  • ind () [integer ]

  • c [integer ,in]

  • alpha [real ,in]

  • li [integer ,in]

  • ui [integer ,in]

Return

res [real ]

subroutine  kdtree2_mod/select_on_coordinate(v, ind, c, k, li, ui)
Purpose

Move elts of ind around between l and u, so that the kth element is >= those below, <= those above, in the coordinate c.

Arguments

  • v (*,*) [real ]

  • ind (*) [integer ]

  • c [integer ,in]

  • k [integer ,in]

  • li [integer ,in]

  • ui [integer ,in]

subroutine  kdtree2_mod/spread_in_coordinate(tp, c, l, u, interv)
Purpose

the spread in coordinate ‘c’, between l and u. Return lower bound in ‘smin’, and upper in ‘smax’,

Arguments

  • tp [kdtree2 ,pointer]

  • c [integer ,in]

  • l [integer ,in]

  • u [integer ,in]

  • interv [interval ,out]

subroutine  kdtree2_mod/kdtree2_destroy(tp)
Purpose

Deallocates all memory for the tree, except input data matrix

Arguments

tp [kdtree2 ,pointer]

Called from

brpr_updateburp(), int_sintcloudtogrid_gsv(), s2c_setupinterpinfo()

subroutine  kdtree2_mod/kdtree2_n_nearest(tp, qv, nn, results)
Purpose

Find the ‘nn’ vectors in the tree nearest to ‘qv’ in euclidean norm returning their indexes and distances in ‘indexes’ and ‘distances’ arrays already allocated passed to this subroutine.

Arguments

  • tp [kdtree2 ,pointer]

  • qv (*) [real ,in,target]

  • nn [integer ,in]

  • results (*) [kdtree2_result ,target]

Call to

validate_query_storage(), pq_create(), search(), kdtree2_sort_results()

subroutine  kdtree2_mod/kdtree2_n_nearest_around_point(tp, idxin, correltime, nn, results)
Purpose

Find the ‘nn’ vectors in the tree nearest to point ‘idxin’, with correlation window ‘correltime’, returing results in

Arguments

  • results (*) [kdtree2_result ,target] :: which must be pre-allocated upon entry.

  • tp [kdtree2 ,pointer]

  • idxin [integer ,in]

  • correltime [integer ,in]

  • nn [integer ,in]

Call to

validate_query_storage(), pq_create(), search(), kdtree2_sort_results()

subroutine  kdtree2_mod/kdtree2_r_nearest(tp, qv, r2, nfound, nalloc, results)
Purpose

find the nearest neighbors to point ‘idxin’, within SQUARED Euclidean distance ‘r2’. Upon ENTRY, nalloc must be the size of memory allocated for results(1:nalloc). Upon EXIT, nfound is the number actually found within the ball.

Note that if nfound .gt. nalloc then more neighbors were found than there were storage to store. The resulting list is NOT the smallest ball inside norm r^2

Results are NOT sorted unless tree was created with sort option.

Arguments

  • tp [kdtree2 ,pointer]

  • qv (*) [real ,in,target]

  • r2 [real ,in]

  • nfound [integer ,out]

  • nalloc [integer ,in]

  • results (*) [kdtree2_result ,target]

Called from

findobs(), brpr_updateburp(), eob_getlocalbodyindices(), gpos_xyfll_unstructgrid(), int_sintcloudtogrid_gsv(), ocm_farfromland(), sstb_getgriddedobs(), sstb_getgriddedbias(), s2c_setupfootprintinterp()

Call to

validate_query_storage(), search(), kdtree2_sort_results()

subroutine  kdtree2_mod/kdtree2_r_nearest_around_point(tp, idxin, correltime, r2, nfound, nalloc, results)
Purpose

Like kdtree2_r_nearest, but around a point ‘idxin’ already existing in the data set.

Results are NOT sorted unless tree was created with sort option.

Arguments

  • tp [kdtree2 ,pointer]

  • idxin [integer ,in]

  • correltime [integer ,in]

  • r2 [real ,in]

  • nfound [integer ,out]

  • nalloc [integer ,in]

  • results (*) [kdtree2_result ,target]

Call to

validate_query_storage(), search(), kdtree2_sort_results()

function  kdtree2_mod/kdtree2_r_count(tp, qv, r2)
Purpose

Count the number of neighbors within square distance ‘r2’.

Arguments

  • tp [kdtree2 ,pointer]

  • qv (*) [real ,in,target]

  • r2 [real ,in]

Return

nfound [integer ]

Call to

search()

function  kdtree2_mod/kdtree2_r_count_around_point(tp, idxin, correltime, r2)
Purpose

Count the number of neighbors within square distance ‘r2’ around point ‘idxin’ with decorrelation time ‘correltime’.

Arguments

  • tp [kdtree2 ,pointer]

  • idxin [integer ,in]

  • correltime [integer ,in]

  • r2 [real ,in]

Return

nfound [integer ]

Call to

search()

subroutine  kdtree2_mod/validate_query_storage(n)
Purpose

make sure we have enough storage for n

Arguments

n [integer ,in]

Called from

kdtree2_n_nearest(), kdtree2_n_nearest_around_point(), kdtree2_r_nearest(), kdtree2_r_nearest_around_point()

Call to

utl_abort()

function  kdtree2_mod/square_distance(d, iv, qv)
Purpose

distance between iv[1:n] and qv[1:n]

Arguments

  • d [integer ]

  • iv (*) [real ]

  • qv (*) [real ]

Return

res [real ]

Called from

kdtree2_n_nearest_brute_force(), kdtree2_r_nearest_brute_force()

subroutine  kdtree2_mod/search(node)
Arguments

node [tree_node ,pointer]

Called from

kdtree2_n_nearest(), kdtree2_n_nearest_around_point(), kdtree2_r_nearest(), kdtree2_r_nearest_around_point(), kdtree2_r_count(), kdtree2_r_count_around_point()

function  kdtree2_mod/dis2_from_bnd(x, amin, amax)
Arguments

  • x [real ,in]

  • amin [real ,in]

  • amax [real ,in]

Return

res [real ]

Called from

box_in_search_range()

function  kdtree2_mod/box_in_search_range(node, sr)
Purpose

Return the distance from ‘qv’ to the CLOSEST corner of node’s bounding box for all coordinates outside the box. Coordinates inside the box contribute nothing to the distance.

Arguments

  • node [tree_node ,pointer]

  • sr (*) [tree_search_record ,pointer]

Return

res [real ]

Call to

dis2_from_bnd()

subroutine  kdtree2_mod/process_terminal_node(node)
Purpose

Look for actual near neighbors in ‘node’, and update the search results on the sr(:) data structure.

Arguments

node [tree_node ,pointer]

Call to

pq_insert(), pq_replace_max()

subroutine  kdtree2_mod/process_terminal_node_fixedball(node)
Purpose

Look for actual near neighbors in ‘node’, and update the search results on the sr(:) data structure, i.e. save all within a fixed ball.

Arguments

node [tree_node ,pointer]

subroutine  kdtree2_mod/kdtree2_n_nearest_brute_force(tp, qv, nn, results)
Purpose

find the ‘n’ nearest neighbors to ‘qv’ by exhaustive search. only use this subroutine for testing, as it is SLOW! The whole point of a k-d tree is to avoid doing what this subroutine does.

Arguments

  • tp [kdtree2 ,pointer]

  • qv (*) [real ,in]

  • nn [integer ,in]

  • results (*) [kdtree2_result ]

Call to

square_distance()

subroutine  kdtree2_mod/kdtree2_r_nearest_brute_force(tp, qv, r2, nfound, results)
Purpose

find the nearest neighbors to ‘qv’ with distance**2 <= r2 by exhaustive search. only use this subroutine for testing, as it is SLOW! The whole point of a k-d tree is to avoid doing what this subroutine does.

Arguments

  • tp [kdtree2 ,pointer]

  • qv (*) [real ,in]

  • r2 [real ,in]

  • nfound [integer ,out]

  • results (*) [kdtree2_result ]

Call to

square_distance(), kdtree2_sort_results()

subroutine  kdtree2_mod/kdtree2_sort_results(nfound, results)
Purpose

Use after search to sort results(1:nfound) in order of increasing distance.

Arguments

  • nfound [integer ,in]

  • results (*) [kdtree2_result ,target]

Called from

kdtree2_n_nearest(), kdtree2_n_nearest_around_point(), kdtree2_r_nearest(), kdtree2_r_nearest_around_point(), kdtree2_r_nearest_brute_force()

Call to

heapsort_struct()

subroutine  kdtree2_mod/heapsort(a, ind, n)
Purpose

Sort a(1:n) in ascending order, permuting ind(1:n) similarly.

If ind(k) = k upon input, then it will give a sort index upon output.

Arguments

  • a (*) [real ,inout]

  • ind (*) [integer ,inout]

  • n [integer ,in]

subroutine  kdtree2_mod/heapsort_struct(a, n)
Purpose

Sort a(1:n) in ascending order

Arguments

  • a (*) [kdtree2_result ,inout]

  • n [integer ,in]

Called from

kdtree2_sort_results()

function  kdtree2_mod/kdtree2_3dposition(lon_rad, lat_rad)
Purpose

Calculate the 3 dimensional coordinates of a point on the sphere of Earth radius given the longitude-latitude position on the surface of the sphere in radian.

Arguments

  • lon_rad [real ,in]

  • lat_rad [real ,in]

Return

positionarray (3) [real ] :: returned values of function

Called from

findobs(), gpos_xyfll_unstructgrid(), int_sintcloudtogrid_gsv(), ocm_farfromland(), sstb_getgriddedobs(), sstb_getgriddedbias(), s2c_setupinterpinfo(), s2c_setupfootprintinterp()