cQuadTree 0.0.2

Python API to a C++-implementation of a BarnesHutTree/QuadTree

Infinite jest with your favorite space-dividing trees. Fork from this C++-codebase: https://github.com/benmaier/BarnesHutTree/

• repository: https://github.com/benmaier/cQuadTree/

>>> from cQuadTree import QuadTree
>>> points = [
...             (1.0, 2.0),
...             (0.1, 10.0),
...             (0.5, 7.4),
...             (6.0, 0.7),
...          ]
>>> T = QuadTree(points)
>>> T
QuadTree(
    geom=Extent(left=0.1,bottom=0.7,width=9.3,height=9.3),
    current_data_quadrant=-1,
    is_leaf=False,
    number_of_contained_points=4,
    center_of_mass=Point(x=1.9,y=5.025),
    total_mass=4,
    total_mass_position=Point(x=7.6,y=20.1),
    number_of_occupied_subtrees=3
)
>>> print(T)
+- CM = 1.9, 5.025; M = 4; n = 4
| +- (nw) CM = 0.3, 8.7; M = 2; n = 2
| | +- (nw) 1 (0.1, 10)
| | +- (sw) 2 (0.5, 7.4)
| +- (se) 3 (6, 0.7)
| +- (sw) 0 (1, 2)

Install

Your machine needs to have a C++11-compatible compiler installed.

pip install cQuadTree

So far, the package’s functionality was tested on Mac OS X and CentOS only.

Dependencies

cQuadTree directly depends on the following packages which will be installed by pip during the installation process

• numpy>=1.20

Documentation

Build the tree

import numpy as np
from cQuadTree import QuadTree
points = np.random.rand(100,2).tolist()
T = QuadTree(points)

Explore the tree recursively

As an example, here’s a recursive function that collects all internal node boxes and leaf’s points

def get_points_and_boxes(quadtree):
    points = []
    boxes = []
    if quadtree.is_leaf():
        points.append(quadtree.this_pos)
    boxes.append(quadtree.geom)
    for tree in quadtree.get_subtrees():
        _points, _boxes = get_points_and_boxes(tree)
        points.extend(_points)
        boxes.extend(_boxes)

    return points, boxes

Compute the force on a point

>>> T.compute_force(point=(0.,0.001),theta=1.0) # default is theta=0.5
(0.117681690892212, 0.20856460584929215)

Get all distances to a point

Note that per default, distances of value zero will be disregarded. If you want to include those, set ignore_zero_distance=False in the function call.

>>> T.get_distances_to((0.,0),theta=1) # default is theta=0.2
[(8.705170877128145, 2), (6.040695324215583, 1), (2.23606797749979, 1)]

The first number is the distance to the query point, the second is the number of points that lie at this approximate distance to the query point.

Get all distances between pairs of points in a list and points in the tree

>>> T.get_distances_to_points(points,theta=1)
[(6.7364679172397155, 2), (5.166236541235796, 1), (2.630589287593181, 1), (11.013627921806693, 1), (8.050465825031493, 1), (2.630589287593181, 1), (8.668333173107735, 1), (5.4230987451825, 1), (9.822932352408825, 2), (5.166236541235796, 1)]

Get all pairwise distances between points in the tree

>>> T.get_pairwise_distances(theta=1.0)
[(2.630589287593181, 1), (11.013627921806693, 1), (8.050465825031493, 1), (2.630589287593181, 1), (8.668333173107735, 1), (5.4230987451825, 1), (9.822932352408825, 2), (5.166236541235796, 1), (6.7364679172397155, 2), (5.166236541235796, 1)]

Build a distance histogram from distance counts

from cQuadTree import histogram
dists, counts = zip(*T.get_pairwise_distances(theta=1.0))
bin_edges = np.logspace(-4,1/2,101,base=2)
pdf, _ = histogram(dists, counts, bin_edges)

Plot tree as boxes and points

from cQuadTree import get_points_and_boxes
from cQuadTree.plot import plot_box_tree

plot_box_tree(*get_points_and_boxes(T))

Docstrings

QuadTree

Help on class QuadTree in module _cQuadTree:

