Merge VR_bitmap

git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/bitmap@1074 636b058d-ea47-450e-bf9e-a15bfbe3eedb

Former-commit-id: 4c9ac225ffcfb924371c72fccc44cbd6ecb3d6e3

1 files changed, 93 insertions, 67 deletions

diff --git a/src/Bitmap_cubical_complex/doc/Gudhi_Cubical_Complex_doc.h b/src/Bitmap_cubical_complex/doc/Gudhi_Cubical_Complex_doc.h
index 00b39f01..cde0b2fc 100644
--- a/src/Bitmap_cubical_complex/doc/Gudhi_Cubical_Complex_doc.h
+++ b/src/Bitmap_cubical_complex/doc/Gudhi_Cubical_Complex_doc.h
@@ -21,64 +21,87 @@
  */

 

 

-#pragma once

+#ifndef DOC_GUDHI_CUBICAL_COMPLEX_COMPLEX_H_

+#define DOC_GUDHI_CUBICAL_COMPLEX_COMPLEX_H_

 

-namespace Gudhi

-{

+namespace Gudhi {

 

-namespace Cubical_complex

-{

+namespace Cubical_complex {

 

 /**  \defgroup cubical_complex Cubical complex

-*

-* \author   Pawel Dlotko

-*

-* @{

-*

-

-*Bitmap_cubical_complex is an example of a structured complex useful in computational mathematics (specially rigorous numerics) and image analysis. The presented implementation of cubical complexes is based on the following definition.

-*

-* An <em>elementary interval</em> is an interval of a form \f$ [n,n+1] \f$, or \f$[n,n]\f$, for \f$ n \in \mathcal{Z} \f$. The first one is called <em>non-degenerate</em>, while the second one is \a degenerate interval. A <em>boundary of a elementary

-*interval</em> is a chain  \f$\partial [n,n+1] = [n+1,n+1]-[n,n] \f$ in case of non-degenerate elementary interval and \f$\partial [n,n] = 0 \f$ in case of degenerate elementary interval. An <em>elementary cube</em> \f$ C \f$ is a

+ *

+ * \author   Pawel Dlotko

+ *

+ * @{

+ *

 

-*product of elementary intervals, \f$C=I_1 \times \ldots \times I_n\f$. <em>Embedding dimension</em> of a cube is n, the number of elementary intervals (degenerate or not) in the product. A <em>dimension of a cube</em> \f$C=I_1 \times ... \times I_n\f$ is the

-*number of non degenerate elementary intervals in the product. A <em>boundary of a cube</em> \f$C=I_1 \times \ldots \times I_n\f$ is a chain obtained in the following way:

-*\f[\partial C = (\partial I_1 \times \ldots \times I_n) + (I_1 \times \partial I_2 \times \ldots \times I_n) + \ldots + (I_1 \times I_2 \times \ldots \times \partial I_n).\f]

-*A <em>cubical complex</em> \f$\mathcal{K}\f$ is a collection of cubes closed under operation of taking boundary (i.e. boundary of every cube from the collection is in the collection). A cube \f$C\f$ in cubical complex \f$\mathcal{K}\f$ is <em>maximal</em> if it is not in

-*a boundary of any other cube in \f$\mathcal{K}\f$. A \a support of a cube \f$C\f$ is the set in \f$\mathbb{R}^n\f$ occupied by \f$C\f$ (\f$n\f$ is the embedding dimension of \f$C\f$).

-*

-*Cubes may be equipped with a filtration values in which case we have filtered cubical complex. All the cubical complexes considered in this implementation are filtered cubical complexes (although, the range of a filtration may be a set of two elements).

-*

-*For further details and theory of cubical complexes, please consult \cite kaczynski2004computational as well as the following paper \cite peikert2012topological .

-*

-*\section datastructure Data structure.

-*

-*The implementation of Cubical complex provides a representation of complexes that occupy a rectangular region in \f$\mathbb{R}^n\f$. This extra

-*assumption allows for a memory efficient way of storing cubical complexes in a form of so called bitmaps. Let \f$R = [b_1,e_1] \times \ldots \times [b_n,e_n]\f$, for \f$b_1,...b_n,e_1,...,e_n \in \mathbb{Z}\f$

-*, \f$b_i \leq d_i\f$ be the considered rectangular region and let \f$\mathcal{K}\f$ be a filtered cubical complex having the rectangle \f$R\f$ as its support. Note that the structure of the coordinate system gives a way

-*a lexicographical ordering of cells of \f$\mathcal{K}\f$. This ordering is a base of the presented bitmap-based implementation. In this implementation, the whole cubical complex is stored as a vector

-*of the values of filtration. This, together with dimension of \f$\mathcal{K}\f$ and the sizes of \f$\mathcal{K}\f$ in all directions, allows to determine, dimension, neighborhood, boundary and coboundary of every cube \f$C \in \mathcal{K}\f$.

-*

-*\image html "bitmapAllCubes.png" "Cubical complex.

-*

-*Note that the cubical complex in the figure above is, in a natural way, a product of one dimensional cubical complexes in \f$\mathbb{R}\f$. The number of all cubes in each direction is

-*equal \f$2n+1\f$, where \f$n\f$ is the number of maximal cubes in the considered direction. Let us consider a cube at the position \f$k\f$ in the bitmap. Knowing the sizes of the bitmap,

-*by a series of modulo operation, we can determine which elementary intervals are present in the product that gives the cube \f$C\f$. In a similar way, we can compute boundary

-*and the coboundary of each cube. Further details can be found in the literature.

-*

-*\section inputformat Input Format.

-*

-*In the current implantation, filtration is given at the maximal cubes, and it is then extended by the lower star filtration to all cubes. There are a number of constructors

-*that can be used to construct cubical complex by users who want to use the code directly. They can be found in the \a Bitmap_cubical_complex class.

-*Currently one input from a text file is used. It uses a format used already in Perseus software (http://www.sas.upenn.edu/~vnanda/perseus/) by Vidit Nanda.

-*Below we are providing a description of the format. The first line contains a number d begin the dimension of the bitmap (2 in the example below). Next d lines are the numbers of

-*top dimensional cubes in each dimensions (3 and 3 in the example below). Next, in lexicographical order, the filtration of top dimensional cubes is given (1 4 6 8 20 4 7 6 5 in the example below).

-*

-*

-*\image html "exampleBitmap.png" "Example of a input data."

-*

-*The input file for the following complex is:

-*\verbatim

+ * Bitmap_cubical_complex is an example of a structured complex useful in computational mathematics (specially rigorous

+ * numerics) and image analysis. The presented implementation of cubical complexes is based on the following

+ * definition.

+ *

+ * An <em>elementary interval</em> is an interval of a form \f$ [n,n+1] \f$, or \f$[n,n]\f$, for \f$ n \in \mathcal{Z}

+ * \f$. The first one is called <em>non-degenerate</em>, while the second one is \a degenerate interval. A

+ * <em>boundary of a elementary interval</em> is a chain  \f$\partial [n,n+1] = [n+1,n+1]-[n,n] \f$ in case of

+ * non-degenerated elementary interval and \f$\partial [n,n] = 0 \f$ in case of degenerate elementary interval. An

+ * <em>elementary cube</em> \f$ C \f$ is a product of elementary intervals, \f$C=I_1 \times \ldots \times I_n\f$.

+ * <em>Embedding dimension</em> of a cube is n, the number of elementary intervals (degenerate or not) in the product.

+ * A <em>dimension of a cube</em> \f$C=I_1 \times ... \times I_n\f$ is the number of non degenerate elementary

+ * intervals in the product. A <em>boundary of a cube</em> \f$C=I_1 \times \ldots \times I_n\f$ is a chain obtained

+ * in the following way:

+ * \f[\partial C = (\partial I_1 \times \ldots \times I_n) + (I_1 \times \partial I_2 \times \ldots \times I_n) +

+ * \ldots + (I_1 \times I_2 \times \ldots \times \partial I_n).\f]

+ * A <em>cubical complex</em> \f$\mathcal{K}\f$ is a collection of cubes closed under operation of taking boundary

+ * (i.e. boundary of every cube from the collection is in the collection). A cube \f$C\f$ in cubical complex

+ * \f$\mathcal{K}\f$ is <em>maximal</em> if it is not in a boundary of any other cube in \f$\mathcal{K}\f$. A \a

+ * support of a cube \f$C\f$ is the set in \f$\mathbb{R}^n\f$ occupied by \f$C\f$ (\f$n\f$ is the embedding dimension

+ * of \f$C\f$).

+ *

+ * Cubes may be equipped with a filtration values in which case we have filtered cubical complex. All the cubical

+ * complexes considered in this implementation are filtered cubical complexes (although, the range of a filtration may

+ * be a set of two elements).

+ *

+ * For further details and theory of cubical complexes, please consult \cite kaczynski2004computational as well as the

+ * following paper \cite peikert2012topological .

+ *

+ * \section datastructure Data structure.

+ *

+ * The implementation of Cubical complex provides a representation of complexes that occupy a rectangular region in

+ * \f$\mathbb{R}^n\f$. This extra assumption allows for a memory efficient way of storing cubical complexes in a form

+ * of so called bitmaps. Let \f$R = [b_1,e_1] \times \ldots \times [b_n,e_n]\f$, for \f$b_1,...b_n,e_1,...,e_n \in

+ * \mathbb{Z}\f$, \f$b_i \leq d_i\f$ be the considered rectangular region and let \f$\mathcal{K}\f$ be a filtered

+ * cubical complex having the rectangle \f$R\f$ as its support. Note that the structure of the coordinate system gives

+ * a way a lexicographical ordering of cells of \f$\mathcal{K}\f$. This ordering is a base of the presented

+ * bitmap-based implementation. In this implementation, the whole cubical complex is stored as a vector of the values

+ * of filtration. This, together with dimension of \f$\mathcal{K}\f$ and the sizes of \f$\mathcal{K}\f$ in all

+ * directions, allows to determine, dimension, neighborhood, boundary and coboundary of every cube \f$C \in

+ * \mathcal{K}\f$.

+ *

+ * \image html "bitmapAllCubes.png" "Cubical complex.

+ *

+ * Note that the cubical complex in the figure above is, in a natural way, a product of one dimensional cubical

+ * complexes in \f$\mathbb{R}\f$. The number of all cubes in each direction is equal \f$2n+1\f$, where \f$n\f$ is the

+ * number of maximal cubes in the considered direction. Let us consider a cube at the position \f$k\f$ in the bitmap.

+ * Knowing the sizes of the bitmap, by a series of modulo operation, we can determine which elementary intervals are

+ * present in the product that gives the cube \f$C\f$. In a similar way, we can compute boundary and the coboundary of

+ * each cube. Further details can be found in the literature.

+ *

+ * \section inputformat Input Format.

+ *

+ * In the current implantation, filtration is given at the maximal cubes, and it is then extended by the lower star

+ * filtration to all cubes. There are a number of constructors that can be used to construct cubical complex by users

+ * who want to use the code directly. They can be found in the \a Bitmap_cubical_complex class.

+ * Currently one input from a text file is used. It uses a format used already in Perseus software

+ * (http://www.sas.upenn.edu/~vnanda/perseus/) by Vidit Nanda.

+ * Below we are providing a description of the format. The first line contains a number d begin the dimension of the

+ * bitmap (2 in the example below). Next d lines are the numbers of top dimensional cubes in each dimensions (3 and 3

+ * in the example below). Next, in lexicographical order, the filtration of top dimensional cubes is given (1 4 6 8

+ * 20 4 7 6 5 in the example below).

+ *

+ *

+ * \image html "exampleBitmap.png" "Example of a input data."

+ *

+ * The input file for the following complex is:

+ * \verbatim

 2

 3

 3

@@ -93,15 +116,17 @@ namespace Cubical_complex
 5

 \endverbatim

 

-\section PeriodicBoundaryConditions Periodic boundary conditions

-Often one would like to impose periodic boundary conditions to the cubical complex. Let \f$ I_1\times ... \times I_n \f$ be a box

-that is decomposed with a cubical complex \f$ \mathcal{K} \f$. Imposing periodic boundary conditions in the direction i, means that the left and the right side of a complex

-\f$ \mathcal{K} \f$ are considered the same. In particular, if for a bitmap \f$ \mathcal{K} \f$ periodic boundary conditions are imposed in all directions, then complex

-\f$ \mathcal{K} \f$ became n-dimensional torus. One can use various constructors from the file Bitmap_cubical_complex_periodic_boundary_conditions_base.h to construct cubical

-complex with periodic boundary conditions. One can also use Perseus style input files. To indicate periodic boundary conditions in a given direction, then number of top dimensional cells

-in this direction have to be multiplied by -1. For instance:

+ * \section PeriodicBoundaryConditions Periodic boundary conditions

+ * Often one would like to impose periodic boundary conditions to the cubical complex. Let \f$ I_1\times ... \times

+ * I_n \f$ be a box that is decomposed with a cubical complex \f$ \mathcal{K} \f$. Imposing periodic boundary

+ * conditions in the direction i, means that the left and the right side of a complex \f$ \mathcal{K} \f$ are

+ * considered the same. In particular, if for a bitmap \f$ \mathcal{K} \f$ periodic boundary conditions are imposed

+ * in all directions, then complex \f$ \mathcal{K} \f$ became n-dimensional torus. One can use various constructors

+ * from the file Bitmap_cubical_complex_periodic_boundary_conditions_base.h to construct cubical complex with periodic

+ * boundary conditions. One can also use Perseus style input files. To indicate periodic boundary conditions in a

+ * given direction, then number of top dimensional cells in this direction have to be multiplied by -1. For instance:

 

-*\verbatim

+ *\verbatim

 2

 -3

 3

@@ -116,15 +141,16 @@ in this direction have to be multiplied by -1. For instance:
 5

 \endverbatim

 

-Indicate that we have imposed periodic boundary conditions in the direction x, but not in the direction y.

+ * Indicate that we have imposed periodic boundary conditions in the direction x, but not in the direction y.

 

  * \section BitmapExamples Examples

  * End user programs are available in example/Bitmap_cubical_complex folder.

 

-

-*/

+ */

 /** @} */  // end defgroup cubical_complex

 

-*@}//end of the group

-}

-}

+}  // namespace Cubical_complex

+

+}  // namespace Gudhi

+

+#endif  // DOC_GUDHI_CUBICAL_COMPLEX_COMPLEX_H_