C# version (Triangle.Net)

[epsi1on]

Hi, I think you did ported this project to C#, but there is no such project under your account. Means you do not maintain the Triangle.Net project anymore? I have some issues with it :) May i ask it here?

[wo80]

Feel free to ask here.

I'm watching the fork at https://github.com/Geri-Borbas/Triangle.NET, so I'll get noticed about issues posted there, too. Also be aware of the licensing issues, so I'd discourage you from using the code in a commercial context or creating a hard dependency on it in your open source projects.

[epsi1on]

I have these:

• An outer ring as a list of points (black one)
• Several holes, also they are in form of points (red ones)
• Several line segments, which should be used for constraints (green one). by constaint i mean no triangle should cross this constraint

The red holes can have collisions with the outer ring also green lines. Does the package handle this case by itself? Or I should do preprocess my geometry data? if yes what other library you suggest for pre-process?

Thanks

[wo80]

I don't think there's a straight forward way to handle such a geometry. To get started, here's a gist: https://gist.github.com/wo80/fe9b40925cdfdafedad935457c4768dd

You can then use the code from this example to process only the triangles that are of interest: https://github.com/garykac/triangle.net/blob/master/wiki/Example_7.md

[wo80]

And always be aware that Triangle.NET shares the same restrictions as the original C code: http://www.cs.cmu.edu/~quake/triangle.trouble.html

[epsi1on]

Thanks. Do you accept donations on your projects? I'm interested to donate crypto or some local handicrafts... :)

[epsi1on]

Is it a suitable input geometry for triangulation?

[wo80]

Is it a suitable input geometry for triangulation?

Yes, that's a much saner input, but might require a segment intersection algorithm, which is O(n log n), just like Delaunay triangulation.

I've updated the gist with a little mesh post-processing function, which returns

Processed 40 triangles in region connected to segment with label 1
Processed 0 triangles in region connected to segment with label 3
Processed 10 triangles in region connected to segment with label 3
Processed 0 triangles in region connected to segment with label 4
Processed 39 triangles in region connected to segment with label 4

Label 1 is the outer boundary, label 4 the constraint. So the only problem is, that the hole (label 3, purple region in image below) is also processed. This is because the outer boundary intersects the hole, which defeats the automatic labeling of regions.

EDIT: this could be fixed by only using iterator seed triangles that are connected to internal constraints - in this case the segments with label 4. Though you'd have to make sure, that the seeding triangle is not inside a hole region.

[wo80]

If you want to support me, donations are very welcome. I do have bitcoin, ether and zcash wallets. You should also have my private email address christian.wo#######@tu-do######.de, so feel free to contact me there.

[wo80]

Updated the gist again to include a post processing function

void PostProcess(IMesh mesh, params int[] constraints)

which returns

Processed 40 triangles in region connected to segment with label 4
Processed 39 triangles in region connected to segment with label 4

[epsi1on]

Thanks. How to add some internal points (i mean the cyan points)? Those point should be presented in triangulation result.

[epsi1on]

If you want to support me, donations are very welcome. I do have bitcoin, ether and zcash wallets. You should also have my private email address christian.wo#######@tu-do######.de, so feel free to contact me there.

I'm not able to send email to that mailbox. it gives me dns error

[wo80]

How to add some internal points (i mean the cyan points)?

If you are using the code from the gist, just add the vertices in the CreatePolygon() method:

poly.Add(new Vertex(-3.5, 0.0, 5)); // 5 = vertex label

I'm not able to send email to that mailbox. it gives me dns error

You'd have to replace the hash chars with correct values. If I remember correctly, we had email contact back in 2016, so you should have the address (I don't like to post my email address on public message boards).

Anyways, you can use this contact form.

I've also written a little page with donation options: http://wo80.bplaced.net/donate.html

[epsi1on]

Thanks, To preserve the quality, during mesh process some nodes are added to result. How can I find them?

[wo80]

Do you mean the Steiner points that are automatically added by Triangle for quality meshing?

Those will be added to the back of the mesh vertices list, so to find them (using Linq), just skip the input points

 mesh.Vertices.Skip(poly.Points.Count)

Be aware that those can be internal vertices, but also constraint/boundary vertices. I recommend to always define labels for input vertices and segments. If a segment is split during refinement, the new vertex will get the segment label. This way, you can tell apart internal (label 0) and constraint Steiner points.

[epsi1on]

Do you mean the Steiner points that are automatically added by Triangle for quality meshing?

Those will be added to the back of the mesh vertices list, so to find them (using Linq), just skip the input points

 mesh.Vertices.Skip(poly.Points.Count)

Be aware that those can be internal vertices, but also constraint/boundary vertices. I recommend to always define labels for input vertices and segments. If a segment is split during refinement, the new vertex will get the segment label. This way, you can tell apart internal (label 0) and constraint Steiner points. yes I mean Steiner Points too, just forgot its name.

Thanks. Ho to identify the Traignles inside holes? i need to exclude them from result. And cannot use RegionPointers to define regions. Because it is hard (for me) to programmatically find any point that located inside the a polygon.

[wo80]

I updated the gist once again. There are two approaches for finding holes, one using region pointers and one using a quadtree. Both should be pretty robust and efficient. Let me know how those work out for you!

[epsi1on]

Thanks. My problem is this: Because i'm getting the hole geometry as set of vertex from user. With you approach user must specify two items: hole vertex list and a sample point inside the hole's polygon (which you store inside holes list). the problem is second item (point inside the polygon) that should be automatically computed, and should not taken from user. I have two ways:

• Use another approach that do not need second item (point inside hole)
• Use a method to automatically compute the second item

I do not have any idea about walking in either ways! :)

[wo80]

That's a frequent problem when using Triangle and Triangle.NET's Contour class has a method which can help. It's a kinda heuristic approach, but it always worked for me:

var vertices = ... // The vertices that define the hole (have to be in order, obviously)
var contour = new Contour(vertices);
var p = contour.FindInteriorPoint(); // Point inside the contour.

EDIT: If you are interested in the implementation, here's the code: Contour.cs and FindPointInPolygon()

If you find the time, please review the code and let me know, whether you think this is a reasonable approach or not :-)

[epsi1on]

Do you mean the Steiner points that are automatically added by Triangle for quality meshing?

Those will be added to the back of the mesh vertices list, so to find them (using Linq), just skip the input points

 mesh.Vertices.Skip(poly.Points.Count)

If a duplicated point is added to input then it is removed from mesh output, so i think mesh.Vertices.Skip(poly.Points.Count) is not a good general idea. I do work with Vertex.ID, any ID that is not generated by me is new and generated by framework... Is it good you think?

If you find the time, please review the code and let me know, whether you think this is a reasonable approach or not :-)

Is it ported from original C code?

[wo80]

If a duplicated point is added to input then it is removed from mesh output, so i think mesh.Vertices.Skip(poly.Points.Count) is not a good general idea. I do work with Vertex.ID, any ID that is not generated by me is new and generated by framework... Is it good you think?

Duplicates will not be removed. They are marked as undead and will simply not be part of the mesh topology. But they are still present in the vertices collection, see TriangulatorTest.cs.

Is it ported from original C code?

No, it's only available in the .NET version.

[Geri-Borbas]

Nice, cleaning up even the issues! 👏 Keep up the great work!