Determine if a point is inside a triangle formed by 3 points with given latitude/longitude

I have 3 points ( lat , lon ) tha开发者_StackOverflowt form a triangle.How can i find if a point is inside this triangle?

Java Code for just triangle , that is 3 points.

    public static boolean pntInTriangle(double px, double py, double x1, double y1, double x2, double y2, double x3, double y3) {

    double o1 = getOrientationResult(x1, y1, x2, y2, px, py);
    double o2 = getOrientationResult(x2, y2, x3, y3, px, py);
    double o3 = getOrientationResult(x3, y3, x1, y1, px, py);

    return (o1 == o2) && (o2 == o3);
}

private static int getOrientationResult(double x1, double y1, double x2, double y2, double px, double py) {
    double orientation = ((x2 - x1) * (py - y1)) - ((px - x1) * (y2 - y1));
    if (orientation > 0) {
        return 1;
    }
    else if (orientation < 0) {
        return -1;
    }
    else {
        return 0;
    }
}

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.

Most languages include a function for this. In Java it's Polygon.contains() http://docs.oracle.com/javase/7/docs/api/java/awt/Polygon.html

Simply create a polygon from your points, and then call contains() on your test point.

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.

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.

Try the ray casting algorithm.

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

It is pretty simple to implement.

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

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.