nontree

nontree

A python package for n-tree 2D data structures similar to and including quadtree, with mapping to payload data
Explore the docs »

Report Bug · Request Feature

Table of Contents

1. About The Project
2. Getting Started
   • Prerequisites
   • Installation
   • Demo
3. Usage
• Data Types
• Constructing A TreeMap
• Adding Data Points To A TreeMap
• Collision Detection
4. Contributing
5. Testing
6. License
7. Project Links

About The Project

This package implements quadtree-like data structures in the classes NonTree, QuadTree and BiTree. More precisely speaking, point-region (PR) quadtrees and variants thereof are implemented. It also provides the class TreeMap to map points from the tree to arbitrary payload data, with a dictionary-like interface.

A point-region quadtree is a recursive data structure to contain points that lie on a two dimensional surface. It allows for efficient collision detection between the containend points and an area. Thus it can answer the question "Which points are within that rectangular area?".

In comparision to looping over all points and comparing the location of each point with the rectangular boundaries, a quadtree delivers the answer in O(log(n)) instead of O(n).

This implementation also provides methods for circular collision detection.

An exemplary application could be to test elements on a map of a 2D game, before rendering each frame, whether they are in the screen area and thus must be drawn, or if the time of drawing them can be saved due to them not beeing in a visible area anyway.

For more information about quadtrees in general, see the Wikipedia article. Or more specifically the paragraph about point region quadtrees.

A quadtree (4-tree) is split into 4 subtrees, if its bucket capacity is full and additional points are added. Thus, it's area gets split into 4 quadrants. The points then are stored in the subtrees, until they are at capacity and get split as well. That's the well known quadtree data structure. This package also implements two unusual variants thereof: The non-tree (9-tree) and the alternating bi-tree (2-tree).

The quadtree splits each tree into 9 segments in a 3 by 3 grid. Due to reduced nesting depth, the retrieval of colliding points can be faster on a densely populated surface.

The bitree splits each tree in only 2 segments, alternatingly horizontally or vertically. This tends to result in a higher nesting depth. But at each level, only two instead of four or nine subtrees have to be considered. Thus it can be faster on a very sparsely populated surface.

The class TreeMap internally contains a NonTree (the default) or a QuadTree or BiTree. It maps the points of the tree to payload data. This allows the retrieval of objects that lie in the searched area.

If no payload data is needed, and only the bare points are of interest, the tree classes can be used directly.

Additionally, a module visualize exists, to plot a graph of the layout of a tree with the help of matplotlib.

Getting Started

Install the package, import a module, and call a function.

Prerequisites

This is a package for python3 (>=3.10). Slightly older versions of python3 might work, but are entirely untested.

The package has no mandatory dependencies of other external packages, but it optionally can make use of the follwing, if present:

• matplotlib to plot graphs of the tree layout, such as the one shown above. It is used by the module visualize.
• numba to speed up (jit-compile) some of the calculations for circular collision detection. It gets detected/used automatically, without need for configuration or passing options.

Installation

You can get the raw files from the git repository:

git clone https://github.com/iehgit/nontree.git

It's easier to install the package with pip:

pip install nontree

Demo

To see that the package has been installed and is accessible, you could plot a demo graph, if you also have matplotlib available:

>>> from nontree import visualize
>>> visualize.plot_demo()
>>>

Or you could simply construct a TreeMap, set a datapoint, and get back its data:

>>> from nontree.TreeMap import TreeMap
>>> tree_map = TreeMap((0, 0, 100, 100))
>>> tree_map[(50, 50)] = 'Hello World!'
>>> tree_map[(50, 50)]
'Hello World!'
>>>

Usage

Data Types

Points are defined as tuples in the shape of (x, y).
Data points are defined as tuples in the shape of (point, data), i.e. ((x, y), data), with data beeing any arbitrary object.
Rectangular areas are defined as tuples in the shape of (x, y, width, height), or anything that can be indexed in the same way. This allows the use of pygame.Rect.
Circular areas are defined as tuples in the shape of (x, y, radius).

Constructing A TreeMap

A TreeMap can be constructed like this, with a rectangle as its first parameter to specify its surface:

from nontree.TreeMap import TreeMap

tree_map = TreeMap((0, 0, 100, 100))

Per default, it contains a NonTree. To specify the tree type, you can use the keyword argument mode, like this:

from nontree.TreeMap import TreeMap

tree_map_foo = TreeMap((0, 0, 100, 100), mode=9)  # NonTree
tree_map_bar = TreeMap((0, 0, 100, 100), mode=4)  # QuadTree
tree_map_baz = TreeMap((0, 0, 100, 100), mode=2)  # BiTree

Adding Data Points To A TreeMap

To add multiple data points:

from nontree.TreeMap import TreeMap

a_lot_of_datapoints = [((2, 3), 'dog'), ((17, 80), 'cat'), ((45, 13), 'fish'), ((99, 77), 'rat')]

tree_map = TreeMap((0, 0, 100, 100))
tree_map.add_datapoints(a_lot_of_datapoints)

To add a single data point, the dict-like interface is convenient:

from nontree.TreeMap import TreeMap

tree_map = TreeMap((0, 0, 100, 100))
tree_map[(55, 89)] = 'goat'

Collision Detection

To query the data within an rectangular area of the surface, you can use the method get_rect, which takes a rectangle as its parameter:

from nontree.TreeMap import TreeMap

a_lot_of_datapoints = [((2, 3), 'dog'), ((17, 80), 'cat'), ((45, 13), 'fish'), ((99, 77), 'rat')]

tree_map = TreeMap((0, 0, 100, 100))
tree_map.add_datapoints(a_lot_of_datapoints)
tree_map[(55, 89)] = 'goat'

result = tree_map.get_rect((4, 4, 80, 80))
print(result)

Output of the above:

['fish', 'cat']

For more details, please refer to the Documentation.

Contributing

Contributions are what make the open source community such an amazing place to learn, inspire, and create. Any contributions you make are greatly appreciated.

If you have a suggestion that would make this better, please fork the repo and create a pull request. Please make sure that all unit tests still pass after any changes.

1. Fork the Project
2. Create your Feature Branch (git checkout -b feature/AmazingFeature)
3. Commit your Changes (git commit -m 'Add some AmazingFeature')
4. Push to the Branch (git push origin feature/AmazingFeature)
5. Open a Pull Request

You can also simply open an issue with the tag "enhancement".

Testing

To run the unit tests:

cd tests
PYTHONPATH=../src python3 utest.py 

The output should look roughly similar to this:

......................................
-------------------------------------------------------------------------------
Ran 38 tests in 0.308s

PASSED (successes=38)

License

Distributed under the MIT License. See LICENSE for more information.

Project Links

Github

PyPI

API documentation