Improving polygon earcut
I found some issues related to vtkTriangleFilter and self-touching (not intersecting) polygons. After looking at the source code I ended up at 'CanRemoveVertex()' in vtkPolygon.cxx. The code uses a call to 'Intersection()' in vtkLine.cxx. The current code fails in the case of a return value != 0 (Note that Intersection() uses some defines for the result while CanRemoveVertex() just does a numerical compare).
In the special case of self-touching the current test will always fail and the higher level Triangulate() returns an empty result.
This behaviour could be fixed if 'CanRemoveVertex()' would do a special case handling:
VTK_NO_INTERSECTION valid earcut, this is the current implementation
Proposed change:
VTK_YES_INTERSECTION invalid earcut, originaly covered by != 0
VTK_ON_LINE this has two sub-cases
- We are 'outside' the polygon in respect to the other line (in/out based on direction). This means we are hit a self-touching line we can ignore -> valid earcut
- We are 'inside' the polygon in respect to the other line. This a -> invalid earcut
I hope the above notes are understandable. I can provide a small Python script showing a none working triangulation with the current code (double self-touching edge polygon).
You can uncomment the z-value hack to play a trick on Intersection(). Note this is not a work-around as it creates other unwanted cases (but it works for the current example).
#!/usr/bin/env python
from vtk import *
# define test polygon ---------------------------------------------------------
# 20 ______4______ 3 concave polygon CCW
# |17____|____6 | Self-touching two edges
# | |_________| | 4,19 at same coords
# |16 __|__ 7 | 5,18 at same coords
# | 13| 9 |10 | 9,14 at same coords
# | 12|_____|11 |
# |_____________|
# 1 2
x=[0,6,6,3,3,5,5,3,3,4,4,2,2,3,3,1,1,3,3,0]
y=[0,0,6,6,5,5,4,4,3,3,1,1,3,3,4,4,5,5,6,6]
npts = len(x)
# creation of the source ------------------------------------------------------
points = vtkPoints()
polygon = vtkPolygon()
polygon.GetPointIds().SetNumberOfIds( npts )
z = 0.0
for i in range( npts ):
points.InsertNextPoint( x[i], y[i], 0 ) # xy plane aligned
# points.InsertNextPoint( x[i], y[i], z )
# z = z + 0.001
polygon.GetPointIds().SetId(i, i)
polys = vtkCellArray()
polys.InsertNextCell(polygon)
polyData = vtkPolyData()
polyData.SetPoints(points)
polyData.SetPolys(polys)
result = polyData # set inital result
# filter the polydata ---------------------------------------------------------
#pdflt = vtkDelaunay2D()
#pdflt.SetSourceData( polyData )
pdflt = vtkTriangleFilter()
pdflt.SetInputData( polyData )
pdflt.Update()
result = pdflt.GetOutput()
# info ------------------------------------------------------------------------
numpoints = result.GetNumberOfPoints()
print( '#points = ', numpoints )
numpolys = result.GetNumberOfPolys()
print( '#polys = ', numpolys )
# map it ----------------------------------------------------------------------
mapper = vtkPolyDataMapper()
mapper.SetInputData( result )
# render it -------------------------------------------------------------------
actor = vtkActor()
actor.SetMapper(mapper)
actor.GetProperty().SetRepresentationToWireframe()
render = vtkRenderer()
render.AddActor(actor)
renwin = vtkRenderWindow()
renwin.AddRenderer(render)
rwiact = vtkRenderWindowInteractor()
rwiact.SetRenderWindow(renwin)
rwiact.SetInteractorStyle(vtkInteractorStyleTrackballCamera())
rwiact.Initialize()
rwiact.Start()
As an alternate solution I could implement a improved ear-cutting function outside VTK (this makes less sense for me).
Best regards Gerald