Triangle containsPoint has a bug

Hi guys!
It seems the ‘containsPoint’ method of the ‘Triangle’ class isn’t working correctly. It returns true instead of false. See the example: https://jsfiddle.net/bbmv_/edsq419m/11/

1 Like

This is a nice catch. And it appears, it is just an issue with floating-point fluctuations and how values are tested in the code. The triangle is not a true triangle – it is collapsed into a segment, because the points are co-linear.

Unfortunately, the code in `THREE.Triangle` checks one specific value against 0, but because of the fluctuations this value is -5.551115123125783×10-17. So, the code goes along a wrong path of calculations.

A note for developers. Here is what I found, in case it might be helpful:
https://github.com/mrdoob/three.js/blob/b447ff2911cbefcd650df5a18a905e7df882fc78/src/math/Triangle.js#L58-L67

The value of `denom` is -5.551115123125783e-17 and the check for co-linearity in the `if` statement fails. Here are lines 58-67:

``````const denom = ( dot00 * dot11 - dot01 * dot01 );

// collinear or singular triangle
if ( denom === 0 ) {

// arbitrary location outside of triangle?
// not sure if this is the best idea, maybe should be returning undefined
return target.set( - 2, - 1, - 1 );

}
``````

Thanks Pavel!
Yep, you are right, implementation of this function is not very successful.
I’ve solved the issue for myself - wrote a function in a couple of lines.

why is it wrong tho. the denominator is small but not 0, so the division might still work. Number.MIN_VALUE is 5e-324 which is a long way from 5e-17

The algorithm for calculating barycentric coordinates in the code is the Cramer’s rule for solving 2 linear equations by using determinants. It is known to be numerically unstable even for 2×2 cases. Here is a snapshot from: Accuracy and Stability of Numerical Algorithms

Page 42 (of the PDF) or page 13 (of the book):