kdtree

A Python implementation of a kd-tree

https://github.com/stefankoegl/kdtree

Science Score: 10.0%

This score indicates how likely this project is to be science-related based on various indicators:

○
CITATION.cff file
○
codemeta.json file
○
.zenodo.json file
○
DOI references
○
Academic publication links
✓
Committers with academic emails
1 of 15 committers (6.7%) from academic institutions
○
Institutional organization owner
○
JOSS paper metadata
○
Scientific vocabulary similarity
Low similarity (8.5%) to scientific vocabulary

Last synced: 11 months ago · JSON representation

Repository

A Python implementation of a kd-tree

Basic Info

Host: GitHub
Owner: stefankoegl
License: isc
Language: Python
Default Branch: master
Homepage:
Size: 127 KB

Statistics

Stars: 375
Watchers: 11
Forks: 118
Open Issues: 9
Releases: 2

Created over 15 years ago · Last pushed about 1 year ago

Metadata Files

Readme License

A simple kd-tree in Python

The kdtree package can construct, modify and search kd-trees.

Website: https://github.com/stefankoegl/kdtree
Repository: https://github.com/stefankoegl/kdtree.git
Documentation: https://python-kdtree.readthedocs.org/
PyPI: https://pypi.python.org/pypi/kdtree
Travis-CI: https://travis-ci.org/stefankoegl/kdtree
Coveralls: https://coveralls.io/r/stefankoegl/kdtree

Usage

>>> import kdtree

# Create an empty tree by specifying the number of
# dimensions its points will have
>>> emptyTree = kdtree.create(dimensions=3)

# A kd-tree can contain different kinds of points, for example tuples
>>> point1 = (2, 3, 4)

# Lists can also be used as points
>>> point2 = [4, 5, 6]

# Other objects that support indexing can be used, too
>>> import collections
>>> Point = collections.namedtuple('Point', 'x y z')
>>> point3 = Point(5, 3, 2)

# A tree is created from a list of points
>>> tree = kdtree.create([point1, point2, point3])

# Each (sub)tree is represented by its root node
>>> tree
<KDNode - [4, 5, 6]>

# Adds a tuple to the tree
>>> tree.add( (5, 4, 3) )

# Removes the previously added point and returns the new root
>>> tree = tree.remove( (5, 4, 3) )

# Retrieving the Tree in inorder
>>> list(tree.inorder())
[<KDNode - (2, 3, 4)>, <KDNode - [4, 5, 6]>, <KDNode - Point(x=5, y=3, z=2)>]

# Retrieving the Tree in level order
>>> list(kdtree.level_order(tree))
[<KDNode - [4, 5, 6]>, <KDNode - (2, 3, 4)>, <KDNode - Point(x=5, y=3, z=2)>]

# Find the nearest node to the location (1, 2, 3)
>>> tree.search_nn( (1, 2, 3) )
<KDNode - (2, 3, 4)>

# Add a point to make the tree more interesting
>>> tree.add( (10, 2, 1) )

# Visualize the Tree
>>> kdtree.visualize(tree)


                     [4, 5, 6]

           (2, 3, 4)       Point(x=5, y=3, z=2)

                            (10, 2, 1)

# Take the right subtree of the root
>>> subtree = tree.right

# and detatch it
>>> tree.right = None
>>> kdtree.visualize(tree)

           [4, 5, 6]

      (2, 3, 4)

>>> kdtree.visualize(subtree)

      Point(x=5, y=3, z=2)

      (10, 2, 1)

# and re-attach it
>>> tree.right = subtree
>>> kdtree.visualize(tree)

                     [4, 5, 6]

           (2, 3, 4)       Point(x=5, y=3, z=2)

                            (10, 2, 1)

# Add a node to make the tree unbalanced
>>> tree.is_balanced
True
>>> tree.add( (6, 1, 5) )
>>> tree.is_balanced
False
>>> kdtree.visualize(tree)

                                   [4, 5, 6]

               (2, 3, 4)                           Point(x=5, y=3, z=2)
                                               (10, 2, 1)
                                                       (6, 1, 5)
# rebalance the tree
>>> tree = tree.rebalance()
>>> tree.is_balanced
True
>>> kdtree.visualize(tree)

                Point(x=5, y=3, z=2)

           [4, 5, 6]            (6, 1, 5)

      (2, 3, 4)

Adding a payload

Indexing a dict by a pair of floats is not a good idea, since there might be unexpected precision errors. Since KDTree expects a tuple-looking objects for nodes, you can make a class that looks like a tuple, but contains more data. This way you can store all your data in a kdtree, without using an additional indexed structure.

```python import kdtree

This class emulates a tuple, but contains a useful payload

class Item(object): def init(self, x, y, data): self.coords = (x, y) self.data = data

def __len__(self):
    return len(self.coords)

def __getitem__(self, i):
    return self.coords[i]

def __repr__(self):
    return 'Item({}, {}, {})'.format(self.coords[0], self.coords[1], self.data)

Now we can add Items to the tree, which look like tuples to it

point1 = Item(2, 3, 'First') point2 = Item(3, 4, 'Second') point3 = Item(5, 2, ['some', 'list'])

Again, from a list of points

tree = kdtree.create([point1, point2, point3])

The root node

print(tree)

...contains "data" field with an Item, which contains the payload in "data" field

print(tree.data.data)

All functions work as intended, a payload is never lost

print(tree.search_nn([1, 2])) ```

Prints:

