# How to triangulate 2d polygons

Hi all,

I have some 2d polygons that may include holes which I need to triangulate.
Searching the forum it seems to me that this should be in general possible, but there may be several solutions. May someone give a hint how to solve that task?

Thanks,
michael Dear Michael,
Regards Dear Supervisor,

Do you propose to use BRep_Tool::Triangulation() or to contact openCascade regarding a paid solution?

Regards,
Michael Dear Michael,
I meant that you may contact us in case if the issue is critical for you.
We will try to find a solution/workaround acceptable for you.
Regards Dear Supervisor,

the issue is of course critical for us. This is what I did so far:

/////////////////////////////////////////////////////////////////////////////
struct Point2D
{
double x;
double y;
};

struct Polygon2D
{
std::vector vertices;
};

gp_Pnt pnt;
TopoDS_Vertex v;
BRepBuilderAPI_MakePolygon wire;

for(std::vector::const_iterator pit = thePolygon->vertices.begin();
pit != thePolygon->vertices.end(); ++pit)
{
pnt.SetCoord((*pit).x, (*pit).y, 0.0);
}
wire.Close();

TopoDS_Face face = BRepBuilderAPI_MakeFace(wire.Wire());

Handle_StlMesh_Mesh Mesh = new StlMesh_Mesh;

Standard_Real theCoefficient = 0.001;
Standard_Real aXmin, aYmin, aZmin, aXmax, aYmax, aZmax;
Bnd_Box Total;
Total.Get(aXmin, aYmin, aZmin, aXmax, aYmax, aZmax);
Standard_Real theDeflection = max(max(abs(aXmax-aXmin), abs(aYmax-aYmin)), abs(aZmax-aZmin)) * theCoefficient;
if (theDeflection <= Precision::Confusion()) continue;

StlTransfer::BuildIncrementalMesh(face, theDeflection, Mesh);

TopLoc_Location Loc;
Handle(Poly_Triangulation) theTriangulation = BRep_Tool::Triangulation(face, Loc);

if (theTriangulation.IsNull()) return false;

Poly_Array1OfTriangle theTriangles(1, theTriangulation->NbTriangles());
theTriangles.Assign(theTriangulation->Triangles());

TColgp_Array1OfPnt thePoints(1, theTriangulation->NbNodes());
thePoints.Assign(theTriangulation->Nodes());

for (int i = 1; i <= theTriangles.Length(); ++i)
{
Standard_Integer V1, V2, V3;
Poly_Triangle triangle = theTriangles.Value(i);
triangle.Get(V1, V2, V3);

gp_Pnt P1, P2, P3;
P1 = thePoints(V1);
P2 = thePoints(V2);
P3 = thePoints(V3);

std::vector resultTriangle;
resultTriangle.push_back(Point2D(P1.X(), P1.Y()));
resultTriangle.push_back(Point2D(P2.X(), P2.Y()));
resultTriangle.push_back(Point2D(P3.X(), P3.Y()));

resultTriangles.push_back(resultTriangle);
}
////////////////////////////////////////////////////////////////////////

That source code actually creates some triangles but not as expected. I've uploaded a screenshot of the triangulation result here: http://imageshack.us/photo/my-images/543/82699325.png
Here a screenshot of the polygon outline I tried to fill/triangulate:
http://imageshack.us/photo/my-images/15/50981371.png

I would be pleased if you find a solution for that task.

I sent a copy of that message via contact formula as you requested.

Thanks & Regards,
Michael Hi Michael,

Here you can find some example of a 3D tesselation algorithm, that should give you some hint about how to proceed:
https://github.com/tpaviot/pythonocc/blob/tp/webgl-backend/src/wrapper/V...
https://github.com/tpaviot/pythonocc/blob/tp/webgl-backend/src/wrapper/V...

Regards,

Thomas Hi Thomas,

thanks for the source code but I think that helps not much. I would guess our problem is related to the construction of the polygon datastructure (BRepBuilderAPI_MakePolygon) which is the base for the triangulation algorithm. Apparently every 4 vertices of our polygon outline are triangulated as 1 independent polygon (see my screenshots)...

Thanks & Regards,
Michael Hi all,

I was able the issue of triangulating polygonal 2 surfaces. The insertion of holes works unfortunately not correctly in all cases.
Hi,

my task is to triangulate 2d polygons described by an ordered sequence of edges. That polygons may include holes.
This is caused by the orientation (CW, CCW) of polygon and hole as I currently do not know exactly which orientation they use.
The openCascade support team told me that the polygon itself should have CCW whereas holes should be CW.
To solve that issue they recommended to use one of the following 2 methods:

1.) Create faces for each polygon and hole seperately and calculate their area. Positive means CCW, Negative means CW
--> this sounds to me to be the best approach. But I have no clue how to calculate the area of a face using openCascade. May someone can give me an advise? Thanks!

2.) Constructing the face and adding holes without paying attention to any orientations. Afterwards apply Shape Healing (ShapeFix_Shape)
--> I have tried that but is does not seem to work correctly. May some have a look?

This is my current source code:

// Create polygon outline
BRepBuilderAPI_MakePolygon W;

for(std::vector::const_iterator pit = polygon->vertices.begin();
pit != polygon->vertices.end(); ++pit)
{
}

W.Close();

if( W.Wire().IsNull() )
return;

// mkplane f1 p1 1
BRepBuilderAPI_MakeFace F1 = BRepBuilderAPI_MakeFace(W.Wire(), Standard_False);

if( F1.Face().IsNull() )
return;

// Create hole polygon outline
BRepBuilderAPI_MakePolygon H;

for(std::vector::const_iterator pit = holePolygon->vertices.begin();
pit != holePolygon->vertices.end(); ++pit)
{
}

H.Close();

if( H.Wire().IsNull() )
return;

// Heal Shape
Handle(ShapeFix_Shape) mkFix = new ShapeFix_Shape(F1);
mkFix->Perform();

TopoDS_Shape FixedShape = mkFix->Shape();

// Do Triangulation...

// incmesh f1 1e-5
BRepMesh_IncrementalMesh mesh(FixedShape, 0.00001);

TopExp_Explorer ex;
Handle(Poly_Triangulation) T;
TopLoc_Location L;

for (ex.Init(mesh.Shape(), TopAbs_FACE); ex.More(); ex.Next())
{
TopoDS_Face F2 = TopoDS::Face(ex.Current());
T = BRep_Tool::Triangulation(F2, L);
if (!T.IsNull())
{
TColgp_Array1OfPnt thePoints(1, T->NbNodes());
thePoints.Assign(T->Nodes());

Poly_Array1OfTriangle theTriangles(1, T->NbTriangles());
theTriangles.Assign(T->Triangles());

//std::cout << "Triangles:" << std::endl;
for (int i = 1; i <= theTriangles.Length(); ++i)
{
Standard_Integer V1, V2, V3;
Poly_Triangle triangle = theTriangles.Value(i);
triangle.Get(V1, V2, V3);

gp_Pnt P1, P2, P3;
P1 = thePoints(V1);
P3 = thePoints(V2);
P2 = thePoints(V3);

std::vector triangleVertices;
triangleVertices.push_back(Point2d(P1.X(), P1.Y()));
triangleVertices.push_back(Point2d(P2.X(), P2.Y()));
triangleVertices.push_back(Point2d(P3.X(), P3.Y()));

resultTriangles.push_back(Polygon2D(triangleVertices));
}
}
}

Thanks & Regards,
Michael