A pure Python Quadtree implementation.
Project description
quads
A pure Python Quadtree implementation.
Quadtrees are a useful data structure for sparse datasets where the location/position of the data is important. They're especially good for spatial indexing & image processing.
An actual visualization of a quads.QuadTree
:
Usage
Full documentation at https://quads.readthedocs.io/en/latest/
>>> import quads
>>> tree = quads.QuadTree(
... (0, 0), # The center point
... 10, # The width
... 10, # The height
... )
# You can choose to simply represent points that exist.
>>> tree.insert((1, 2))
True
# ...or include extra data at those points.
>>> tree.insert(quads.Point(4, -3, data="Samus"))
True
# You can search for a given point. It returns the point if found...
>>> tree.find((1, 2))
Point(1, 2)
# Or `None` if there's no match.
>>> tree.find((4, -4))
None
# You can also find all the points within a given region.
>>> bb = quads.BoundingBox(min_x=-1, min_y=-2, max_x=2, max_y=2)
>>> tree.within_bb(bb)
[Point(1, 2)]
# You can also search to find the nearest neighbors of a point, even
# if that point doesn't have data within the quadtree.
>>> tree.nearest_neighbors((0, 1), count=2)
[
Point(1, 2),
Point(4, -4),
]
# And if you have `matplotlib` installed (not required!), you can visualize
# the tree.
>>> quads.visualize(tree)
Installation
$ pip install quads
Requirements
- Python 3.7+ (untested on older versions but may work)
Running Tests
$ git clone https://github.com/toastdriven/quads.git
$ cd quads
$ poetry install
$ poetry shell
# Just the tests.
$ pytest .
# With coverage.
$ pytest -s --cov=quads .
# And with pretty reports.
$ pytest -s --cov=quads . && coverage html
License
New BSD
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
quads-1.1.0.tar.gz
(9.6 kB
view details)
Built Distribution
quads-1.1.0-py3-none-any.whl
(9.4 kB
view details)
File details
Details for the file quads-1.1.0.tar.gz
.
File metadata
- Download URL: quads-1.1.0.tar.gz
- Upload date:
- Size: 9.6 kB
- Tags: Source
- Uploaded using Trusted Publishing? No
- Uploaded via: poetry/1.0.5 CPython/3.7.4 Darwin/19.5.0
File hashes
Algorithm | Hash digest | |
---|---|---|
SHA256 | 59c1d86e551a734ea83c61c185c84873cf604b54bbacdfdbce831067715ecc7e |
|
MD5 | a4b4379fadbddd3e8bcaae1688e79528 |
|
BLAKE2b-256 | 74c7257b7c30a7483e7cc699d0faf1695a04d3251f955789339a8d8f50c74008 |
Provenance
File details
Details for the file quads-1.1.0-py3-none-any.whl
.
File metadata
- Download URL: quads-1.1.0-py3-none-any.whl
- Upload date:
- Size: 9.4 kB
- Tags: Python 3
- Uploaded using Trusted Publishing? No
- Uploaded via: poetry/1.0.5 CPython/3.7.4 Darwin/19.5.0
File hashes
Algorithm | Hash digest | |
---|---|---|
SHA256 | 4f2a05381f07fdf6d61352b0893819b2c52ae2286211c74bd9639a28d6424540 |
|
MD5 | 808d7c3c9d1c350fa04f2cf981b28a2a |
|
BLAKE2b-256 | 0a18053514fdacc17ac4439496e44ccc99547e1672afce1536a2a8e84aacf5c2 |