Tree-based geometric lookup

Area queries (Balls -> overlapping leaves)

class boxtree.area_query.AreaQueryBuilder(array_context: ArrayContext)

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.

Added in version 2016.1.

__init__(array_context: ArrayContext) → None

__call__(actx: ArrayContext, tree: Tree, ball_centers, ball_radii, peer_lists=None, wait_for=None)

Parameters:

• ball_centers – an object array of coordinates. Their dtype must match tree’s boxtree.Tree.coord_dtype.

• ball_radii – an array of positive numbers. Its dtype must match tree’s boxtree.Tree.coord_dtype.

• peer_lists – may either be None or an instance of PeerListLookup associated with tree.

• wait_for – may either be None or a list of pyopencl.Event instances for whose completion this command waits before starting execution.

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(tree: Tree, leaves_near_ball_starts: Array, leaves_near_ball_lists: Array)

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

Added in version 2016.1.

Inverse of area query (Leaves -> overlapping balls)

class boxtree.area_query.LeavesToBallsLookupBuilder(array_context: ArrayContext)

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.

__init__(array_context: ArrayContext) → None

__call__(actx: ArrayContext, tree: Tree, ball_centers, ball_radii, peer_lists=None, wait_for=None)

Parameters:

• ball_centers – an object array of coordinates. Their dtype must match tree’s boxtree.Tree.coord_dtype.

• ball_radii – an array of positive numbers. Its dtype must match tree’s boxtree.Tree.coord_dtype.

• peer_lists – may either be None or an instance of PeerListLookup associated with tree.

• wait_for – may either be None or a list of pyopencl.Event instances for whose completion this command waits before starting execution.

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(tree: Tree, balls_near_box_starts: Array, balls_near_box_lists: Array)

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

Space invader queries

class boxtree.area_query.SpaceInvaderQueryBuilder(array_context: ArrayContext)

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)\]

__init__(array_context: ArrayContext) → None

__call__(actx: ArrayContext, tree: Tree, ball_centers, ball_radii, peer_lists=None, wait_for=None)

Parameters:

• ball_centers – an object array of coordinates. Their dtype must match tree’s boxtree.Tree.coord_dtype.

• ball_radii – an array of positive numbers. Its dtype must match tree’s boxtree.Tree.coord_dtype.

• peer_lists – may either be None or an instance of PeerListLookup associated with tree.

• wait_for – may either be None or a list of pyopencl.Event instances for whose completion this command waits before starting execution.

Returns:

a tuple (sqi, event), where sqi is an 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(array_context: ArrayContext)

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.”

Added in version 2016.1.

__init__(array_context: ArrayContext) → None

__call__(actx: ArrayContext, tree: Tree, wait_for=None)

Parameters:

wait_for – may either be None or a list of pyopencl.Event instances for whose completion this command waits before starting execution.

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(tree: Tree, peer_list_starts: Array, peer_lists: Array)

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

Added in version 2016.1.