Infinite triangular pyramid

Playing around with triangulating using the ear clipping technique and had the issue of trying to determine if a point in 3D space overlapped a triangular area.

In brief the ear clipping technique consists of

1. Find a set of 3 points p0, p1, p2 where the tip p1 is convex i.e. the angle between p0-p1 and p1-p2 is < 180°.
2. Iterate through all the other positions and check though no other point exists within this triangle.
3. Create a triangle from these positions.
4. Remove p1 from the list of points and continue searching for the next triangle.

Step 2 was causing a little bit of an issue. There are plenty of sites out there that will describe how to check if a point is inside or outside a 2D triangle, but not much for 3D.

Turns out in my case it is pretty easy. Since I’m working on adding a polygon onto the surface of the earth I am working off an ellipsoid. I can therefore extend the triangle back to the centre of the earth and create a triangular pyramid. The maths is pretty easy:

1. For a given pyramid using points p0, p1, p2 and the tip apex construct vectors pointing to each point

   Vector v0 = p0 - apex;
   Vector v1 = p1 - apex;
   Vector v2 = p2 - apex;
   

2. Take a pair of these vectors and use them to create a plane normal

   Vector n0 = p0.cross(p1);
   Vector n1 = p1.cross(p2);
   Vector n2 = p2.cross(p0);
   

3. Finally use these to calculate the which side of the plane the point is on

   Vector pointToApex = point - apex;
   return pointToApex.dot(n0) < 0 &&
    pointToApex.dot(n1) < 0 &&
    pointToApex.dot(n2) < 0;
   

That should do the trick. Of course a nice little optimisation there is if the apex is at the centre of the earth (i.e. 0, 0, 0) then all the subtractions can be skipped.