View Issue Details [ Jump to Notes ] | [ Print ] | ||||||||
ID | Project | Category | View Status | Date Submitted | Last Update | ||||
0001868 | VTK | (No Category) | public | 2005-05-19 08:18 | 2013-04-05 19:57 | ||||
Reporter | Marijn van Stralen | ||||||||
Assigned To | Zhanping Liu | ||||||||
Priority | high | Severity | major | Reproducibility | always | ||||
Status | closed | Resolution | fixed | ||||||
Platform | OS | OS Version | |||||||
Product Version | |||||||||
Target Version | Fixed in Version | ||||||||
Summary | 0001868: vtkTriangle::PointInTriangle returns true if on extended line of line segment | ||||||||
Description | The 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; } | ||||||||
Tags | No tags attached. | ||||||||
Project | |||||||||
Type | |||||||||
Attached Files | vtkTriangle.cxx.patch [^] (1,117 bytes) 1969-12-31 19:00 [Show Content] | ||||||||
Relationships | |
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 |
Notes |
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 |
Issue History |
Copyright © 2000 - 2018 MantisBT Team |