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

    Please find the below algorithm:
    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  --
        --  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 Abhijeet Lakra 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.

    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
    Wednesday, April 22, 2009 5:02 AM
  • Thanks Aby. I will try it out momentarily.

    edit: it works! Thank you guys.
    Wednesday, April 22, 2009 6:27 AM