How can I prove a point is within a triangle, given three other points?

Question

Could someone please explain the formula behind this, and then provide an example of how to do this? Basically I have 4 points, each with a longitude and latitude number. (They make a polygon quad, so a square or rectangle, in the shape of two triangles.) I then have a user's point. This is their location, also in the form of latitude and longitude coordinates. What is the process I need to determine if that point is INSIDE the square (or two triangles)?

For example, I may have four points:

Point A: x = 5, y = 0

Point B: x = 10, y = 0

Point C: x = 4, y = 3

Point D: x = 10, y = 3

User Point Z: x = 7, y = 2

If I were to draw this out on a graph, I can see that "Z" is clearly inside the polygon. However, how can I prove this with math, rather than relying on graph paper?

Thank you!

Answer 1

You can express the position of the fourth point in Barycentric Co-ordinates by reference to the first three. If these are all positive the fourth point lies in the triangle defined by the first three. If one co-ordinate is zero, the fourth point lies on a side, and if two are zero, the fourth is at a vertex (ie one of the original points).

Answer 2

How come do you think that there are just 2 triangles? You can make 4 triangles out of 4 points.

BTW -> this page will give you some hints: http://www.blackpawn.com/texts/pointinpoly/

Answer 3

This is the classical "point in polygon" problem. There are two ways to attack it -- one way is to use ray casting, and the other is to use winding numbers.

You'll find lots of other material if you search for "point in polygon". Here is one link, and here is another one.

You can solve the point-in-polygon problem by repeatedly solving the point-in-triangle problem, but you have to do it carefully if the polygon is not convex. See the second link above for details.