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

Question

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

Answer 1

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

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

Answer 2

Try the ray casting algorithm.

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

It is pretty simple to implement.

Answer 3

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 4

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