Solved

Latitude, Longitude, polygons, and points.

Posted on 2008-06-20
13
3,331 Views
Last Modified: 2009-11-12
Hello,

I am trying to figure out a way to determine whether a give point on a map (literally anywhere on earth) falls within the bounds of a polygon drawn from a list of ordinal lat/lon points.  The polygon could have any number of sides, as long as none intersect.

I am guessing that starting by converting the lat/lon values (which also have a N, S, E, or W associated with them) into a totally numerical representation is how I should start.  If that is correct, what is the best way to do it?

For the record, I already have my lat/lon values converted to a decimal number rather than minutes and seconds, etc.

Does anyone have a good algorithm to determine if the point is inside a polygon that is mapped on the surface of the earth?  I am looking for a very precise way to do this, as the precision is important in this case.
0
Comment
Question by:Perplexity
  • 4
  • 3
  • 2
  • +4
13 Comments
 
LVL 3

Accepted Solution

by:
JayeshKitukale earned 200 total points
ID: 21832613
You need to use one of the algos presented here:
http://local.wasp.uwa.edu.au/~pbourke/geometry/insidepoly/
0
 
LVL 23

Expert Comment

by:Christopher Kile
ID: 21834976
You have a special condition here that is not taken into account by the algorithms in the page to which JayeshKitukale's excellent link points:  since you are working on a closed surface (the flattened sphere of Earth), some sets of your points might form polygons which overlap themselves.  Are your polygons liable to do that?  
0
 

Author Comment

by:Perplexity
ID: 21835412
Thanks for the responses thus far...if I understand the question correctly, the answer is that there should be no self-overlapping polygons.  The points that comprise each polygon are kept in order and no lines can intersect another line in a given polygon.

With that assumption, are those the algorithms to make the determination whether or not a set of coordinates falls within the bounds of a polygon formed by a given ordered set of coordinates?

Thanks again for the guidance.
0
 
LVL 3

Assisted Solution

by:JayeshKitukale
JayeshKitukale earned 200 total points
ID: 21836216
Yes these alogorithms are appropriate for your purpose. Use the 2D alogorithms and not the 3D ones for this purpose. The flattened map of earth is actually 2 dimensional and subject to all 2D calculations.
0
 
LVL 27

Expert Comment

by:aburr
ID: 21836535
"The points that comprise each polygon are kept in order and no lines can intersect another line in a given polygon"
But every adjacent pair of lines intersect ie have a common point. You probably mean that they do not cross.
0
 
LVL 84

Expert Comment

by:ozo
ID: 21836784
If the lines on your map follow great circles, they may not follow straight lines along a cylindrical equidistant projection.
If this makes a difference, you may want to use a gnomonic projection to do your 2-d  point in polygoin test
0
Do You Know the 4 Main Threat Actor Types?

Do you know the main threat actor types? Most attackers fall into one of four categories, each with their own favored tactics, techniques, and procedures.

 
LVL 22

Expert Comment

by:NovaDenizen
ID: 21847042
The easy way is to take the problem into 3D.

Take the lat/lons of the vertices of the polygon and find their (x,y,z).

Move the polygon vertices away from the center of the earth until they all can see each other over the surface of the earth.  

Create a 3d polytope from the aforesaid vertices and the center of the earth.

To test if a point is in the polygon, just take it to 3d and see if it is in the polytope.
0
 
LVL 23

Expert Comment

by:Christopher Kile
ID: 21847753
From what Perplexity has told us, "the point is inside a polygon that is mapped on the surface of the earth."  JayeshKitukale's page of algorithms tell us when a point lies within the polygon on a plane, and whether a point falls within a polyhedron.  

Perplexity,

How accurate do you need this to be?  I ask because I used to get problems from a teacher, who developed models for predictive purposes in her day job.  She gave us a problem once where there was no symbolic solution, but which could be approximate by either circular or sinusoidal approximations (she chose the former, simpler calculation).  In your case, do you need to have your algorithm tell you that a point lies on a polygon on an approximated Earth's surface? The planet is somewhat pear-shaped, but even by simply assuming Earth is a sphere, there can be quite a distance between the surface of a flat polygon described by a plane cutting through each vertex plotted on the Earth's surface as opposed to the actual position on the surface - this sort of thing is sometimes called the approximation error.  As the size of the polygons decreases, the approximation error decreases.  What are the acceptable levels of approximation error for the problem with which you are faced?


0
 
LVL 84

Assisted Solution

by:ozo
ozo earned 100 total points
ID: 21848922
A gnomonic projection would map great circles onto straight lines, so if your polygon edges follow great circles, a 2D point in polygon algorithm on the mapped points may suffice for you.
It your points span more than a hemisphere, it may be hard to do a gnomonic projection,
(but it could also be problematic to decide which side of the polygon is meant to be the inside)
0
 
LVL 23

Assisted Solution

by:Christopher Kile
Christopher Kile earned 100 total points
ID: 21849036
Gnomonic projects don't of themselves answer the problem because there is no guarantee that more than one edge of a polygon will lie along a "great circle."  I also suggest that if you go down this track, you will have to compose a Dymaxion Map (http://en.wikipedia.org/wiki/Dymaxion_Map) which is not a trivial task.

I resubmit my question to Perplexity:  How accurate does this need to be?

0
 

Assisted Solution

by:wthengineering
wthengineering earned 100 total points
ID: 21904757
Here is an algorithm that I use to do exactly what you are describe.  This works for any clean 2D polygons including complex doughnut shaped boundaries.

General: Imagine a ray starting at the point in question and extending due north to infinity.  Count the number of boundary line segments that this ray intersects.  If the number is odd then the point is inside the boundary, otherwise it is outside the boundary.    

Details:
IntersectionCount=0
Foreach boundary segment
    If Pt.x is between segment.x1 and segment.x2
        Calculate the y value where ray intersects this segment
        If y is north of Pt.y
            Increment IntersectionCount
If IntersectionCount is Odd
    Point IS in boundary
Else
    Point is NOT in boundary

Note that the above summary does not go into the more complex situation where one or more boundary points have the EXACT same x value as the x value of the point in question.
0
 
LVL 84

Expert Comment

by:ozo
ID: 21905089
(unless your polygon includes the north pole) due north is a good direction to pick, since a north-south great circle easily maps to latitude longitude coordinates,
however, care is still needed to do the
   Calculate the y value where ray intersects this segment
step properly

0
 
LVL 84

Expert Comment

by:ozo
ID: 21905101
> there is no guarantee that more than one edge of a polygon will lie along a "great circle."
So one edge is guaranteed but the other edges are not?
How are the edges defined if not by great circles?  are they loxodromes? some other curve?
0

Featured Post

How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

Join & Write a Comment

Article by: Nadia
Linear search (searching each index in an array one by one) works almost everywhere but it is not optimal in many cases. Let's assume, we have a book which has 42949672960 pages. We also have a table of contents. Now we want to read the content on p…
This article seeks to propel the full implementation of geothermal power plants in Mexico as a renewable energy source.
This tutorial demonstrates how to identify and create boundary or building outlines in Google Maps. In this example, I outline the boundaries of an enclosed skatepark within a community park.  Login to your Google Account, then  Google for "Google M…
This tutorial walks through the best practices in adding a local business to Google Maps including how to properly search for duplicates, marker placement, and inputing business details. Login to your Google Account, then search for "Google Mapmaker…

706 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

18 Experts available now in Live!

Get 1:1 Help Now