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