source: src/documentation/constructs/linkedcell.dox@ 8c9cce

/*
 * Project: MoleCuilder
 * Description: creates and alters molecular systems
 * Copyright (C)  2010 University of Bonn. All rights reserved.
 * Please see the LICENSE file or "Copyright notice" in builder.cpp for details.
 */

/**
 * \file linkedcell.dox
 *
 * Created on: Nov 15, 2011
 *    Author: heber
 */

/** \page linkedcell Linked Cell structure
 *
 *  The linked cell ansatz is used to obtain neighborhoods of particles in
 *  \f${\cal R}^3\f$ more quickly than in \f${\cal O}(N^2)\f$ if \f$ N \f$ is
 *  the number of particles. We require a maximum length, beyond which no more
 *  neighbors are sought. With this length we place a mesh on top of our space
 *  and associate each particle with a specific cell in this three-dimensional
 *  mesh, i.e. per cell we have a linked list containing references to all
 *  particles that are located in this cell (i.e. whose coordinates are bounded
 *  from above and below per coordinate axis by the cell's intervals). Eventually
 *  this allows for a complexity of \f${\cal O}(N \log N)\f$.
 *
 *  \section linkedcell-structure Code structure
 *
 *  The code is structured as a Model-View-Controller ansatz. The reason is as
 *  follows: The required edge length is not known at compilation but is a
 *  value depending on run-time variables. However, we must not re-initiate a
 *  linked cell structure whenever a slightly different edge length is requested.
 *  Instead we may use an already present linked cell instance that more or
 *  less (via some heuristic) matches the desired edge length. This slightly
 *  degrades asymptotic performance but enhances pre-asymptotics because we
 *  don't have to re-build a linked cell instance each and every time.
 *
 *  We briefly explain
 *  each part:
 *  -# \link LinkedCell_Model Model\endlink:
 *    The model represents a certain representation of the data( here a
 *    specific edge length), i.e. it is a specific instantiation of a linked
 *    cell structure.
 *  -# \link LinkedCell_Controller Controller\endlink:
 *    The controller contains the heuristic criterion and all
 *    present linked cell instances. It decides when new ones are required and
 *    when old ones are no longer needed.
 *  -# \link LinkedCell_View View\endlink:
 *    The view is the interface of the whole to the outside, here the
 *    user requests high-level functions, such as getAllNeighbours. How these
 *    are then performed is none-of-his-business but encapsulated below.
 *
 * This ansatz makes it possible to even implemented k-Nearest-Neighbor trees
 * instead of a linked cell ansatz if it is more convenient (e.g. if constant
 * updates are required). A single cell of the linked cell array is implemented
 * in LinkedCell for greater convenience, e.g. we store the array indices there
 * and may add further commodity functions.
 *
 *
 * \section linkedcell-howto How to use the code
 *
 * In this section we explain how you, as the user, is supposed to use the code.
 *
 * The following snippet gives you access to the linked cell interface.
 * \code
    LinkedCell_View &interface = World::getInstance().getLinkedCell(double distance);
 * \endcode
 * where distance is the desired edge length for the linked cell construct (e.g.
 * the maximum distance where you want neighbors to be returned).
 *
 * Now, you can access its functions as simply as
 * \code
    LinkedList &list = interface.getAllNeighbours(4., Vector(0.,0.,0.));
 * \endcode
 * which returns a LinkedList, i.e. a set of points, that reside in a sphere
 * around the origin of radius 4. where the boundary conditions apply as are
 * current in the Box stored in the World:
 * \code
   World::getInstance().getDomain()
 * \endcode
 *
 * You can iterate over the LinkedList as follows:
 * \code
    if (!ListOfNeighbors.empty()) {
      // we have some possible candidates, go through each
      for (LinkedCell::LinkedList::const_iterator neighboriter = ListOfNeighbors.begin();
          neighboriter != ListOfNeighbors.end();
          ++neighboriter) {
        const atom * const OtherWalker = dynamic_cast<const atom *>(*neighboriter);
        ASSERT(OtherWalker != NULL,
            "__func__ - TesselPoint "
            +(*neighboriter)->getName()+" that was not an atom retrieved from LinkedList");
         ...

        }
      }
 * \endcode
 * Note that we dynamically cast the TesselPoint to its more involved class atom which is
 * in general ok as only atoms are contained in LinkedCell constructs.
 *
 * \date 2011-11-30
 *
 */