S3E11: A point-in-triangle detection algorithm

Описание: In this episode we look at "an amazing problem", see below, in which we are required to come up with an algorithm for detecting whether a given point is located strictly OUT or strictly INside of a given (planar) Euclidean triangle.

To that end, we, first, discuss three honorable mention algorithm and then deep-dive into the underlying mathematics of the algorithm of interest.

The first honorable mention is an approach that is based on the so-called 2-space ray tracing that, fundamentally, hails from ray optics and amounts to the analysis of the objects or of the geometry that is seen from the perspective of a ray of light emitted from a point light source which, in this case, is the sample point to test.

The second honorable mention is an approach that is based on the following theorem. A point, P, is located strictly inside of a given triangle, ABC, if and only if the sum of the magnitudes of the angles under which all three sides of the given triangle are seen from that point P is equal to 2*pi radians.

The third honorable mention is an approach that is based on the following theorem. A point, P, is located strictly inside of a given triangle, ABC, if and only if the non-zero areas of the triangles APC, CPB and BPA sum to the area of the given triangle, ABC.

Lastly, we look at the algorithm that is the main hero of this episode. The basic idea of that algorithm is very straightforward, it can be comprehended by any sufficiently motivated middle school student and amounts to a geometric fact that a given straight line partitions the parent, ambient, plane into two half planes, each of which generates a real number that has a sign that is opposite to the sign that is generated by "the other" half plane.

We show a straightforward proof of that fact and then we carry out four, no less, sample computations that illustrate the idea that the direction in which the vertices of the given triangle are traversed, counter- or clockwise, makes no difference for this algorithm, provided, of course, that we are consistent in the way in which we compute the values of the so-called "location predicates".

In conclusion we show a suggestion for a sample implementation of this algorithm in the best programming language of all times, C.

*In mathematics there exist a rich set of problems each of which has the following property: every time we look at such a problem, we come up with a new solution for that problem. We refer to this type of problems as "an amazing" problem and the problem of detecting whether a given point is in our outside of a given triangle is precisely that, "an amazing" problem that admits many different solutions.

If you know of other ways of solving this problem then share it with our community in the comments section.