| I would like some code that finds the intersection of two spherical polygons. For simplicity, consider both polygons to be on the surface of earth — which, also for simplicity, should be considered a perfect sphere.
The software input is two text files. Each text file contains a listing of coordinates of a single polygon.
Find the intersection of the two polygons and provide the result. The result will either be no intersection, a polygon, or multiple polygons. If the result is a polygon are multiple polyongs, create text files in the same format as the input.
No user interface is needed. You can make the text files have static names and always be in static locations (like c:testpolygon1.txt).
Some relevant information can be found online by googling "intersecting spherical polygons". These sources may be useful for someone with a good engineering or mathematics background. Please do account for the spherical nature of the problem (the flat surface version of the problem is one I can already solve and program myself).
Any programming language can be used. Please ask if you have questions.
Regards, jagusa
—INPUT FILE DETAILS—
Example Input
polygon1.txt 34.404733,-119.843950 34.408415,-119.853527 34.422013,-119.853494 34.414226,-119.839684 34.404733,-119.843950
polygon2.txt 34.417403,-119.859704 34.424537,-119.859925 34.424190,-119.845465 34.417297,-119.845858 34.417403,-119.859704
Explanation: Each line is vertex of the polygon provides as: latitude, longitude(in decimal degrees; WGS84, if that matters). Note that the first and last coordinates close the polygon and, thus, are always the same; vertices are given clockwise. Positive latitudes value are the northern hemisphere (like 45 means 45 degrees North), negative latitudes are in the southern hemisphere (-12.5 would mean 12.5 degrees South). Also, positive longitudes are in the eastern hemisphere; negative are the western hemisphere. You can cut, past, then search for the individual coordinates in Google Local for clarification.
————– Another sample of textfile inputs:
polygonA.txt 7.692156,77.450609 22.959595,89.906700 -0.959211,109.195114 7.692156,77.450609
polygonB.txt -8.585513,114.841715 -2.843772,100.030245 8.940580,105.278561 -8.585513,114.841715
Additional information submitted:
10/20/2005 at 5:17 EDT:
I am preparing to make the bid selection. I have attached an example .gif file which might be helpful. Feel free to send me a message via pmb if you have any final questions. Thank you all for bidding!
10/20/2005 at 13:31 EDT:
In response to several of bidders’ questions —
Source code and a description of a similar, non-spherical version of the problem can be found at:
http://www.codeguru.com/article.php/c8965
Writing the code built upon GNU-license source is fine. My purpose is for discussion in academic community. After reviewing literature on the problem, a large amount of information can be found using the search terms "clipping polygons".
The following ACM paper appears to address the algorithm (maybe?) — http://portal.acm.org/citation.cfm?doid=159730.159732
regards, jagusa
Additional files submitted:
polygons.gif |