helium/kdtree

Name: kdtree

Owner: Helium

Description: Simple kdtree library in erlang

Created: 2018-01-02 00:09:40.0

Updated: 2018-04-17 01:00:06.0

Pushed: 2018-04-17 01:00:06.0

Homepage: null

Size: 1437

Language: Erlang

GitHub Committers

User	Most Recent Commit	# Commits

Other Committers

User	Email	Most Recent Commit	# Commits

README

kdtree

Erlang implementation of kdtree

Implementation:

• Uses haversine distance to approximate the distance between two GPS coordinates.
• Building a tree from a list of coordinates takes O(nlog(n)) time complexity.
• I've added a placeholder on the node which allows you to put in any value/data. I use it to add PIDs as an example.
• Search takes O(log(n)) time complexity.

Build

$ make

Test

$ make test

Typecheck

$ make typecheck

Example:

ist = [{{48.55321,-125.02235}, make_ref()},
{45.26664,-66.06525}, make_ref()},
{51.64982,-121.28594}, make_ref()},
{51.6675,-121.29361}, make_ref()},
{47.811,-53.97733}, make_ref()},
{51.685,-121.29861}, make_ref()},
{63.89335,-139.1991}, make_ref()},
{51.84983,-121.60273}, make_ref()}].
8.55321,-125.02235},
ef<0.3804993279.2739142657.109428>},
5.26664,-66.06525},#Ref<0.3804993279.2739142657.109429>},
1.64982,-121.28594},#Ref<0.3804993279.2739142657.109430>},
1.6675,-121.29361},#Ref<0.3804993279.2739142657.109431>},
7.811,-53.97733},#Ref<0.3804993279.2739142657.109432>},
1.685,-121.29861},#Ref<0.3804993279.2739142657.109433>},
3.89335,-139.1991},#Ref<0.3804993279.2739142657.109434>},
1.84983,-121.60273},
ef<0.3804993279.2739142657.109435>}]
ree = kdtree:from_list(List).
e,{51.6675,-121.29361},
  #Ref<0.3804993279.2739142657.109431>,
  {node,{51.64982,-121.28594},
        #Ref<0.3804993279.2739142657.109430>,
        {node,{48.55321,-125.02235},
              #Ref<0.3804993279.2739142657.109428>,
              {node,{45.26664,-66.06525},
                    #Ref<0.3804993279.2739142657.109429>,undefined,undefined},
              undefined},
        {node,{47.811,-53.97733},
              #Ref<0.3804993279.2739142657.109432>,undefined,undefined}},
  {node,{63.89335,-139.1991},
        #Ref<0.3804993279.2739142657.109434>,
        {node,{51.685,-121.29861},
              #Ref<0.3804993279.2739142657.109433>,undefined,undefined},
        {node,{51.84983,-121.60273},
              #Ref<0.3804993279.2739142657.109435>,undefined,undefined}}}
dtree:nearest(Tree, {51.685,-121.29861}).
1.6675,-121.29361},#Ref<0.3804993279.2739142657.109431>},
286600794979432}
dtree:nearby(Tree, {51.685,-121.29861}, 10).
1.64982,-121.28594},
ef<0.3804993279.2739142657.109430>},
1.6675,-121.29361},#Ref<0.3804993279.2739142657.109431>}]

References

k-d tree