<KDNode - Item(3, 4, Second)> Second (<KDNode - Item(2, 3, First)>, 2.0)

Owner

Name: Stefan Kögl
Login: stefankoegl
Kind: user
Location: Austria

Repositories: 34
Profile: https://github.com/stefankoegl

GitHub Events

Total

Issues event: 1
Watch event: 6
Issue comment event: 1
Push event: 1

Last Year

Issues event: 1
Watch event: 6
Issue comment event: 1
Push event: 1

Committers

Last synced: about 1 year ago

All Time

Total Commits: 136
Total Committers: 15
Avg Commits per committer: 9.067
Development Distribution Score (DDS): 0.228

Past Year

Commits: 0
Committers: 0
Avg Commits per committer: 0.0
Development Distribution Score (DDS): 0.0

Top Committers

Name	Email	Commits
Stefan Kögl	s**n@s**t	105
Warwick Stone	u**o@g**m	7
CQY	q**n@p**n	4
Joachim Hagege	c**c@g**m	4
Jeffrey Finkelstein	j**n@g**m	3
RafiKueng	r**g@g**h	2
Denbeigh Stevens	d**h@d**m	2
Baudouin Raoult	b**t@e**t	2
grapemix	k**g@g**m	1
TennnyZhuang	z**6@g**m	1
Paulo Mello	p**o@g**m	1
Ilya Zverev	z**k@t**u	1
Eric SHI	l**n@g**m	1
Ben Regenspan	b**n@g**m	1
Emil Hernvall	e**l@q**t	1

Committer Domains (Top 20 + Academic)

quench.at: 1 textual.ru: 1 ecmwf.int: 1 denbeighstevens.com: 1 gmx.ch: 1 pku.edu.cn: 1 skoegl.net: 1

Issues and Pull Requests

Last synced: 11 months ago

All Time

Total issues: 30
Total pull requests: 25
Average time to close issues: 9 months
Average time to close pull requests: 3 months
Total issue authors: 23
Total pull request authors: 19
Average comments per issue: 2.17
Average comments per pull request: 1.68
Merged pull requests: 16
Bot issues: 0
Bot pull requests: 0

Past Year

Issues: 0
Pull requests: 1
Average time to close issues: N/A
Average time to close pull requests: N/A
Issue authors: 0
Pull request authors: 1
Average comments per issue: 0
Average comments per pull request: 0.0
Merged pull requests: 0
Bot issues: 0
Bot pull requests: 0

View more stats

Top Authors

Issue Authors

vincefernando (6)
dalippa (2)
nicky-zs (2)
joric (1)
Maryom (1)
ntamas (1)
fobdy (1)
nicolas-f (1)
jrtk (1)
cfdbwrbq (1)
hossin007 (1)
betterenvi (1)
Rhuax (1)
matburnham (1)
changle0703 (1)

Pull Request Authors

stefankoegl (3)
RafiKueng (2)
betterenvi (2)
jfinkels (2)
uozuAho (2)
qqwqqw689 (1)
zaaroth (1)
EmilHernvall (1)
ghost (1)
harish1996 (1)
denbeigh2000 (1)
TennyZhuang (1)
longwosion (1)
Copilot (1)
bregenspan (1)

Top Labels

Issue Labels

Pull Request Labels

Packages

Total packages: 2
Total downloads:
- pypi 87,105 last-month
Total docker downloads: 91

Total dependent packages: 3
(may contain duplicates)
Total dependent repositories: 321
(may contain duplicates)
Total versions: 17
Total maintainers: 1

pypi.org: kdtree

A Python implemntation of a kd-tree

Homepage: https://github.com/stefankoegl/kdtree
Documentation: https://kdtree.readthedocs.io/
License: ISC license
Latest release: 0.16
published almost 9 years ago

Versions: 15
Dependent Packages: 3
Dependent Repositories: 321
Downloads: 87,105 Last month
Docker Downloads: 91

Rankings

Dependent repos count: 0.8%

Docker downloads count: 2.7%

Average: 2.9%

Downloads: 3.1%

Dependent packages count: 3.2%

Stargazers count: 3.4%

Forks count: 4.3%

Maintainers (1)

skoegl

Last synced: 11 months ago

conda-forge.org: kdtree

Homepage: https://github.com/stefankoegl/kdtree
License: ISC
Latest release: 0.12
published over 7 years ago

Versions: 2
Dependent Packages: 0
Dependent Repositories: 0

Rankings

Forks count: 15.1%

Stargazers count: 19.3%

Average: 29.9%

Dependent repos count: 34.0%

Dependent packages count: 51.2%

Last synced: 11 months ago

Dependencies

requirements-dev.txt pypi

wheel * development

kdtree

Science Score: 10.0%

Repository

Basic Info

Statistics

Metadata Files

readme.md

A simple kd-tree in Python

Usage

Adding a payload

This class emulates a tuple, but contains a useful payload

Now we can add Items to the tree, which look like tuples to it

Again, from a list of points

The root node

...contains "data" field with an Item, which contains the payload in "data" field

All functions work as intended, a payload is never lost

Owner

GitHub Events

Total

Last Year

Committers

All Time

Past Year

Top Committers

Committer Domains (Top 20 + Academic)

Issues and Pull Requests

All Time

Past Year

Top Authors

Issue Authors

Pull Request Authors

Top Labels

Issue Labels

Pull Request Labels

Packages

pypi.org: kdtree

Rankings

Maintainers (1)

conda-forge.org: kdtree

Rankings

Dependencies