View Issue Details [ Jump to Notes ] [ Print ]
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 
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;
}
TagsNo tags attached.
Project
Type
Attached Filespatch file icon vtkTriangle.cxx.patch [^] (1,117 bytes) 1969-12-31 19:00 [Show Content]

 Relationships

  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 (reporter)
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 (developer)
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

 Issue History
Date Modified Username Field Change
2008-09-23 11:30 Berk Geveci Assigned To Will Schroeder => Zhanping Liu
2008-09-25 16:23 Zhanping Liu Note Added: 0013585
2008-09-25 16:24 Zhanping Liu Status tabled => @80@
2008-09-25 16:24 Zhanping Liu Resolution open => fixed
2011-06-16 13:11 Zack Galbreath Category => (No Category)
2013-04-05 19:57 Berk Geveci Status customer review => closed

Copyright © 2000 - 2018 MantisBT Team