# Tree-based geometric lookup#

## Area queries (Balls -> overlapping leaves)#

class boxtree.area_query.AreaQueryBuilder(context)[source]#

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.

__init__(context)[source]#
__call__(queue, tree, ball_centers, ball_radii, peer_lists=None, wait_for=None)[source]#
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=None, **kwargs)[source]#
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)[source]#

Return a copy of self in which all data lives on the host, i.e. all pyopencl.array.Array and ImmutableHostDeviceArray 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)[source]#

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__(context)[source]#
__call__(queue, tree, ball_centers, ball_radii, peer_lists=None, wait_for=None)[source]#
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=None, **kwargs)[source]#
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)[source]#

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

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__(context)[source]#
__call__(queue, tree, ball_centers, ball_radii, peer_lists=None, wait_for=None)[source]#
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)[source]#

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.

New in version 2016.1.

__init__(context)[source]#
__call__(queue, tree, wait_for=None)[source]#
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=None, **kwargs)[source]#
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)[source]#

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

New in version 2016.1.