4

I'm looking for a simple explanation on how to detect if GPS coordinates fall within a polygon of points.

I would prefer an explanations that can be done using paper and pencil and not programming language specific.

If I have a list of points (latitude and longitude in degrees) that makes up a polygon. How can I tell if a point falls withing that polygon.

The only data I have access to is the polygon points and the point to check. An example is: 41.21,-104.77(point to check) then I have polygon points (39.39 -101.69 + 48.8335,-106.2435 + 38.803,-109.5781 + 39.4413,-111.043 + 45.6336,-113.7162 + 48.8335,-106.2435)

enter image description here

I found a Java specific answer and an R specific answer but I am looking for a programming language agnostic answer. Something written in plain English/step by step.

7

If you want a really simple algorithm how about this:

  • Take your point and draw a straight line to the bounding box of your polygon.
  • Count how many times it crosses the polygon boundary.
  • If number is odd it must be inside, if even it must be outside.
  • The only data I have access to is the polygon points and the point to check. An example is: 41.21,-104.77(point to check) then I have polygon points (39.39 -101.69 + 48.8335,-106.2435 + 38.803,-109.5781 + 39.4413,-111.043 + 45.6336,-113.7162 + 48.8335,-106.2435) Is there a way to find it with just this info? it seems like the solution above I would need a list of all the points for boundaries... which I do not have. Thanks! – Tim May 8 '18 at 22:11
  • Awesomely simple implementation of the odd/even rule. Tim, you can only work with the points you have.. those will have to do. find your minimum X and use the Y of the point then imagine a line segment Xmin, Y to X, Y. You can skip any polygon segment not in the range of your points' Y coordinate otherwise for each segment see if the intersection occurs mathsfirst.massey.ac.nz/Algebra/SystemsofLinEq/EMeth.htm the intersection should be in the bounds of the imaginary line and segment or they don't intersect, count the ones that do and if the modulus of that by 2 is 1 you're inside. – Michael Stimson May 8 '18 at 22:21
  • @MichaelStimson I am still a little fuzzy on how to do that. Unfortunately I am not a GIS wiz... Is there a way you could give an answer/example showing a step by step solution on how to do this using the points given in my question? I need to see the process of how someone would do this so I can recreate it. If it helps I am okay with pseudo code, as long as it shows the entire process of how the problem is solved. Thanks! – Tim May 8 '18 at 23:31
  • It's high school math, the simultaneous solution of two equations to find the point of intersection but the intersection could be out of range which is why you need to constrain.. it should be enough to find the X of the intersection between the minimum X point of the polygon and your GPS X point. First step is to find the equation for both segments (mathsisfun.com/algebra/line-equation-2points.html) then solve to find the point that satisfies both. It's been a very long time since high school which is why I'd use OGR geometry within method, but perhaps I'm just lazy. – Michael Stimson May 8 '18 at 23:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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