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

Question

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

Answer 1

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

If so, then something as simple as barycentric coordinates will work well.

Answer 2

Java code for a simple triangle, i.e. 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; } } 

Answer 3

Most languages ​​have a function for this. In Java, this is Polygon.contains () http://docs.oracle.com/javase/7/docs/api/java/awt/Polygon.html

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

Answer 4

Here is the implementation of the Javascript solution for barycentric coordinates:

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

He said he is faster than cross-product solutions.

Answer 5

You can use the polygon test.

It's simple. Draw a line from your point to the East over a fairly large distance. Count the number of times the line crosses with your plygon. Even if it is, your point is outside, if odd, inside.

This works for any type of polygon.

Answer 6

Try the ray casting algorithm.

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

This is pretty easy to implement.

Answer 7

 function SameSide(p1,p2, a,b) cp1 = CrossProduct(ba, p1-a) cp2 = CrossProduct(ba, 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 

Explanation of the link below

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

Answer 8

Today I did something similar! Also with (lat, lon), actually (theta, phi), although I knew a little more about the grid I was working with. I work with (theta, phi) with 0 <= theta <= PI && 0 <= phi = 2 * PI.

You will find that you may have problems if one of the vertices is in the upper or lower part of the sphere, since in my case phi is not defined. You end up with a feature. You basically have a square that makes it easy to check if your point is in it or not.

In all other cases, if you converted your point to (lat, lon) / (theta, phi). You just need to use the method described by @Michelle Six.