Answered by:
determine of a coordinate is in a quadrilateral

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.
Thanks in advance.
Question
Answers

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.
http://sites.google.com/site/abylexsite/Home/dotnet/determineifthepointliesinsidetheregion
Hope, it helps. Please remember to Mark as Answer if it does so.
Happy Coding!
Regards, Lakra :) Proposed as answer by Abhijeet Lakra Wednesday, April 22, 2009 5:04 AM
 Marked as answer by metalloid Wednesday, April 22, 2009 6:26 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.
Please find the below algorithm:
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 4Quadrilaterals.
And, also similarlly  if the Y coordinate of the point under observation is greater than any one of the 4 Y Corrdinate of the 4Quadrilaterals.
Would be glad to know if it works and solves you requirement.
Regards, Lakra :) Edited by Abhijeet Lakra Tuesday, April 21, 2009 9:19 AM Updated for better understanding.


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.


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. 
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.
http://sites.google.com/site/abylexsite/Home/dotnet/determineifthepointliesinsidetheregion
Hope, it helps. Please remember to Mark as Answer if it does so.
Happy Coding!
Regards, Lakra :) Proposed as answer by Abhijeet Lakra Wednesday, April 22, 2009 5:04 AM
 Marked as answer by metalloid Wednesday, April 22, 2009 6:26 AM
