• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 574
  • Last Modified:

Find if a geographical point lies within a set of points making a polygon

Given a set of geographical coordinates making up a polygon, how would I determine if another geographical point (x-latitude, y-longitude) lies either within the polygon, or outside the polygon. The set of coordinates is stored in a table in an SQL server database.
0
websss
Asked:
websss
2 Solutions
 
Paul 1Commented:
The first process is to create a virtual box around the polygon. This gives you a top, bottom, left and right value to see if the target point is close ( T > bottom, T < Top, T > Left and T < Right)

If the value is confirmed then you work out the 3 nearest point to form a triangle and then calculate - check this to see the theory - http://www.blackpawn.com/texts/pointinpoly/

also this explains - http://stackoverflow.com/questions/2049582/how-to-determine-a-point-in-a-triangle
0
 
gurutcCommented:
Are you using  LatLon, UTM, UPS, MGRS, MGRS Polar, USNG (identical to MGRS), Georef, or State Plane coordinate systems?  Depending on the coordinate format, it'll be an algebraic equation.

- gurutc
0
 
gurutcCommented:
Also, what type of polygon?  How many points?
0
What Kind of Coding Program is Right for You?

There are many ways to learn to code these days. From coding bootcamps like Flatiron School to online courses to totally free beginner resources. The best way to learn to code depends on many factors, but the most important one is you. See what course is best for you.

 
Olaf DoschkeSoftware DeveloperCommented:
I used a nice algorithm favorised in raytraycing for this. It counts the number of intersections with a line drawn from the test point and any polygon borders. If that's odd the test point is inside, if it's even the point is not.

Sounds complicated, but if you draw a line exactly in x or latitude direction the determination of intersections gets very simple, also considering you only need to find out, whether there is an intersection with a polygon border, not the point of the intersection.

The algorithm is in the book "An Introduction to Ray Tracing".  Simple logic:

If both y positions of start and end point of a line are below your test point y position, that  means no intersection. Dito, if both y positions are above the test point y position. If one is above and one below, there also is no intersection, if that line crosses the test point y position at an x position before the test point x position. You only need to calculate this, if one of  the x positions is lower and one higher than your test point x position, if both are lower, there is no intersection, as you only want to count intersections in x directions higher than the test point.

You get the idea:  Mostly this is just comparsions, no intersection point calculations. This is used for fast ray traycing and can be applied to your case, too.

Bye, Olaf.

By the way: If you thought there was a simple INSIDEPOLYGON T-SQL Function or system stored proc, I fear that's not the case.
0
 
websssAuthor Commented:
@gurutc, I am using LatLon
0
 
gurutcCommented:
Degree-Decimal?
0
 
websssAuthor Commented:
Decimal..
0
 
gurutcCommented:
The OpenLayers Project has a library of javascript code to perform this function as well as many more.

Their repository and library are here:

OpenLayers Code Collection

This type of function is pretty complex.  But that collection contains the code to do it.

- gurutc
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

Join & Write a Comment

Featured Post

Free Tool: Site Down Detector

Helpful to verify reports of your own downtime, or to double check a downed website you are trying to access.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Tackle projects and never again get stuck behind a technical roadblock.
Join Now