Back to index

salome-med  6.5.0
Geometric2D Intersector

Like other intersectors the aim of this intersector is to compute intersection between 2 polygons.

The specificity of this intersector is to deal with any type of polygons even those with quadratic edges. Its quite generic architecture allows him to deal with some other patentially usefull functions.
This page described Geometric2D intersector basic principles and specific usage.


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.

Naming conventions

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

Basic concepts

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

Each elementary edge and each nodes have a flag that states if during the split process if it is out, on, in or unknown.

Boolean operation algorithm


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 :

  1. splitting.
    1. edges localization.
    2. result polygons building.

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.
After this edge-splitting, polygon P1 is splitted, so that each elementary edge constituting P1 is either in, out or on polygon P2. And inversely, polygon P2 is splitted so that each elementary edge constituting P2 is either in, out or 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.
The method in charge of that is INTERP_KERNEL::QuadraticPolygon::splitPolygonsEachOther.

Step2 : Edges localization.

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

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

Previous Edge LocCurrent start node LocCurrent edge Loc
UNKNOWN ANY UNKNOWN -> Absolute search
ON ANY UNKNOWN -> Absolute search

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

Step3 : Result polygon building.

This stage links each edge with wanted loc. 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.
The principle of result polygon building is to build polygon by taking edges localized as in or on.

Generally, the principle is to take an edge in P1 with wanted loc and linking direct neighbour-edges (with correct loc) until closing a polygon. If not, using 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.

underneath algorithms.

Absolute localization algorithm.

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

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

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

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

Intersection algorithms.

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

  1. Lin-Lin intersection :
    1. Lin-Arc intersection :
    2. Arc-Arc intersection :

Other algorithms.

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


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

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 :

// defining a precision
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.
//play with polygons
double intersection=polygon1->intersectWith(*polygon2);
double dhydPol1=polygon1->getHydraulicDiameter();
double areaPol1=polygon1->getAreaOfZone();
delete polygon1;
delete polygon2;

Example of result.

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

An example of intersection of 2 polygons.
After spliting process P1 has 6 edges and P2 has 6 edges too.

After spliting process two edges of P1 have been located has out.
BLUE is for OUT, GREEN for IN and RED for ON.

For each 6 edges locate them.

Result after locating phase.
Too finish closing polygons.

Close-up of final result after close polygons phase.
The result polygon is constitued from 2 sub-edges coming from P1 and 1 sub-edge from P2 closing the polygon. For the 2 edges of P1 they are green because they are fully included in P2. Inversely, the only sub-edge coming from P2 is fully included in P1.