Skip to content

Fix FindTriangle if a test point is on an edge

Tokishiro Karasawa requested to merge Toki/vtk:fix_FindTriangle into master

The class vtkDelaunay2D has a function FindTriangle to find a triangle that includes a test point. It works normally if the test point is in a triangle but has a problem if it is exactly on an edge of a triangle.

The function has an identification process whether a test point is outside of an edge by a value of variable dp. If the test point is exactly on the edge, dp takes a value of zero. In this case, the original code

if ( dp < VTK_DEL2D_TOLERANCE )
      {
      if ( dp < minProj ) //track edge most orthogonal to point direction
        {
        inside = 0;
        nei[1] = ptIds[i];
        nei[2] = ptIds[i2];
        minProj = dp;
        }
      }//outside this edge

does nothing, since minProj variable is initialized as zero. As a result, the triangle is treated as one that has a test point inside of it. This flow is inappropriate, because the triangle has the test point on the edge.

This problem causes some failures, in the Boolean difference process, such as triangle losses and process down.

We modified the initial value of minProj to be VTK_DEL2D_TOLERANCE, to prevent the above problem from occurring. This initialization is motivated by the statement

  else if ( !inside && (fabs(minProj) < VTK_DEL2D_TOLERANCE) ) // on edge

where any test point whose distance from the edge is less than VTK_DEL2D_TOLERANCE is identified to be on the edge.

Merge request reports