determine of a coordinate is in a quadrilateral

Question

• Hi

I have a problem ( i'm stuck for a few days now) My problem is that I must determine of a coordinate is in a quadrilateral.
To put it simple, I get a coordinate from my GPS and i want to know if I'm on my property.

Does anyone has an idea how to program this? I thought about it a lot and I don't see a simple solution.

Tuesday, April 21, 2009 8:50 AM

All replies

• This looks very interesting.
It seems like - it's more of a Mathematical Geometry and Puzzle Solving rather than a coding challenge.
I would try to come up with a solution i.e. simple and easy to understand.

Suppose,
1. Coordinate of the point under observation - where it is to be decided if it lies inside the quadrilateral or not = P(Xp, Yp)
2. 4 Coordinates of quadrilateral => P(X1, Y1), P(X2, Y2), P(X3, Y3), P(X4, Y4)

Now, check:
If( (Xp > X1 || Xp > X2 || Xp > X3 || Xp > X4)
&&
(Xp < X1 || Xp < X2 || Xp < X3 || Xp < X4)
&&
(Yp > Y1 || Yp > Y2 || Yp > Y3 || Yp > Y4)
&&
(Yp < Y1 || Yp < Y2 || Yp < Y3 || Yp > Y4)
)
{
--  Point P(Xp, Yp) lies inside the quadrilateral  --
}
else
{
--  Point P(Xp, Yp) DOES NOT lie inside the quadrilateral  --

}

Hope, you have understood the logic.
I am trying to check if the X coordinate of the point under observation is greater than any one of the 4- X Corrdinate of the 4-Quadrilaterals.
And, also similarlly - if the Y coordinate of the point under observation is greater than any one of the 4- Y Corrdinate of the 4-Quadrilaterals.

Would be glad to know if it works and solves you requirement.

Regards, Lakra :)
• Edited by Tuesday, April 21, 2009 9:19 AM Updated for better understanding.
Tuesday, April 21, 2009 9:17 AM
• Thanks for the quick reply. I understand it completely.
Hopefully it works because the code is very easy to use.

Thank you again for the reply. :)
Tuesday, April 21, 2009 9:27 AM
• Hi. I think the above algorithm only creates a bounding box around the quadrilateral. Imagine a diamond shape:

P(X1,Y1) = (0,10),   P(X2,Y2) = (10,20),   P(X3,Y3) = (20,10),   P(X4,Y4) = (10,0)

The point P(Xp,Yp) = (2,2) would be considered inside the shape using the algorithm above, but is actually outside.

Tuesday, April 21, 2009 9:42 AM
• Yes, I saw it. I tried the code by testing on a piece of paper and it makes a box round the quadrilateral, as you say. Damn, I thought I had the solution.
Tuesday, April 21, 2009 9:51 AM
• You could take a line at Yp. Work out which sides or your quadrilateral that line crosses by comparing Y coordinates.

Then work out the proportion down the line between Y1 and Y4 (from my example), in this case 2 pixels down. Then work out the same proportion in the difference of X coord between X1 and X4, in my example 2 pixels to the left of X4, giving 8.

8 is the lower bound for Xp. Between point 3 and 4, the other side that's crossed, the upper bound for Xp is 12.

So if Yp = 2, then Xp must be between 8 and 12 to be inside the quadrilateral.

Hope that makes sense. Was a bit rushed. I'll try and work out a better example if I get time.
Tuesday, April 21, 2009 10:03 AM
• This was certainly a very interesting question.

Well, here's the link with method(s) to identify if a point lies inside a quadrilateral/ region or not.