球体表面上(经度，纬度)点的凸包 [英] Convex hull of (longitude, latitude)-points on the surface of a sphere

问题描述

标准凸包算法不适用于(经度，纬度)点，因为标准算法假定您需要一组笛卡尔点的壳.纬度-经度点不是笛卡尔坐标系，因为经度在反子午线(+/- 180度)处环绕".也就是说，经度179以东两度为-179.

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?

现在，我想一想，有很多有趣的案例要比跨越反子午线要考虑的多.考虑环绕地球的点带"-它的凸包没有东西边界.甚至更进一步，{(0,0)，(0、90)，(0，-90)，(90、0)，(-90、0)，(180、0)}的凸包是什么? -它似乎包含地球的整个表面，那么在其周界上有哪些点呢?

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?

推荐答案

标准凸包算法不会因为地球表面坐标的环绕而失败，而是遇到了更为根本的问题.球体的表面(不要忘了地球的非球形)不是欧几里得空间，因此欧几里得几何学不起作用，而凸包例程则假定基础空间是欧几里得(向我展示其中一个不存在). t，请)将无法正常工作.

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.

向您开放的一种方法是采用测地学凸度的定义并实施测地学凸包例行程序.看起来很毛.而且它可能不会产生符合您(通常是欧几里得)期望的结果.在许多情况下，对于3个任意点，凸包都是球体的整个表面.

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.

导航员和制图师千古以来一直采用的另一种方法是将球体表面的一部分(包含所有点的一部分)投影到欧几里得空间(这是地图投影的主题，我会'请参考其中的大量文献来打扰您，并找出投影点的凸包.将您感兴趣的区域投影到平面上并调整坐标，以使其不会环绕；例如，如果您对法国感兴趣，可以通过加30度来调整所有经度，以使整个国家都由+ ve个数字进行协调.

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.

在撰写本文时，@ Li-aung Yip的答案中提出的使用3D凸包算法的想法让我误以为是.一组表面点的3D凸包将包括位于球体内的点，边和面.这些从字面上看并不存在于球的2D曲面上，只会将您的困难从从2D中不太正确的概念进行角力转变为在3D中完全出错的困难.此外，我从Wikipedia文章中了解到，我提到了一个封闭的半球(即包括其赤道"的半球)在球表面的几何形状上不是凸的.

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.

这篇关于球体表面上(经度，纬度)点的凸包的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！