doc/user/doxygen/doxfiles/reference/interpolation/Geometric2D.dox

   1 /*!
   2 \page interpkernelGeo2D Geometric2D Intersector
   3
   4 Like other intersectors the aim of this intersector is to compute intersection between 2
   5 polygons.\n
   6 The specificity of this intersector is to deal with \b any \b type of
   7 polygons even those with \b quadratic \b edges.
   8 Its quite generic architecture allows him to deal with some other
   9 potentially useful functions.\n
  10 This page described Geometric2D intersector basic principles and
  11 specific usage.
  12
  13 \section interpkernelGeo2DIntro Introduction
  14
  15 The principle used in this intersector to perform boolean operation on geometry is geometric-modeler like.
  16 The data structure used to describe polygons is boundary description. That is to say the internal
  17 representation of a polygon is its edges composing it.
  18
  19 \subsection interpkernelGeo2DNamingConv Naming conventions
  20
  21   - An \ref INTERP_KERNEL::Edge "edge" is defined by a start
  22     node, a end node and a curve equation (linear or arc of
  23     circle). \b WARNING : start node and end node \b HAVE \b TO \b BE
  24     different and distant at least equal to precision set.
  25   - An \ref INTERP_KERNEL::ElementaryEdge "elementary edge" is an edge \b NOT \b splittable \b without \b applying
  26     \b mathematical \b intersection \b computation.
  27   - A \ref INTERP_KERNEL::ComposedEdge "composed edge" is a collection of consecutive edges hierarchically \b splittable
  28     \b without \b any \b mathematical \b intersection \b computation.
  29
  30 Consecutive means that in a composed edge if edge \a e2 follows edge
  31 \a e1, the end node of \a e1 is geometrically equal to start node of
  32 \a e2.
  33
  34 \subsection interpkernelGeo2DBasicConcepts Basic concepts
  35
  36 A \ref INTERP_KERNEL::QuadraticPolygon "quadratic polygon" is a
  37 specialization of a
  38 \ref INTERP_KERNEL::ComposedEdge "composed edge" in that it is
  39 closed. Closed means that the start node of first edge is equal to end
  40 node of last edge.\n
  41 A \ref INTERP_KERNEL::ComposedEdge "composed edge" is considered as a
  42 collection of \ref INTERP_KERNEL::Edge "abstract edges". An
  43 \ref INTERP_KERNEL::Edge "abstract edge" is either an \ref
  44 INTERP_KERNEL::ElementaryEdge "elementary edge" or itself a \ref
  45 INTERP_KERNEL::ComposedEdge "composed edge".\n A composite pattern has
  46 been used here.
  47
  48 Each \ref INTERP_KERNEL::ElementaryEdge " elementary edge" and each
  49 \ref INTERP_KERNEL::Node "nodes" have a flag that states if during
  50 the split process if it is \b out, \b on, \b in or \b unknown.
  51
  52 \section interpkernelGeo2DBoolOp Boolean operation algorithm
  53
  54 \subsection interpkernelGeo2DBoolOpPrinc Basics
  55
  56 The boolean operation (intersection) between two polygons is used in P0 P0 interpolation.
  57
  58 The process of boolean operations between two polygons P1 and P2 is done in three steps :
  59
  60   -# \ref interpkernelGeo2DBoolOpStep1 "splitting".
  61   -# \ref interpkernelGeo2DBoolOpStep2 "edges localization".
  62   -# \ref interpkernelGeo2DBoolOpStep3 "result polygons building".
  63
  64 \subsection interpkernelGeo2DBoolOpStep1 Step1 : splitting.
  65
  66 The principle used to do boolean operations between 2 polygons P1 and
  67 P2 is to intersect each edge of P1 with each edge of P2. \n After this
  68 edge-splitting, polygon P1 is splitted, so that each
  69 \ref INTERP_KERNEL::ElementaryEdge "elementary edge" constituting P1
  70 is either \b in, \b out or \b on polygon P2. And inversely, polygon P2 is splitted so that each
  71 \ref INTERP_KERNEL::ElementaryEdge "elementary edge" constituting P2
  72 is either \b in, \b out or \b on polygon P1.
  73
  74 During split process, when, without any CPU overhead, the location can be
  75 deduced, the nodes and edges are localized.
  76
  77 This step of splitting is common to all boolean operations.\n
  78 The method in charge of that is INTERP_KERNEL::QuadraticPolygon::splitPolygonsEachOther.
  79
  80 \subsection interpkernelGeo2DBoolOpStep2 Step2 : Edges localization.
  81
  82 Perform localization of each splitted edge. As \ref interpkernelGeo2DBoolOpStep1 "split process" it
  83      is common to all boolean operations.
  84
  85 When the location of edges has \b not been
  86 already deduced in previous computation and there is no predecessor, the
  87 \ref interpkernelGeo2DAlgLoc "localization is done in absolute".
  88 After it deduces the localization relatively to the previous edge
  89 thanks to node localization.\n The relative localization is done
  90 following these rules :
  91
  92  * <TABLE BORDER=1 >
  93  * <TR><TD>Previous Edge Loc</TD><TD>Current start node Loc</TD><TD> Current edge Loc</TD></TR>
  94  * <TR><TD> UNKNOWN </TD><TD> ANY </TD><TD> UNKNOWN -> \ref interpkernelGeo2DAlgLoc "Absolute search" </TD></TR>
  95  * <TR><TD> OUT </TD><TD> ON </TD><TD> IN  </TD></TR>
  96  * <TR><TD> OUT </TD><TD> ON_TANGENT </TD><TD> OUT  </TD></TR>
  97  * <TR><TD> IN </TD><TD> ON </TD><TD> OUT </TD></TR>
  98  * <TR><TD> IN </TD><TD> ON_TANGENT </TD><TD> IN </TD></TR>
  99  * <TR><TD> OUT </TD><TD> OUT </TD><TD> OUT </TD></TR>
 100  * <TR><TD> IN </TD><TD> IN </TD><TD> IN </TD></TR>
 101  * <TR><TD> ON </TD><TD> ANY </TD><TD> UNKNOWN -> \ref interpkernelGeo2DAlgLoc "Absolute search" </TD></TR>
 102  *</TABLE>
 103
 104 The method in charge of that is INTERP_KERNEL::QuadraticPolygon::performLocatingOperation.
 105
 106 \subsection interpkernelGeo2DBoolOpStep3 Step3 : Result polygon building.
 107
 108 This stage links each edge with wanted loc. \b Contrary to last 2 steps it is obviously boolean
 109 operation dependant. Let's take the case of the intersection that is used in
 110 P0->P0 interpolation. \n The principle of result polygon building is to build polygon by taking
 111 edges localized as \b in or \b on.
 112
 113 Generally, the principle is to take an edge in \a P1 with wanted loc and linking
 114 direct neighbour-edges (with correct loc) until closing a polygon. If
 115 not, using \a P2 edges to try to close polygon. The process is
 116 repeated until all edges with correct loc have been consumed.
 117
 118 The method in charge of that is INTERP_KERNEL::QuadraticPolygon::buildIntersectionPolygons.
 119
 120 \section interpkernelGeo2DAlg Underlying algorithms
 121
 122 \subsection interpkernelGeo2DAlgLoc Absolute localization algorithm
 123
 124 This algorithm is called when splitting process has been done, and
 125 that we are sure that the edge is either \b fully \b in ,or \b fully \b on or \b fully
 126 \b out.
 127
 128 The principle chosen to know if an edge \a E is completely included in an
 129 any polygon \a P is to see if its barycenter \a B is inside this any
 130 polygon \a P.
 131 After, for each nodes \f$ P_i \f$ of polygon \a P we store angle in \f$ [-\pi/2,\pi/2 ] \f$
 132 that represents the slope of line \f$ (BP_i) \f$.\n
 133 Then a line \a L going through \a B with a slope being as far as
 134 possible from all slopes found above. Then the algorithm goes along \a L
 135 and number of times \a N it intersects \b non-tangentially the any polygon \a P.
 136
 137 If \a N is odd \a B (and then \a E) is IN.
 138 If \a N is even \a B (and then \a E) is OUT.
 139
 140 This computation is \b very \b expensive, that why some tricks as described in
 141 \ref interpkernelGeo2DBoolOpStep2 "localization techniques" are used to call as few as possible
 142 during intersecting process.
 143
 144 \subsection interpkernelGeo2DAlgIntsect Intersection algorithms
 145
 146 The only mathematical intersections performed are edges intersections.
 147 The algorithms used are :
 148
 149   -# Lin-Lin intersection : http://mathworld.wolfram.com/Line-LineIntersection.html
 150   -# Lin-Arc intersection : http://mathworld.wolfram.com/Circle-LineIntersection.html
 151   -# Arc-Arc intersection : http://mathworld.wolfram.com/Circle-CircleIntersection.html
 152
 153 \subsection interpkernelGeo2DAlgOthers Other algorithms
 154
 155 As internal architecture is quite general, it is possible to have more than classical intersection on any polygons :
 156
 157   - \ref INTERP_KERNEL::ComposedEdge::getAreaOfZone "area" computation is available.
 158   - \ref INTERP_KERNEL::QuadraticPolygon::getPerimeterFast "perimeter" computation.
 159   - \ref INTERP_KERNEL::QuadraticPolygon::getHydraulicDiameter "Hydraulic diameter" computation.
 160
 161 \section interpkernelGeo2DUsage Usage
 162
 163 This intersector is usable standalone. To use a set of user friendly methods have been implemented.
 164
 165   - INTERP_KERNEL::QuadraticPolygon::buildArcCirclePolygon method builds from a \c std::vector of INTERP_KERNEL::Node* \a V, an instance of QuadraticPolygon \a P.
 166   \a P will have \f$ N_{edges} = V.size()/2 \f$ edges. Quadratic edge \f$ Edge_i i \in [0,N_{edges}-1] \f$ starts with node V[i], ends with node V[i+1] and has a middle in
 167    \f$ V[i+N_{edge}] \f$. \n If start, end and middle nodes of edge \f$ Edge_i \f$ are aligned by a precision specified by INTERP_KERNEL::QUADRATIC_PLANAR::setArcDetectionPrecision.
 168   - INTERP_KERNEL::QuadraticPolygon::buildLinearPolygon method builds from a \c std::vector of INTERP_KERNEL::Node* \a V, an instance of QuadraticPolygon \a
 169   P. \a P will have \f$ N_edges = V.size() \f$ edges. Linear edge \f$ Edge_i i \in [0,N_{edges}-1] \f$ starts with node V[i] and ends with node V[i+1].
 170
 171 The orientation of polygons (clockwise, inverse clockwise) impact computation only on the sign of areas. During intersection of 2 polygons their orientation can be different.
 172
 173 The usage is simple :
 174
 175 \code
 176 ...
 177 // defining a precision
 178 INTERP_KERNEL::QUADRATIC_PLANAR::setPrecision(1e-5);
 179 INTERP_KERNEL::QUADRATIC_PLANAR::setArcDetectionPrecision(1e-5);
 180 //
 181 INTERP_KERNEL::QuadraticPolygon *polygon1=...;
 182 bool isQuadratic=...//Depends on the nature of your cell. If your cell is MED_QUAD8 or MED_TRIA6 for example isQuadratic=true.
 183 const double *externalTabXCoords=...;
 184 const double *externalTabYCoords=...;
 185 std::vector<INTERP_KERNEL::Node *> nodes;
 186 INTERP_KERNEL::QuadraticPolygon *polygon2=0;
 187 for(int i=0;i<nbOfNodes;i++)
 188   nodes.push_back(new INTERP_KERNEL::Node(externalTabXCoords[i],externalTabYCoords[i]));// First param of Node constructor is its X-axis and the second its Y-axis.
 189 if(isQuadratic)
 190   polygon2=INTERP_KERNEL::QuadraticPolygon::buildArcCirclePolygon(nodes);
 191 else
 192   polygon2=INTERP_KERNEL::QuadraticPolygon::buildLinearPolygon(nodes);
 193 //play with polygons
 194 double intersection=polygon1->intersectWith(*polygon2);
 195 double dhydPol1=polygon1->getHydraulicDiameter();
 196 double areaPol1=polygon1->getAreaOfZone();
 197 //clean-up
 198 delete polygon1;
 199 delete polygon2;
 200 ...
 201 \endcode
 202
 203 \section interpkernelGeo2DExample Example of result
 204
 205 Here an example of 2 polygons. The left one \a P1 has 4 edges and the
 206 right one \a P2 has 4 edges too.
 207
 208 \anchor interpkernelGeo2DEx1
 209 \image html SampGeo2D1.png "An example of intersection of 2 polygons."
 210 \image latex SampGeo2D1.eps "An example of intersection of 2 polygons."
 211
 212 After \ref interpkernelGeo2DBoolOpStep1 "spliting process" \a P1 has 6 edges and \a P2 has 6 edges too.
 213
 214 \anchor interpkernelGeo2DEx2
 215 \image html SampGeo2D2.png "After spliting process two edges of P1 have been located has out."
 216 \image latex SampGeo2D2.eps "After spliting process two edges of P1 have been located has out."
 217
 218 \note BLUE is for OUT, GREEN for IN and RED for ON.
 219
 220 For each 6 edges \ref interpkernelGeo2DBoolOpStep2 "locate" them.
 221
 222 \anchor interpkernelGeo2DEx3
 223 \image html SampGeo2D3.png "Result after locating phase."
 224 \image latex SampGeo2D3.eps "Result after locating phase."
 225
 226 Too finish \ref interpkernelGeo2DBoolOpStep3 "closing" polygons.
 227
 228 \anchor interpkernelGeo2DEx4
 229 \image html SampGeo2D4.png "Close-up of final result after close polygons phase."
 230 \image latex SampGeo2D4.eps "Close-up of final result after close polygons phase."
 231
 232 \note The result polygon is constituted of 2 sub-edges coming from \a P1
 233 and 1 sub-edge from \a P2 closing the polygon. For the 2 edges of \a P1
 234 they are green because they are fully included in \a P2. Inversely,
 235 the only sub-edge coming from \a P2 is fully included in \a P1.
 236
 237 */