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.

Added 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: Mapping[str, Any] | None = None, exclude: Sequence[str] | None = None, **kwargs: Any)[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.

Added 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: Mapping[str, Any] | None = None, exclude: Sequence[str] | None = None, **kwargs: Any)[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.

Space invader queries¶

class boxtree.area_query.SpaceInvaderQueryBuilder(context)[source]¶

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.

Added 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: Mapping[str, Any] | None = None, exclude: Sequence[str] | None = None, **kwargs: Any)[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.

Added in version 2016.1.