class QuadTree(pybind11_builtins.pybind11_object)
 |  A QuadTree.
 |
 |  Method resolution order:
 |      QuadTree
 |      pybind11_builtins.pybind11_object
 |      builtins.object
 |
 |  Methods defined here:
 |
 |  __init__(...)
 |      __init__(*args, **kwargs)
 |      Overloaded function.
 |
 |      1. __init__(self: _cQuadTree.QuadTree) -> None
 |
 |      Initialize an empty tree.
 |
 |      2. __init__(self: _cQuadTree.QuadTree, position_pairs: List[Tuple[float, float]], force_square: bool = True) -> None
 |
 |      Initialize a tree given a list of positions.
 |
 |      3. __init__(self: _cQuadTree.QuadTree, position_pairs: List[Tuple[float, float]], masses: List[float], force_square: bool = True) -> None
 |
 |      Initialize a tree given a list of positions and a list of corresponding masses.
 |
 |  __repr__(...)
 |      __repr__(self: _cQuadTree.QuadTree) -> str
 |
 |      Get string representation of object
 |
 |  __str__(...)
 |      __str__(self: _cQuadTree.QuadTree) -> str
 |
 |      Get a string representation of the full tree
 |
 |  compute_force(...)
 |      compute_force(self: _cQuadTree.QuadTree, point: Tuple[float, float], theta: float = 0.5) -> Tuple[float, float]
 |
 |
 |      Compute the force on a single point using the Barnes-Hut-Algorithm
 |      with cutoff parameter :math:`\theta`.
 |
 |      Parameters
 |      ----------
 |      point : 2-tuple of float
 |          Point in plane on which to compute the total force
 |      theta : float, default = 0.5
 |          If the distance between the point and the current internal node's
 |          center of mass is smaller than :math:`\theta` times the diameter
 |          of the internal node's extent (box), the algorithm will treat
 |          all children of this node as a giant point mass located at the
 |          center of mass of this internal node.
 |
 |      Returns
 |      -------
 |      force : 2-tuple of float
 |          Evaluated force vector
 |
 |  get_distances_to(...)
 |      get_distances_to(self: _cQuadTree.QuadTree, point: Tuple[float, float], theta: float = 0.2, ignore_zero_distance: bool = True, tree: _cQuadTree.QuadTree = None) -> List[Tuple[float, int]]
 |
 |
 |      Compute distances of point masses and mass clusters to a single point
 |      using the Barnes-Hut-Algorithm with cutoff parameter :math:`\theta`.
 |
 |      Parameters
 |      ----------
 |      point : 2-tuple of float
 |          Points in the plane to which to measure the distances
 |      theta : float, default = 0.2
 |          If the distance between the point and the current internal node's
 |          center of mass is smaller than :math:`\theta` times the diameter
 |          of the internal node's extent (box), the algorithm will treat
 |          all children of this node as a giant point mass located at the
 |          center of mass of this internal node.
 |      ignore_zero_distance : bool, default = True
 |          If the distance is zero, do or do not include this result in
 |          the ``distance_counts``-list.
 |
 |      Returns
 |      -------
 |      distance_counts : list of 2-tuple of double, int
 |          An item of this list is a distance-count pair,
 |          the first entry of the tuple containing a distance
 |          to the query point and the second entry being the
 |          number of points that lie at that approximate distance
 |          to the query point, such that it will look like this
 |
 |          .. code:: python
 |
 |              [
 |                  (0.2, 1),
 |                  (0.1, 1),
 |                  (1.5, 32),
 |                  ...
 |              ]
 |
 |  get_distances_to_points(...)
 |      get_distances_to_points(self: _cQuadTree.QuadTree, points: List[Tuple[float, float]], theta: float = 0.2, ignore_zero_distance: bool = True, tree: _cQuadTree.QuadTree = None) -> List[Tuple[float, int]]
 |
 |
 |      Compute distances of point masses and mass clusters to a list of points
 |      using the Barnes-Hut-Algorithm with cutoff parameter :math:`\theta`.
 |
 |      Parameters
 |      ----------
 |      points : 2-tuple of float
 |          List of points in the plane to which to measure the distances
 |      theta : float, default = 0.2
 |          If the distance between the point and the current internal node's
 |          center of mass is smaller than :math:`\theta` times the diameter
 |          of the internal node's extent (box), the algorithm will treat
 |          all children of this node as a giant point mass located at the
 |          center of mass of this internal node.
 |      ignore_zero_distance : bool, default = True
 |          If the distance is zero, do or do not include this result in
 |          the ``distance_counts``-list.
 |
 |      Returns
 |      -------
 |      distance_counts : list of 2-tuple of double, int
 |          An item of this list is a distance-count pair,
 |          the first entry of the tuple containing a distance
 |          to the query point and the second entry being the
 |          number of points that lie at that approximate distance
 |          to the query point, such that it will look like this
 |
 |          .. code:: python
 |
 |              [
 |                  (0.2, 1),
 |                  (0.1, 1),
 |                  (1.5, 32),
 |                  ...
 |              ]
 |
 |  get_pairwise_distances(...)
 |      get_pairwise_distances(self: _cQuadTree.QuadTree, theta: float = 0.2, ignore_zero_distance: bool = True) ->
