MantisBT - VTK
View Issue Details
IDProjectCategoryView StatusDate SubmittedLast Update
0001868VTK(No Category)public2005-05-19 08:182013-04-05 19:57
ReporterMarijn van Stralen 
Assigned ToZhanping Liu 
PriorityhighSeveritymajorReproducibilityalways
StatusclosedResolutionfixed 
PlatformOSOS Version
Product Version 
Target VersionFixed in Version 
Project
Type
Summary0001868: vtkTriangle::PointInTriangle returns true if on extended line of line segment
DescriptionThe method vtkTriangle::PointInTriangle returns true if the point is on the full line of one of the line segments, and thus NOT in the triangle. This is not an edge problem, but a serious error.
In the following code, all points are in the triangle according to vtkTriangle::PointInTriangle(...), while only the second should be:
void vtkTriangleTest(){
    double p1[3] = {0,7,0};
    double p2[3] = {0,10,0};
    double p3[3] = {5,7,0};
    double x1[3] = {0,11,0};
    double x2[3] = {0.0001,8,0};
    double x3[3] = {0,1,0};

    if (vtkTriangle::PointInTriangle(x1, p1, p2, p3, 0.01)){
        std::cout << "1: " << "Point in triangle" << std::endl;
    }
    else std::cout << "1: " << "Point NOT in triangle" << std::endl;
    if (vtkTriangle::PointInTriangle(x2, p1, p2, p3, 0.01)){
        std::cout << "2: " << "Point in triangle" << std::endl;
    }
    else std::cout << "2: " << "Point NOT in triangle" << std::endl;
    if (vtkTriangle::PointInTriangle(x3, p1, p2, p3, 0.01)){
        std::cout << "3: " << "Point in triangle" << std::endl;
    }
    else std::cout << "3: " << "Point NOT in triangle" << std::endl;
}
Steps To Reproduce
Additional Information
TagsNo tags attached.
Relationships
Attached Filespatch vtkTriangle.cxx.patch (1,117) 1969-12-31 19:00
https://www.vtk.org/Bug/file/5294/vtkTriangle.cxx.patch
Issue History
Date ModifiedUsernameFieldChange
2008-09-23 11:30Berk GeveciAssigned ToWill Schroeder => Zhanping Liu
2008-09-25 16:23Zhanping LiuNote Added: 0013585
2008-09-25 16:24Zhanping LiuStatustabled => @80@
2008-09-25 16:24Zhanping LiuResolutionopen => fixed
2011-06-16 13:11Zack GalbreathCategory => (No Category)
2013-04-05 19:57Berk GeveciStatuscustomer review => closed

Notes
(0002447)
   
2005-05-25 13:48   
Bug 0000640 changed the code in vtkTriangle::PointInTriangle so that a point on an edge would return true. This was done so that
vtkPolygon::IntersectPolygonWithPolygon() would return true when polygons intersected each other at their edges. Looks like it returns true along an infinite edge :-(

To fix this, some code to check if the cross products == 0 (or the dot prod of the norms == 0) and then to see if the point is outside the edge could work (see patch). Alternatively, a different point in triangle test here: http://www.blackpawn.com/texts/pointinpoly/default.html [^] could be tried.
(0002448)
Goodwin Lawlor   
2005-05-25 13:54   
Bug 0000640 changed code in vtkTriangle::PointInTriangle so that a point on the edge of a triangle would return true. This was done so that vtkPolygon::IntersectPolygonWithPolygon would return true if polygons intersected each other at their edges. But its returning true along an infinite edge :-(

To fix this a code to see if the point is on an edge could be added (see patch). Alternatively, a different point in triangle test could be tried (see http://www.blackpawn.com/texts/pointinpoly/default.html [^] )
(0013585)
Zhanping Liu   
2008-09-25 16:23   
The bug has been fixed. The problem was due to the normal
checking mechanism, which did not consider the third normal check
--- the dot-product between n1 and n3. Now that the third normal
check is included, only point #2 is inside the triangle while point #1
and point #3 are outside. Please go to vtkTriangle::PointInTriangle()
to find the fix.
new revision: 1.8; previous revision: 1.7