/*!
\page interpkernelGeo2D Geometric2D Intersector

Like other intersectors the aim of this intersector is to compute intersection between 2
polygons.\n
The specificity of this intersector is to deal with \b any \b type of
polygons even those with \b quadratic \b edges.
Its quite generic architecture allows him to deal with some other
patentially usefull functions.\n
This page described Geometric2D intersector basic principles and
specific usage.

\section interpkernelGeo2DIntro Introduction

The principle used in this intersector to perform boolean operation on geometry is geometric-modeler like.
The data structure used to describe polygons is boundary description. That is to say the internal
representation of a polygon is its edges composing it.

\subsection interpkernelGeo2DNamingConv Naming conventions

  - An \ref INTERP_KERNEL::AbstractEdge "edge" is defined by a start
    node, a end node and a curve equation (linear or arc of
    circle). \b WARNING : start node and end node \b HAVE \b TO \b BE
    different and distant at least equal to precision set.
  - An \ref INTERP_KERNEL::ElementaryEdge "elementary edge" is an edge \b NOT \b splittable \b without \b applying
    \b mathematical \b intersection \b computation.
  - A \ref INTERP_KERNEL::ComposedEdge "composed edge" is a collection of consecutive edges hierarchically \b splittable
    \b without \b any \b mathematical \b intersection \b computation.

Consecutive means that in a composed edge if edge \a e2 follows edge
\a e1, the end node of \a e1 is geometrically equal to start node of
\a e2.

\subsection interpkernelGeo2DBasicConcepts Basic concepts

A \ref INTERP_KERNEL::QuadraticPolygon "quadratic polygon" is a
specialization of a
\ref INTERP_KERNEL::ComposedEdge "composed edge" in that it is
closed. Closed means that the start node of first edge is equal to end
node of last edge.\n
A \ref INTERP_KERNEL::ComposedEdge "composed edge" is considered as a
collection of \ref INTERP_KERNEL::AbstractEdge "abstract edges". An
\ref INTERP_KERNEL::AbstractEdge "abstract edge" is either an \ref
INTERP_KERNEL::ElementaryEdge "elementary edge" or itself a \ref
INTERP_KERNEL::ComposedEdge "composed edge".\n A composite pattern has
been used here.

Each \ref INTERP_KERNEL::ElementaryEdge " elementary edge" and each
\ref INTERP_KERNEL::Node "nodes" have a flag that states if during
the split process if it is \b out, \b on, \b in or \b unknown.

\section interpkernelGeo2DBoolOp Boolean operation algorithm

\subsection interpkernelGeo2DBoolOpPrinc Basics

The boolean operation (intersection) between two polygons is used in P0 P0 interpolation.

The process of boolean operations between two polygons P1 and P2 is done in three steps :

  -# \ref interpkernelGeo2DBoolOpStep1 "splitting".
  -# \ref interpkernelGeo2DBoolOpStep2 "edges localization".
  -# \ref interpkernelGeo2DBoolOpStep3 "result polygons building".

\subsection interpkernelGeo2DBoolOpStep1 Step1 : splitting.

The principle used to do boolean operations between 2 polygons P1 and
P2 is to intersect each edge of P1 with each edge of P2. \n After this
edge-splitting, polygon P1 is splitted, so that each 
\ref INTERP_KERNEL::ElementaryEdge "elementary edge" constituting P1
is either \b in, \b out or \b on polygon P2. And inversely, polygon P2 is splitted so that each 
\ref INTERP_KERNEL::ElementaryEdge "elementary edge" constituting P2
is either \b in, \b out or \b on polygon P1.

During split process, when, without any CPU overhead, the location can be
deduced, the nodes and edges are localized.

This step of splitting is common to all boolean operations.\n
The method in charge of that is INTERP_KERNEL::QuadraticPolygon::splitPolygonsEachOther.

\subsection interpkernelGeo2DBoolOpStep2 Step2 : Edges localization.

Perform localization of each splitted edge. As \ref interpkernelGeo2DBoolOpStep1 "split process" it
     is common to all boolean operations.

When the location of edges has \b not been
already deduced in previous computation and there is no predecessor, the 
\ref interpkernelGeo2DAlgLoc "localization is done in absolute".
After it deduces the localization relatively to the previous edge
thanks to node localization.\n The relative localization is done
following these rules :

 * <TABLE BORDER=1 >
 * <TR><TD>Previous Edge Loc</TD><TD>Current start node Loc</TD><TD> Current edge Loc</TD></TR>
 * <TR><TD> UNKNOWN </TD><TD> ANY </TD><TD> UNKNOWN -> \ref interpkernelGeo2DAlgLoc "Absolute search" </TD></TR>
 * <TR><TD> OUT </TD><TD> ON </TD><TD> IN  </TD></TR>
 * <TR><TD> OUT </TD><TD> ON_TANGENT </TD><TD> OUT  </TD></TR>
 * <TR><TD> IN </TD><TD> ON </TD><TD> OUT </TD></TR>
 * <TR><TD> IN </TD><TD> ON_TANGENT </TD><TD> IN </TD></TR>
 * <TR><TD> OUT </TD><TD> OUT </TD><TD> OUT </TD></TR>
 * <TR><TD> IN </TD><TD> IN </TD><TD> IN </TD></TR>
 * <TR><TD> ON </TD><TD> ANY </TD><TD> UNKNOWN -> \ref interpkernelGeo2DAlgLoc "Absolute search" </TD></TR>
 *</TABLE>

The method in charge of that is INTERP_KERNEL::QuadraticPolygon::performLocatingOperation.

\subsection interpkernelGeo2DBoolOpStep3 Step3 : Result polygon building.

This stage links each edge with wanted loc. \b Contrary to last 2 steps it is obviously boolean
operation dependant. Let's take the case of the intersection that is used in
P0->P0 interpolation. \n The principle of result polygon building is to build polygon by taking
edges localized as \b in or \b on.

Generally, the principle is to take an edge in \a P1 with wanted loc and linking
direct neighbour-edges (with correct loc) until closing a polygon. If
not, using \a P2 edges to try to close polygon. The process is
repeated until all edges with correct loc have been consumed. 

The method in charge of that is INTERP_KERNEL::QuadraticPolygon::buildIntersectionPolygons.

\section interpkernelGeo2DAlg underneath algorithms.

\subsection interpkernelGeo2DAlgLoc Absolute localization algorithm.

This algorithm is called when splitting process has been done, and
that we are sure that the edge is either \b fully \b in ,or \b fully \b on or \b fully
\b out.

The principle chosen to know if an edge \a E is completely included in an
any polygon \a P is to see if its barycenter \a B is inside this any
polygon \a P.
After, for each nodes \f$ P_i \f$ of polygon \a P we store angle in \f$ [-\pi/2,\pi/2 ] \f$ 
that represents the slope of line \f$ (BP_i) \f$.\n
Then a line \a L going through \a B with a slope being as far as
possible from all slopes found above. Then the algorithm goes along \a L 
and number of times \a N it intersects \b non-tangentally the any polygon \a P.

If \a N is odd \a B (and then \a E) is IN.
If \a N is even \a B (and then \a E) is OUT.

This computation is \b very \b expensive, that why some tricks as described in
\ref interpkernelGeo2DBoolOpStep2 "localization techniques" are used to call as few as possible
during intersecting process.

\subsection interpkernelGeo2DAlgIntsect Intersection algorithms.

The only mathematical intersections performed are edges intersections.
The algorithms used are : 

  -# Lin-Lin intersection : http://mathworld.wolfram.com/Line-LineIntersection.html
  -# Lin-Arc intersection : http://mathworld.wolfram.com/Circle-LineIntersection.html
  -# Arc-Arc intersection : http://mathworld.wolfram.com/Circle-CircleIntersection.html

\subsection interpkernelGeo2DAlgOthers Other algorithms.

As internal architecture is quite general, it is possible to have more than classical intersection on any polygons :

  - \ref INTERP_KERNEL::ComposedEdge::getAreaOfZone "area" computation is available.
  - \ref INTERP_KERNEL::QuadraticPolygon::getPerimeterFast "perimeter" computation.
  - \ref INTERP_KERNEL::QuadraticPolygon::getHydraulicDiameter "Hydraulic diameter" computation.

\section interpkernelGeo2DUsage Usage.

This intersector is usable standalone. To use a set of user friendly methods have been implemented.

  - INTERP_KERNEL::QuadraticPolygon::buildArcCirclePolygon method builds from a \c std::vector of INTERP_KERNEL::Node* \a V, an instance of QuadraticPolygon \a P.
  \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
   \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.
  - INTERP_KERNEL::QuadraticPolygon::buildLinearPolygon method builds from a \c std::vector of INTERP_KERNEL::Node* \a V, an instance of QuadraticPolygon \a
  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].

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.

The usage is simple :

\code
...
// defining a precision
INTERP_KERNEL::QUADRATIC_PLANAR::setPrecision(1e-5);
INTERP_KERNEL::QUADRATIC_PLANAR::setArcDetectionPrecision(1e-5);
//
INTERP_KERNEL::QuadraticPolygon *polygon1=...;
bool isQuadratic=...//Depends on the nature of your cell. If your cell is MED_QUAD8 or MED_TRIA6 for example isQuadratic=true.
const double *externalTabXCoords=...;
const double *externalTabYCoords=...;
std::vector<INTERP_KERNEL::Node *> nodes;
INTERP_KERNEL::QuadraticPolygon *polygon2=0;
for(int i=0;i<nbOfNodes;i++)
  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.
if(isQuadratic)
  polygon2=INTERP_KERNEL::QuadraticPolygon::buildArcCirclePolygon(nodes);
else
  polygon2=INTERP_KERNEL::QuadraticPolygon::buildLinearPolygon(nodes);
//play with polygons
double intersection=polygon1->intersectWith(*polygon2);
double dhydPol1=polygon1->getHydraulicDiameter();
double areaPol1=polygon1->getAreaOfZone();
//clean-up
delete polygon1;
delete polygon2;
...
\endcode

\section interpkernelGeo2DExample Example of result.

Here an example of 2 polygons. The left one \a P1 has 4 edges and the
right one \a P2 has 4 edges too.

\anchor interpkernelGeo2DEx1
\image html SampGeo2D1.png "An example of intersection of 2 polygons."
\image latex SampGeo2D1.eps "An example of intersection of 2 polygons."

After \ref interpkernelGeo2DBoolOpStep1 "spliting process" \a P1 has 6 edges and \a P2 has 6 edges too.

\anchor interpkernelGeo2DEx2
\image html SampGeo2D2.png "After spliting process two edges of P1 have been located has out."
\image latex SampGeo2D2.eps "After spliting process two edges of P1 have been located has out."

\note BLUE is for OUT, GREEN for IN and RED for ON.

For each 6 edges \ref interpkernelGeo2DBoolOpStep2 "locate" them.

\anchor interpkernelGeo2DEx3
\image html SampGeo2D3.png "Result after locating phase."
\image latex SampGeo2D3.eps "Result after locating phase."

Too finish \ref interpkernelGeo2DBoolOpStep3 "closing" polygons.

\anchor interpkernelGeo2DEx4
\image html SampGeo2D4.png "Close-up of final result after close polygons phase."
\image latex SampGeo2D4.eps "Close-up of final result after close polygons phase."

\note The result polygon is constitued from 2 sub-edges coming from \a P1
and 1 sub-edge from \a P2 closing the polygon. For the 2 edges of \a P1
they are green because they are fully included in \a P2. Inversely,
the only sub-edge coming from \a P2 is fully included in \a P1.

*/