#include <source/hierarchy/boxes/BoxTree.h>
Public Member Functions | |
BoxTree (const BoxArray< DIM > &boxes, const tbox::Array< tbox::List< IntVector< DIM > > > &box_shifts, const ProcessorMapping &box_mapping, int min_length=10) | |
Constructor for BoxTree. | |
BoxTree (const BoxArray< DIM > &boxes, const tbox::Array< tbox::List< IntVector< DIM > > > &box_shifts, int min_length=10) | |
BoxTree (const BoxArray< DIM > &boxes, int min_length=10) | |
~BoxTree () | |
void | findOverlapIndices (tbox::Array< int > &indices, const Box< DIM > &box) const |
Compute the indices of all boxes that overlap the specified box. | |
void | findLocalOverlapIndices (tbox::Array< int > &indices, const Box< DIM > &box) const |
Compute the indices of the boxes local to this processor that overlap the specified box. | |
void | findOverlapBoxes (BoxList< DIM > &overlap_boxes, const Box< DIM > &box) const |
Compute list of boxes that overlap the specified box. | |
void | removeIntersections (BoxList< DIM > &list) const |
Remove from list the portions that intersect the boxes in the BoxArray that was passed to the constructor. |
A BoxTree object is constructed by passing the ctor a BoxArray; this array is used internally to setup private data structures that will be used in subsequent methods, described below. If the BoxArray contains n boxes, then the setup phase (which is invoked by the constructor) has an expected runtime complexity of O(n log(n)).
Following construction, two types of operations are supported by the member functions findOverlapIndices() and findLocalOverlapIndices(). Each function takes an integer array and a box as input, and computes the indices of the subset of the boxes (in the array that was passed to the constructor) that overlap with the argument box. On return from the function, the integer array holds the indices of the boxes in the array that overlap with the argument box. The function findOverlapIndices() returns indices of all boxes that overlap the argument box. The function findLocalOverlapIndices() returns only the indices of the boxes that are assigned to this processor.
Second, the removeIntersections call takes a list of boxes as input, and removes those portions that intersect with the boxes in the BoxArray that was passed to the constructor.
This class provides functionality that is similar to that provided by the BoxTop and BoxGraph classes. However, it employs different algorithms to do so, and is expected to have different runtime characteristics. Questions such as "which is faster for removeIntersections(): BoxTop, BoxGraph, or BoxTree?" depends on many factors for which analysis is difficult. The answer is largely a function of a particular problem and domain topology, and is best answered experimentally.
|
Constructor for BoxTree. The primary difference between the constructors is that the first takes processor mapping information while the others do not. This is because processor mapping information is required in the method findLocalOverlapIndices(), but is not required for the other methods. If you do not pass processor mappying information, and subsequently call findLocalOverlapIndices(), an unrecoverable assertion will be thrown.
|
|
|
|
|
|
The dtor does nothing interesting. |
|
Compute the indices of all boxes that overlap the specified box. The integer array will contain the indices of all boxes (in the BoxArray that was passed to the constructor) and that overlap the specified box.
|
|
Compute the indices of the boxes local to this processor that overlap the specified box. The integer array will contain the indices of the boxes (in the BoxArray that was passed to the constructor) and that overlap the specified box and which are assigned to this processor. The processor assignment is determined from the mapping information passed to the constructor. This routine will result in an unrecoverable exception if a constructor that does not accept the mapping information was used to create this object. See the comments for the constructors.
|
|
Compute list of boxes that overlap the specified box.
|
|
Remove from list the portions that intersect the boxes in the BoxArray that was passed to the constructor. CAUTION: the semantics of this call differ from that of BoxList::removeIntersections(const BoxList<DIM> takeaway). Here, the list that is being modified is the list that is passed as an argument; the "takeaway" list is the list that was passed when the BoxTop object was constructed.
|