# 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

- 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°. - Iterate through all the other positions and check though no other point exists within this triangle.
- Create a triangle from these positions.
- 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:

- For a given pyramid using points
*p0, p1, p2*and the tip*apex*construct vectors pointing to each pointVector v0 = p0 - apex; Vector v1 = p1 - apex; Vector v2 = p2 - apex;

- 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);

- 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.