Solved

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

Posted on 2014-01-22
8
523 Views
Last Modified: 2014-02-11
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
Comment
Question by:websss
8 Comments
 
LVL 3

Expert Comment

by:Paul 1
ID: 39802256
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
 
LVL 16

Expert Comment

by:gurutc
ID: 39803078
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
 
LVL 16

Expert Comment

by:gurutc
ID: 39803081
Also, what type of polygon?  How many points?
0
 
LVL 29

Assisted Solution

by:Olaf Doschke
Olaf Doschke earned 200 total points
ID: 39803680
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
PRTG Network Monitor: Intuitive Network Monitoring

Network Monitoring is essential to ensure that computer systems and network devices are running. Use PRTG to monitor LANs, servers, websites, applications and devices, bandwidth, virtual environments, remote systems, IoT, and many more. PRTG is easy to set up & use.

 

Author Comment

by:websss
ID: 39805705
@gurutc, I am using LatLon
0
 
LVL 16

Expert Comment

by:gurutc
ID: 39806255
Degree-Decimal?
0
 

Author Comment

by:websss
ID: 39806264
Decimal..
0
 
LVL 16

Accepted Solution

by:
gurutc earned 300 total points
ID: 39806289
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

Featured Post

How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

Join & Write a Comment

I wrote this interesting script that really help me find jobs or procedures when working in a huge environment. I could I have written it as a Procedure but then I would have to have it on each machine or have a link to a server-related search that …
Everyone has problem when going to load data into Data warehouse (EDW). They all need to confirm that data quality is good but they don't no how to proceed. Microsoft has provided new task within SSIS 2008 called "Data Profiler Task". It solve th…
Using examples as well as descriptions, and references to Books Online, show the documentation available for date manipulation functions and by using a select few of these functions, show how date based data can be manipulated with these functions.
This videos aims to give the viewer a basic demonstration of how a user can query current session information by using the SYS_CONTEXT function

708 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

17 Experts available now in Live!

Get 1:1 Help Now