insert Vertex into Delaunay and evaluate adjacent triangles

Feb 23, 2016 at 2:47 PM
Dear wo80,
First I would like to thank you for this great contribution.


I am working on a tool using your libary and having some speed issues using the insertVertex method and VertexCirculator class.
I am iteratively inserting a new vertex at the time into an exising delaunay ( created with triangle.net) After every vertex inserted I need to find the adjacent triangles
to calculate distances via circumference circle. I am currently using the following workflow below at each iteration and have a few questions:


A: can var circulator ( vertexCirculator) be updated each iteration rather than newly instanciated every iteration.
B: Is there a way to get the boundary triangles already as a result of the insertVertex Method ?
C: To insert a the Vertex I am using a dummytri for the otri .. Sometimes this results in a nullexception at the locationsearch. Therefore I built this workaround (below) and changed some codein the mesh.cs to not precise.locate when a triangle[0] is given .. Any suggestions how to solve the issue in a cleaner way ?
  ///////////// INSERT VERTEX IN MESH /////

 TriangleNet.Topology.Otri otri3 = default(TriangleNet.Topology.Otri);
 TriangleNet.Topology.Osub osub3 = default(TriangleNet.Topology.Osub);
 osub3.seg = null;
 TriangleNet.Geometry.Vertex myvertex = new TriangleNet.Geometry.Vertex(pN.X, pN.Y);


 while (true)
    {
      try
         {
          otri3.tri = triangleNetMesh.dummytri;
          var res = triangleNetMesh.InsertVertex(myvertex, ref otri3, ref osub3, false, false);
          resInt = (int)res;
          break;
          }
          catch
                {
                 List<TriangleNet.Topology.Triangle> netTriangle = new                
                 List<TriangleNet.Topology.Triangle>(triangleNetMesh.Triangles);
                 otri3.tri = netTriangle[0];
                 var res = triangleNetMesh.InsertVertex(myvertex, ref otri3, ref osub3, false, false);
                 resInt = (int)res;
                 break;
                  }
       }

var vertices = triangleNetMesh.Vertices.ToList();
TriangleNet.Geometry.Vertex insertedVertex = vertices[vertices.Count - 1];
var circulator = new TriangleNet.Meshing.Iterators.VertexCirculator(triangleNetMesh);
IEnumerable<TriangleNet.Geometry.ITriangle> EnumAdjacentTriangles;
EnumAdjacentTriangles = circulator.EnumerateTriangles(insertedVertex);
                
Thanks in advance
Best
Christoph
Coordinator
Feb 23, 2016 at 11:39 PM
Edited Feb 23, 2016 at 11:55 PM
  1. The speed of the incremental Delaunay algorithm largely depends on the speed of triangle location. So, depending on your problem, you should know a good starting triangle before calling the InsertVertex method.
  2. The InsertVertex method might fail for non-convex meshes (see TriangleLocator class). That's probably why you get the exceptions. Don't try to work around this (while-loop and try-catch). You will need some kind of point location (see Kirkpatrick's algorithm as an example (efficient, but not the easiest to understand)).
  3. Depending on the size of your mesh, doing new List<Triangle>(mesh.Triangles) or mesh.Vertices.ToList() is a bad idea (lots of unnecessary memory allocations). Use LINQ instead (mesh.Triangles.First(), mesh.Vertices.Last()).
  4. Avoid using the VertexCirculator class: On successful return of InsertVertex, the searchtri parameter will point to a triangle that has the inserted vertex as it's origin. You can start iterating from that triangle. If you can be sure that the inserted vetrex will not lie on the mesh boundary, getting the adjacent triangles is very simple (look at the VertexCirculator implementation - you only need the first while-loop of BuildCache).