Determine if a point is inside a triangle formed b

Question

I have 3 points ( lat , lon ) that form a triangle.How can i find if a point is inside this triangle?

Answer 1

function SameSide(p1,p2, a,b)
    cp1 = CrossProduct(b-a, p1-a)
    cp2 = CrossProduct(b-a, p2-a)
    if DotProduct(cp1, cp2) >= 0 then return true
    else return false

function PointInTriangle(p, a,b,c)
    if SameSide(p,a, b,c) and SameSide(p,b, a,c)
        and SameSide(p,c, a,b) then return true
    else return false

Explained at the link below

http://www.blackpawn.com/texts/pointinpoly/default.html

Answer 2

You can use point-polygon test.

It's simple. Draw a line from your point to East for a big enough distance. Count the number of times that line intersects with your plygon. If it's even, your point is outside, if odd, its inside.

That works for any type of polygon.

Answer 3

Here's a Javascript implementation of the barycentric coordinates solution discussed here:

// Returns true if point P inside the triangle with vertices at A, B and C
// representing 2D vectors and points as [x,y]. Based on                        
// http://www.blackpawn.com/texts/pointinpoly/default.html
function pointInTriange(P, A, B, C) {
  // Compute vectors        
  function vec(from, to) {  return [to[0] - from[0], to[1] - from[1]];  }
  var v0 = vec(A, C);
  var v1 = vec(A, B);
  var v2 = vec(A, P);
  // Compute dot products
  function dot(u, v) {  return u[0] * v[0] + u[1] * v[1];  }
  var dot00 = dot(v0, v0);
  var dot01 = dot(v0, v1);
  var dot02 = dot(v0, v2);
  var dot11 = dot(v1, v1);
  var dot12 = dot(v1, v2);
  // Compute barycentric coordinates
  var invDenom = 1.0 / (dot00 * dot11 - dot01 * dot01);
  var u = (dot11 * dot02 - dot01 * dot12) * invDenom;
  var v = (dot00 * dot12 - dot01 * dot02) * invDenom;
  // Check if point is in triangle
  return (u >= 0) && (v >= 0) && (u + v < 1);
}

It's said to be faster than the cross-product based solutions.

Answer 4

Try the ray casting algorithm.

http://en.wikipedia.org/wiki/Point_in_polygon

It is pretty simple to implement.

Answer 5

The main question is whether you can use a 2D approximation for this (in other words, is your triangle small enough).

If so, something simple like barycentric coordinates will work well.

Answer 6

I've done something like this today! Also with (lat, lon), actually (theta, phi), although I knew a little more about the mesh I was working with. I'm working with (theta, phi) with 0 <= theta <= PI && 0 <= phi <= 2*PI.

You'll find that you might have some trouble if one of the vertices is at the top or bottom of your sphere, since in my case phi isn't really defined. You end up with a singularity there. You've basically got a square, which makes it easier to check whether your point lies within it or not.

In all other cases, if you've converted your point into (lat, lon) / (theta, phi). It should be simple to just use the method as described by @Michelle Six.