List[Tuple[float, int]]
 |
 |
 |      Compute distances between pairs of points and point clusters
 |      of a tree using the Barnes-Hut-Algorithm with cutoff parameter
 |      :math:`\theta`.
 |
 |      Iterates over points by querying the tree recursively, which
 |      might take longer than simply externally iterating over a list of points
 |      if they're known.
 |
 |      Parameters
 |      ----------
 |      theta : float, default = 0.2
 |          If the distance between the point and the current internal node's
 |          center of mass is smaller than :math:`\theta` times the diameter
 |          of the internal node's extent (box), the algorithm will treat
 |          all children of this node as a giant point mass located at the
 |          center of mass of this internal node.
 |      ignore_zero_distance : bool, default = True
 |          If the distance is zero, do or do not include this result in
 |          the ``distance_counts``-list.
 |
 |      Returns
 |      -------
 |      distance_counts : list of 2-tuple of double, int
 |          An item of this list is a distance-count pair,
 |          the first entry of the tuple containing a distance
 |          to the query point and the second entry being the
 |          number of points that lie at that approximate distance
 |          to the query point, such that it will look like this
 |
 |          .. code:: python
 |
 |              [
 |                  (0.2, 1),
 |                  (0.1, 1),
 |                  (1.5, 32),
 |                  ...
 |              ]
 |
 |  get_subtree(...)
 |      get_subtree(self: _cQuadTree.QuadTree, arg0: int) -> _cQuadTree.QuadTree
 |
 |      Get subtree 0<=i<=3.
 |
 |  get_subtrees(...)
 |      get_subtrees(self: _cQuadTree.QuadTree) -> List[_cQuadTree.QuadTree]
 |
 |      Get a list of all of this node's children that contain data.
 |
 |  is_leaf(...)
 |      is_leaf(self: _cQuadTree.QuadTree) -> bool
 |
 |      Whether or not this node is a leaf.
 |
 |  ----------------------------------------------------------------------
 |  Data descriptors defined here:
 |
 |  center_of_mass
 |      Mass-weighted mean position of all points contained in this internal node.
 |
 |  current_data_quadrant
 |      Quadrant of the parent geometry the data of this tree resides in.
 |
 |  geom
 |      Extent of box this tree represents.
 |
 |  number_of_contained_points
 |      Number of points contained in this internal node.
 |
 |  parent
 |      The parent of this internal node.
 |
 |  this_id
 |      Data index of the point contained in this leaf.
 |
 |  this_mass
 |      Mass the point contained in this leaf.
 |
 |  this_pos
 |      Position of the point contained in this leaf.
 |
 |  total_mass
 |      Total mass of all points contained in this internal node.
 |
 |  total_mass_position
 |      Sum of product of mass and position of all points contained in this internal node.
 |

Extent

