docs/doxygen/user/analysisnbsearch.md

   1 Neighborhood search for analysis tools {#page_analysisnbsearch}
   2 ======================================
   3
   4 The header nbsearch.h declares a C++ interface to a relatively flexible and
   5 efficient neighborhood search.  It is currently implemented within the
   6 selection module where it originated, but it does not have any dependencies on
   7 the other selection code and can be easily split out in the future.
   8
   9 The emphasis is on flexibility and ease of use; one main driver is to have
  10 one common implementation of grid-based searching to avoid replicating this in
  11 multiple tools (and to make more tools take advantage of the significant
  12 performance improvement this allows).  The main features that it provides:
  13
  14  - Grid-based searching with any triclinic box shape that \Gromacs supports
  15    (i.e., a triangular box matrix and not too skewed).
  16  - Grid-based searching with all PBC options except for screw boundary
  17    conditions.
  18  - With no PBC, grid-based searching where the grid is constructed based on the
  19    bounding box of the gridded atoms.
  20  - Efficient, rectangular grid cells whose size is determined by particle
  21    density and not limited by the cutoff.
  22  - Transparent fallback to a simple all-pairs search if the cutoff is too long
  23    for the algorithm or grid searching is not otherwise supported.
  24  - Support for computing all distances in the XY plane only (and still
  25    grid-based).
  26  - Convenience functions for finding the shortest distance or the nearest pair
  27    between two sets of positions.
  28  - Basic support for exclusions.
  29  - Thread-safe handling of multiple concurrent searches with the same cutoff
  30    with the same or different reference positions.
  31
  32 Usage
  33 =====
  34
  35 The neighborhood search works conceptually with two different sets of
  36 coordinates:
  37
  38  - _reference positions_: When initiating the search, you provide one set of
  39    reference positions that get placed on the search grid and determine the
  40    size of the grid.
  41  - _test positions_: For each set of reference positions, you provide a set of
  42    test positions (or a single position).  The search is performed from each
  43    test position, finding the reference positions within the cutoff from this
  44    point.  It is possible to perform multiple searches against the same set of
  45    reference positions (and the same grid).
  46
  47 To start using the neighborhood search, you need to first create an instance of
  48 gmx::AnalysisNeighborhood.  This class allows you to set some global properties
  49 for the search (most notably, the cutoff distance).  Then you provide the
  50 reference positions as a gmx::AnalysisNeighborhoodPositions and PBC information
  51 to get a gmx::AnalysisNeighborhoodSearch instance.  You can then either use
  52 methods directly in this class to find, e.g., the nearest reference point from
  53 a test position, or you can do a full pair search that returns you all the
  54 reference-test pairs within a cutoff.  The pair search is performed using an
  55 instance of gmx::AnalysisNeighborhoodPairSearch that the search object returns.
  56 Methods that return information about pairs return an instance of
  57 gmx::AnalysisNeighborhoodPair, which can be used to access the indices of
  58 the reference and test positions in the pair, as well as the computed distance.
  59 See the class documentation for these classes for details.
  60
  61 For use together with selections, an instance of gmx::Selection or
  62 gmx::SelectionPosition can be transparently passed as the positions for the
  63 neighborhood search.
  64
  65 Implementation
  66 ==============
  67
  68 This section provides a high-level overview of the algorithm used.  It is not
  69 necessary to understand all the details to use the API, but it can be useful to
  70 get the best performance out of it.  The main audience is developers who may
  71 need to extend the API to make it suitable for more cases.
  72
  73 The grid for the search is initialized based on the reference positions and the
  74 PBC information:
  75
  76  - The grid cells are always rectangular, even for fully triclinic boxes.
  77  - If there is no PBC, the grid edges are defined from the bounding box of the
  78    reference positions; with PBC, the grid covers the unit cell.
  79  - The grid cell size is determined such that on average, each cell contains
  80    ten particles.  Special considerations are in place for cases where the grid
  81    will only be one- or two-dimensional because of a flat box.
  82  - If the resulting grid has too few cells in some dimensions, the code
  83    falls back automatically to an all-pairs search.  For correct operation, the
  84    grid algorithm needs three cells in each dimension, but the code can fall
  85    back to a non-gridded search for each dimension separately.
  86  - If the resulting grid has so few cells that the search would anyways
  87    consider all (or nearly all) cell pairs, the search falls back to a
  88    simple search.
  89  - The initialization also pre-calculates the shifts required across the
  90    periodic boundaries for triclinic cells, i.e., the fractional number of
  91    cells that the grid origin is shifted when crossing the periodic boundary in
  92    Y or Z directions.
  93  - Finally, all the reference positions are mapped to the grid cells.
  94
  95 There are a few heuristic numbers in the above logic: the average number of
  96 particles within a cell, and the cutover point from grid to an all-pairs
  97 search.  These have not been particularly optimized for best performance.
  98
  99 When doing the search for test positions, each test position is considered
 100 independently:
 101
 102  - The coordinates of the test position are mapped to the grid coordinate
 103    system.  The coordinates here are fractional and may lay outside the grid
 104    for non-periodic dimensions.
 105  - The bounding box of the cutoff sphere centered at the mapped coordinates is
 106    determined, and each grid cell that intersects with this box is used for
 107    searching the reference positions.  So the searched grid cells may vary
 108    depending on the coordinates of the test position, even if the test position
 109    is within the same cell.
 110  - Possible triclinic shifts in the grid are considered when looping over the
 111    cells in the cutoff box if the coordinates wrap around a periodic dimension.
 112    This is done by shifting the search range in the other dimensions when the Z
 113    or Y dimension loop crosses the boundary.