Convex hull of (longitude, latitude)-points on the

问题:

Standard convex hull algorithms will not work with (longitude, latitude)-points, because standard algorithms assume you want the hull of a set of Cartesian points. Latitude-longitude points are not Cartesian, because longitude "wraps around" at the anti-meridian (+/- 180 degrees). I.e., two degrees east of longitude 179 is -179.

So if your set of points happens to straddle the anti-meridian, you will compute spurious hulls that stretch all the way around the world incorrectly.

Any suggestions for tricks I could apply with a standard convex hull algorithm to correct for this, or pointers to proper "geospherical" hull algorithms?

Now that I think on it, there are more interesting cases to consider than straddling the anti-merdian. Consider a "band" of points that encircle the earth -- its convex hull would have no east/west bounds. Or even further, what is the convex hull of {(0,0), (0, 90), (0, -90), (90, 0), (-90, 0), (180, 0)}? -- it would seem to contain the entire surface of the earth, so which points are on its perimeter?

回答1:

Standard convex hull algorithms are not defeated by the wrapping-around of the coordinates on the surface of the Earth but by a more fundamental problem. The surface of a sphere (let's forget the not-quite-sphericity of the Earth) is not a Euclidean space so Euclidean geometry doesn't work, and convex hull routines which assume that the underlying space is Euclidean (show me one which doesn't, please) won't work.

The surface of the sphere conforms to the concepts of an elliptic geometry where lines are great circles and antipodal points are considered the same point. You've already started to experience the issues arising from trying to apply a Euclidean concept of convexity to an elliptic space.

One approach open to you would be to adopt the definitions of geodesic convexity and implement a geodesic convex hull routine. That looks quite hairy. And it may not produce results which conform to your (generally Euclidean) expectations. In many cases, for 3 arbitrary points, the convex hull turns out to be the entire surface of the sphere.

Another approach, one adopted by navigators and cartographers through the ages, would be to project part of the surface of the sphere (a part containing all your points) into Euclidean space (which is the subject of map projections and I won't bother you with references to the extensive literature thereon) and to figure out the convex hull of the projected points. Project the area you are interested in onto the plane and adjust the coordinates so that they do not wrap around; for example, if you were interested in France you might adjust all longitudes by adding 30deg so that the whole country was coordinated by +ve numbers.

While I'm writing, the idea proposed in @Li-aung Yip's answer, of using a 3D convex hull algorithm, strikes me as misguided. The 3D convex hull of the set of surface points will include points, edges and faces which lie inside the sphere. These literally do not exist on the 2D surface of the sphere and only change your difficulties from wrestling with the not-quite-right concept in 2D to quite-wrong in 3D. Further, I learned from the Wikipedia article I referenced that a closed hemisphere (ie one which includes its 'equator') is not convex in the geometry of the surface of the sphere.

回答2:

Instead of considering your data as latitude-longitude data, could you instead consider it in 3D space and apply a 3D convex hull algorithm? You may be able to then find the 2D convex hull you desire by analysing the 3D convex hull.

This returns you to well-travelled algorithms for cartesian convex hulls (albeit in three dimensions) and has no issues with wrap around of the coordinates.

Alternately, there's this paper: Computing the Convex Hull of a Simple Polygon on the Sphere (1996) which seems to deal with some of the same issues that you're dealing with (coordinate wrap-around, etc.)

回答3:

If all your points are within a hemisphere (that is, if you can find a cut plane through the center of the Earth that puts them all on one side), then you can do a central a.k.a. gnomic a.k.a. gnomonic projection from the center of the Earth to a plane parallel to the cut plane. Then all great circles become straight lines in the projection, and so a convex hull in the projection will map back to a correct convex hull on the Earth. You can see how wrong lat/lon points are by looking at the latitude lines in the "Gnomonic Projection" section here (notice that the longitude lines remain straight).

(Treating the Earth as a sphere still isn't quite right, but it's a good second approximation. I don't think points on a true least-distance path across a more realistic Earth (say WGS84) generally lie on a plane through the center. Maybe pretending they do gives you a better approximation than what you get with a sphere.)

回答4:

FutureNerd:

You are absolutely correct. I had to solve the exact same problem as Maxy-B for my application. As a first iteration, I just treated (lng,lat) as (x,y) and ran a standard 2D algorithm. This worked fine as long as nobody looked too close, because all my data were in the contiguous U.S. As a second iteration, though, I used your approach and proved the concept.

The points MUST be in the same hemisphere. As it turns out, choosing this hemisphere is non-trivial (it's not just the points' center, as I had initially guessed.) To illustrate, consider the following four points: (0,0), (-60,0), (+60,0) along the equator, and (0,90) the north pole. However you choose to define "center", their center lies on the north pole by symmetry and all four points are in the Northern Hemisphere. However, consider replacing the fourth point with, say (-19, 64) iceland. Now their center is NOT on the north pole, but asymmetrically drawn toward iceland. However, all four points are still in the Northern Hemisphere. Further, the Northern Hemisphere, as uniquely defined by the North Pole, is the ONLY hemisphere they share. So calculating this "pole" becomes algorithmic, not algebraic.

See my repository for the Python code: https://github.com/VictorDavis/GeoConvexHull