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.

Loading Facebook Comments ...

Leave a Reply

Your email address will not be published. Required fields are marked *