Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
in case of a triangle, for instance, perhaps you could try showing that your given point is inside each of its angles. E.g. first take $\angle BAC$ and your point $D$. Show that $D$ is inside this angle by proving that $\angle DAB + \angle DAC = \angle BAC$ (vectors could be useful here...) –  W_D Sep 12 '13 at 9:11
add comment

3 Answers 3

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

share|improve this answer
    
we can can express the position of the fourth point if we have a rectangle but the OP's example is not a rectangle. –  Soosh Sep 12 '13 at 10:31
    
@AmirNoori: Barycentric coordinates work with the vertices of a simplex, which is a triangle (not a rectangle) in two dimensions. The OP's Question is a little confusing in that the subject line asks about a point inside a triangle, but then gives data about a point inside a quadrilateral (two triangles). –  hardmath Sep 12 '13 at 12:34
add comment

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.

share|improve this answer
add comment

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/

share|improve this answer
    
The charitable interpretation is that the given quadrilateral can be decomposed into two triangles, so a question about whether a point is inside the quadrilateral amounts to a question about which of two triangles the point belongs to (if either). –  hardmath Sep 12 '13 at 12:39
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.