[vtkusers] vtkPointInTriangle - bug?

[David Thompson]

Hi Dov,

Looking at the source for vtkTriangle::PointInTriangle, it appears that 3 cross products are computed: for each corner point of the triangle, a vector from the test point p to the corner is crossed with an edge vector of the triangle. When p is in the plane of the corner points, these vectors are either aligned or opposite the plane normal. If all three cross products are codirectional, the point is inside the triangle. Otherwise it is out. This is tested by taking the dot product of each cross product with the others and verifying the sign is positive. As the test point is moved outside the plane, the cross products will eventually produce a negative dot product and the test will fail.

It's not how I would have written the test, but I believe it produces correct results when p is in the plane of the triangle. I do not think the test should be expected to work when p is far from the plane. However, I agree that the documentation should be improved. Please feel free to submit a patch to gerrit to improve it.

	David

On Feb 19, 2014, at 1:47 AM, Dov Grobgeld <dov.grobgeld at gmail.com> wrote:

> Hi David,
> 
> Thanks for your reply. Three comments:
> 
> 1. The documentation doesn't explain this is the behavior.
> 2. Projected by what direction. I would assume by the direction of the triangle normal. But this is not consistant with testing p=P((5,1,10)) in the below script which is reported by vtk to not be in the triangle (a,b,c).
> 3. Could this behavior be related to my other reported bug in vtkCellLocator.FindCell() that return the ''wrong" vtkTriangle, which does not contain the queried point?
> 
> Thanks!
> Dov
> 
> 
> 
> On Tue, Feb 18, 2014 at 11:57 PM, David Gobbi <david.gobbi at gmail.com> wrote:
> Hi Dov,
> 
> The PointInTriangle method checks whether the point, after being
> projected onto the plane of the triangle, lies within the triangle.
> 
>   David
> 
> On Tue, Feb 18, 2014 at 1:11 PM, Dov Grobgeld <dov.grobgeld at gmail.com> wrote:
> > The following is a comparison of testing whether a point p falls within the
> > plane of a triangle a,b,c by basic python code vs by using vtk.
> >
> > #!/usr/bin/python
> >
> > from numpy import cross, dot, sqrt
> > from numpy import array as P
> > import vtk
> >
> > def norm(v):
> >   mag = sqrt((v**2).sum())
> >   return v/mag
> >
> > a,b,c = (P((0,0,0)),
> >          P((10,0,0)),
> >          P((10,10,0)))
> >
> > p = P((5,1,1))
> >
> > # Test for linearity
> > #
> > #       b
> > #      / \
> > #     /   \
> > #    /  p  \
> > #   a-------c
> > #
> > N1 = norm(cross(b-a, p-a))
> > N2 = norm(cross(p-c, b-c))
> > N1dotN2 = dot(N1,N2)
> > print 'By norms: ', N1dotN2 > 0.99
> >
> > # Same test with vtk
> > print 'vtkInTriangle = ', vtk.vtkTriangle.PointInTriangle(p, a,b,c, 1e-10)
> >
> > The result is:
> >
> > By norms:  False
> > vtkInTriangle =  1
> >
> > It is trivial that the point p does not fall in the triangle. But still vtk
> > sais so. Is this a bug in vtk or am I misunderstanding what
> > vtkTriangle.PointInTriangle() is doing?
> >
> > Thanks!
> > Dov
> 
> _______________________________________________
> Powered by www.kitware.com
> 
> Visit other Kitware open-source projects at http://www.kitware.com/opensource/opensource.html
> 
> Please keep messages on-topic and check the VTK FAQ at: http://www.vtk.org/Wiki/VTK_FAQ
> 
> Follow this link to subscribe/unsubscribe:
> http://www.vtk.org/mailman/listinfo/vtkusers