class Extent(pybind11_builtins.pybind11_object)
 |  A rectangular geometry.
 |
 |  Method resolution order:
 |      Extent
 |      pybind11_builtins.pybind11_object
 |      builtins.object
 |
 |  Methods defined here:
 |
 |  __init__(...)
 |      __init__(*args, **kwargs)
 |      Overloaded function.
 |
 |      1. __init__(self: _cQuadTree.Extent) -> None
 |
 |      Initializes a zero-dimensional box.
 |
 |      2. __init__(self: _cQuadTree.Extent, left: float, bottom: float, width: float, height: float) -> None
 |
 |      Initialize with position of bottom left corner, as well as width and height.
 |
 |  __repr__(...)
 |      __repr__(self: _cQuadTree.Extent) -> str
 |
 |      Get string representation of object
 |
 |  b(...)
 |      b(self: _cQuadTree.Extent) -> float
 |
 |  bottom(...)
 |      bottom(self: _cQuadTree.Extent) -> float
 |
 |  h(...)
 |      h(self: _cQuadTree.Extent) -> float
 |
 |  height(...)
 |      height(self: _cQuadTree.Extent) -> float
 |
 |  l(...)
 |      l(self: _cQuadTree.Extent) -> float
 |
 |  left(...)
 |      left(self: _cQuadTree.Extent) -> float
 |
 |  w(...)
 |      w(self: _cQuadTree.Extent) -> float
 |
 |  width(...)
 |      width(self: _cQuadTree.Extent) -> float

Point

class Point(pybind11_builtins.pybind11_object)
 |  Minimal 2D-vector implementation based on code by openFrameworks
 |
 |  Method resolution order:
 |      Point
 |      pybind11_builtins.pybind11_object
 |      builtins.object
 |
 |  Methods defined here:
 |
 |  __init__(...)
 |      __init__(*args, **kwargs)
 |      Overloaded function.
 |
 |      1. __init__(self: _cQuadTree.Point) -> None
 |
 |      2. __init__(self: _cQuadTree.Point, x: float, y: float) -> None
 |
 |      Initialize with coordinates
 |
 |  __repr__(...)
 |      __repr__(self: _cQuadTree.Point) -> str
 |
 |      Get string representation of object
 |
 |  length(...)
 |      length(self: _cQuadTree.Point) -> float
 |
 |      Get the length of the vector
 |
 |  ----------------------------------------------------------------------
 |  Data descriptors defined here:
 |
 |  x
 |
 |  y

Histogram

>>> from cQuadTree import histogram
>>> help(histogram)

histogram(data, counts, bin_edges, density=True)
    Returns a histogram from distance count data
    received from a tree.

    Parameters
    ==========
    data : numpy.ndarray of float
        Distances
    counts : numpy.ndarray of int
        Corresponding counts of distances in ``data``.
    bin_edges : numpy.ndarray
        Edges of bins for which the histogram should be computed
    density : boolean, default = True
        Whether or not to make the histogram a probability density

    Returns
    =======
    hist : numpy.ndarray
        Either count of data in bins, or pdf, will have length
        ``len(bin_edges)-1``.
    bin_edges : numpy.ndarray
        The used bin edges

Get points and boxes

>>> from cQuadTree.utils import get_points_and_boxes
>>> help(get_points_and_boxes)

get_points_and_boxes(quadtree)
    Returns two lists, one filled with "Extent" objects
    representing the boxes of the tree that are occupied,
    the other one contains the points that are located at
    the leaf nodes

    Parameters
    ==========
    quadtree : :class:`_cQuadTree.QuadTree`
        Self-explanatory, no?

    Returns
    =======
    points : list of :class:`_cQuadTree.Point`
        Points located at the leaves ot the tree
    boxes : list of :class:`_cQuadTree.Extent`
        The boxes that internal tree nodes represent

Plot boxes

>>> from cQuadTree.plot import plot_box_tree
>>> help(plot_box_tree)

plot_box_tree(list_of_points, list_of_boxes, ax=None, box_kwargs={}, point_kwargs={})
    Plot a graphical representation of the tree as boxes and points on a matplotlib.Axes.

    Use with data obtained from :func:`cQuadTree.utils.get_points_and_boxes`.

Changelog

Changes are logged in a separate file.

License

This project is licensed under the MIT License. Note that this excludes any images/pictures/figures shown here or in the documentation.

Contributing

If you want to contribute to this project, please make sure to read the code of conduct and the contributing guidelines. In case you’re wondering about what to contribute, we’re always collecting ideas of what we want to implement next in the outlook notes.

Dev notes

Fork this repository, clone it, and install it in dev mode.

git clone [e-mail]:YOURUSERNAME/cQuadTree.git
make

If you want to upload to PyPI, first convert the new README.md to README.rst

make readme

It will give you warnings about bad .rst-syntax. Fix those errors in README.rst. Then wrap the whole thing

make pypi

It will probably give you more warnings about .rst-syntax. Fix those until the warnings disappear. Then do

make upload