Tree-based geometric lookup

Area queries (Balls -> overlapping leaves)

class boxtree.area_query.AreaQueryBuilder(context)

Given a set of \(l^\infty\) “balls”, this class helps build a look-up table from ball to leaf boxes that intersect with the ball.

New in version 2016.1.

__call__(queue, tree, ball_centers, ball_radii, peer_lists=None, wait_for=None)
Parameters:
Returns:

a tuple (aq, event), where aq is an instance of AreaQueryResult, and event is a pyopencl.Event for dependency management.

class boxtree.area_query.AreaQueryResult(valuedict=None, exclude=['self'], **kwargs)
tree

The boxtree.Tree instance used to build this lookup.

leaves_near_ball_starts

Indices into leaves_near_ball_lists. leaves_near_ball_lists[leaves_near_ball_starts[ball_nr]: leaves_near_ball_starts[ball_nr]+1] results in a list of leaf boxes that intersect ball_nr.

leaves_near_ball_lists
get(queue, **kwargs)

Return a copy of self in which all data lives on the host, i.e. all pyopencl.array.Array objects are replaced by corresponding numpy.ndarray instances on the host.

New in version 2016.1.

Inverse of area query (Leaves -> overlapping balls)

class boxtree.area_query.LeavesToBallsLookupBuilder(context)

Given a set of \(l^\infty\) “balls”, this class helps build a look-up table from leaf boxes to balls that overlap with each leaf box.

__call__(queue, tree, ball_centers, ball_radii, peer_lists=None, wait_for=None)
Parameters:
Returns:

a tuple (lbl, event), where lbl is an instance of LeavesToBallsLookup, and event is a pyopencl.Event for dependency management.

class boxtree.area_query.LeavesToBallsLookup(valuedict=None, exclude=['self'], **kwargs)
tree

The boxtree.Tree instance used to build this lookup.

balls_near_box_starts

Indices into balls_near_box_lists. balls_near_box_lists[balls_near_box_starts[ibox]: balls_near_box_starts[ibox]+1] results in a list of balls that overlap leaf box ibox.

Note

Only leaf boxes have non-empty entries in this table. Nonetheless, this list is indexed by the global box index.

balls_near_box_lists
get(queue, **kwargs)

Return a copy of self in which all data lives on the host, i.e. all pyopencl.array.Array objects are replaced by corresponding numpy.ndarray instances on the host.

Space invader queries

class boxtree.area_query.SpaceInvaderQueryBuilder(context)

Given a set of \(l^\infty\) “balls”, this class helps build a look-up table which maps leaf boxes to the outer space invader distance. This is defined below but roughly, from the point of view of a leaf box, it is the farthest “leaf center to ball center” distance among all balls that intersect the leaf box.

Formally, given a leaf box \(b\), the outer space invader distance is defined by the following expression (here \(d_\infty\) is the \(\infty\) norm):

\[\max \left( \{ d_{\infty}(\text{center}(b), \text{center}(b^*)) : b^* \text{ is a ball}, b^* \cap b \neq \varnothing \} \cup \{ 0 \} \right)\]
__call__(queue, tree, ball_centers, ball_radii, peer_lists=None, wait_for=None)
Parameters:
Returns:

a tuple (sqi, event), where sqi is an instance of pyopencl.array.Array, and event is a pyopencl.Event for dependency management. The dtype of sqi is tree’s boxtree.Tree.coord_dtype and its shape is (tree.nboxes,) (see boxtree.Tree.nboxes). The entries of sqi are indexed by the global box index and are as follows:

  • if i is not the index of a leaf box, sqi[i] = 0.
  • if i is the index of a leaf box, sqi[i] is the outer space invader distance for i.

Peer Lists

Area queries are implemented using peer lists.

class boxtree.area_query.PeerListFinder(context)

This class builds a look-up table from box numbers to peer boxes. The full definition [1] of a peer box is as follows:

Given a box \(b_j\) in a quad-tree, \(b_k\) is a peer box of \(b_j\) if it is

  1. adjacent to \(b_j\),
  2. of at least the same size as \(b_j\) (i.e. at the same or a higher level than), and
  3. no child of \(b_k\) satisfies the above two criteria.
[1]Rachh, Manas, Andreas Klöckner, and Michael O’Neil. “Fast algorithms for Quadrature by Expansion I: Globally valid expansions.”

New in version 2016.1.

__call__(queue, tree, wait_for=None)
Parameters:
Returns:

a tuple (pl, event), where pl is an instance of PeerListLookup, and event is a pyopencl.Event for dependency management.

class boxtree.area_query.PeerListLookup(valuedict=None, exclude=['self'], **kwargs)
tree

The boxtree.Tree instance used to build this lookup.

peer_list_starts

Indices into peer_lists. peer_lists[peer_list_starts[box_id]:peer_list_starts[box_id]+1] contains the list of peer boxes of box box_id.

peer_lists
get(queue, **kwargs)

Return a copy of self in which all data lives on the host, i.e. all pyopencl.array.Array objects are replaced by corresponding numpy.ndarray instances on the host.

New in version 2016.1.