Bug in triangulation pointLocation calculations?

I have a snippet of code that is a simplifcation of a problem I've found using the pointLocation feature of MATLAB's triangulation. I believe this to be a numerical bug but am hesitant to submit it as such until I've verified its behavior across multiples platforms. I've reproduced errors with this script on the PC on versions 2018a & 2021b and a different error set on the Mac version 2022a.

Here's the example code, I'll explain what it is and what I would expect after.

clearvars

DemoXY = [0 0;1 0;0.7 -1; 0.6 1];                           % Four XY points
DemoConn = [1 2 3; 1 2 4];                                  % Connectivitiy List
DemoTri = triangulation(DemoConn,DemoXY);                   % Define Triangulation
DemoIdx = DemoTri.pointLocation(0.5,0)                      % Find a point on the shared edge

TestXYGrid = [171.0 126.9; 170.7 127.0; 170.4 127.0; 170.3 127.2];
TestConn = [1 2 3; 2 3 4];
for Scale = [1 1+eps]
    TestTri = triangulation(TestConn,Scale*TestXYGrid);
    TestIdx = TestTri.pointLocation(170.42*Scale, 127*Scale)
end

I'm repeating the same process twice using variables starting with 'Demo' and 'Test.' In each case, I create a 4-point XY convex hull that I triangulate manually. This creates one shared edge between triangles.

I then use the pointLocation operation on the triangulation to determine which triangle contains a point along the shared edge. Either triangle ID would be valid. In the Demo portion of the code, a real value is returned for DemoIdx for all versions and platforms tested. This demonstrates that pointLocation is capable of assigning a point along a shared edge to one triangle within the triangulation.

For the Test portion, when Scale is 1, I get a NaN for TestIdx on all versions tested. The point is within the convex hull so one expects a real value.

On the PC versions 2018a & 2021b, when Scale is not equal to unity (as in the code when it's set to 1+eps) the operation returns a real number (but 2, 3 and 4 also fail, e.g.). On the Mac 2022a version, TestIdx continues to return NaN for values of Scale set to 1, 1+eps, and 10 even though the PC versions returned real values for the second and third.

As I don't have access to the PC version of 2022a I cannot extensively test this. So if someone can repeat my test and let me know if this is a numerical bug I can properly submit it as such.

[nightflight]

I get NaNs on both iterations of the loop on R2020b Update 3 on Windows. It's very frustrating.

Answer 1

[Divyam]

Hi @Wick,

This is a numerical precision issue which may arise because the point you have selected lies exactly on the edge or vertex of the triangle. Thus, the floating-point precision error is causing the "pointLocation" function to assert that the point is located outside the triangle.

As you have correctly determined, adjusting the point location slightly may help your case as it will mitigate the precision error. However, I am unsure as to why the issue persists with values close to in MATLAB R2022a.

For further testing, try fetching the "Barycentric coordinates" using the "pointLocation" method. The points which lie on an edge have at least one "Barycentric coordinate" equal to "zero" while the ones which lie on a vertex have the "Barycentric coordinate" corresponding to that vertex equal to "one" and others equal to "zero". This would help in determining the reason behind the persistence of the NaN for TestIdx.

% Here B are the Barycentric Coordinates
[ID, B] = pointLocation(TR,P);

This issue has been fixed in MATLAB R2022b, consider upgrading to the latest version using this link: https://www.mathworks.com/downloads

For more information regarding fetching the "Barycentric coordinates" using the "pointLocation" function, refer to this example: https://www.mathworks.com/help/matlab/ref/triangulation.pointlocation.html?s_tid=doc_ta#d126e1498788:~:text=%27r%27)-,Enclosing%20Tetrahedra,-Input%20Arguments