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.

Improve this question

2 Answers 2

Reset to default
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.
Improve this answer
4
  • 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
    Commented May 8, 2018 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
    Commented May 8, 2018 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
    Commented May 8, 2018 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
    Commented May 8, 2018 at 23:39
1

This video explains it very clear to understand. https://youtu.be/RSXM9bgqxJM?si=zKVuHF_YtrcTS7Ec

Improve this answer
2
  • 1
    Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center.
    – Community Bot
    Commented Aug 18 at 12:27
  • Thanks for sharing this @Jacob 🚀
    – Tim
    Commented Sep 27 at 18:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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