구면의 (경도, 위도) 볼록한 선체

Question

표준 볼록 선체 알고리즘은 (경도, 위도) - 점과 함께 작동하지 않습니다. 표준 알고리즘은 데카르트 점 집합의 선체를 원하기 때문입니다. 위도 - 경도 점은 이 아니고 데카르트 식입니다. 경도가 반 자오선 (+/- 180도)에서 "랩 어라운드"하기 때문입니다. 즉, 경도 179에서 동쪽으로 2도 -179입니다.

포인트 세트가 반 자오선에 걸 치면 전 세계의 모든 곳에서 잘못 늘어나는 가짜 선체를 계산하게됩니다.

트릭에 대한 제안 표준 볼록 헐 알고리즘을 사용하여이를 보정하거나 올바른 "지구 대기"헐 알고리즘을 가리키는 포인터를 적용 할 수 있습니까?

이제 나는 그것에 대해 생각해 보면 반 merdian에 걸쳐있는 것보다 고려해야 할 흥미로운 사례가 있습니다. 지구를 둘러싼 지점의 "띠"를 고려하십시오 - 볼록 선체에는 동/서 경계가 없습니다. 또는 {(0,0), (0,90), (0, -90), (90,0), (-90,0), (180,0)}의 볼록한 선체는 무엇입니까? - 그것은 지구의 전체 표면을 포함하는 것처럼 보일 것입니다. 그래서 어떤 점들이 그 둘레에 있습니까?

Answer 1

표준 볼록 선체 알고리즘이 포장에 의해 격파되지 않습니다 (랩 어라운드 등을 조정) - 지구 표면의 좌표에 대한 근본적인 문제. 구의 표면은 유클리드 공간이 아니므로 유클리드 기하학은 작동하지 않습니다. 그리고 밑에있는 공간이 유클리드라고 가정하는 볼록 선체 루틴 (내게 ' t, 제발) 작동하지 않습니다.

구면은 ​​elliptic geometry의 개념을 따르며, 여기서 선은 큰 원이고 정다면 점은 같은 점으로 간주됩니다. 타원형 공간에 유클리드 개념의 볼록 개념을 적용하려고 시도하면서 발생하는 문제를 이미 경험하기 시작했습니다.

접근 방식 중 하나는 geodesic convexity의 정의를 채택하고 측지 볼록 선체 루틴을 구현하는 것입니다. 그건 꽤 털이 보입니다. 그리고 귀하의 (일반적으로 유클리드) 기대에 부합하는 결과를 산출하지 못할 수도 있습니다. 많은 경우, 임의의 3 점에 대해 볼록한 선체가 구의 전체 표면으로 밝혀졌습니다.

나이를 거쳐 네비게이터와지도 제작자가 채택한 또 다른 접근법은 구의 표면 부분 (모든 점을 포함하는 부분)을 유클리드 공간으로 투영하는 것입니다 (이는지도 투영의 대상이며, 그 너머의 광범위한 문헌에 대한 언급으로 귀찮게하지 말 것) 그리고 투영 된 점들의 볼록한 선체를 알아내는 것. 관심있는 영역을 비행기에 투영하고 주위를 감싸지 않도록 좌표를 조정하십시오. 예를 들어, 프랑스에 관심이 있다면 30deg를 추가하여 모든 경도를 조정할 수 있습니다. 그러면 전체 국가가 + 숫자로 조정됩니다.

필자는 @ Li-aung Yip의 대답에서 3D 볼록 선체 알고리즘을 사용하여 아이디어를 제안했지만 잘못 생각했다.표면 점 집합의 3D 볼록 선체에는 구형 내부에있는 점, 모서리 및면이 포함됩니다. 이것들은 말 그대로 구면의 2D 표면에 존재하지 않으며 단지 2D에서의 상당히 옳지 않은 개념과 3D에서 상당히 잘못된 것에 대한 어려움을 변화시킵니다. 더구나 나는 닫힌 반구 (즉, 적도를 포함하는 것)가 구면의 기하학에 볼록하지 않다는 것을 언급 한 Wikipedia 기사에서 배웠다.

Answer 2

데이터를 위도 - 경도 데이터로 간주하는 대신 3D 공간에서 고려하고 3D convex hull algorithm을 적용 할 수 있습니까? 그런 다음 3D 볼록 선체를 분석하여 원하는 2D 볼록 선체를 찾을 수 있습니다.

이것은 (3 차원 임에도 불구하고) 직교하는 볼록 선체에 대한 잘 여행 된 알고리즘으로 돌아가며 좌표의 줄 바꿈에 문제가 없습니다.

다른 방법으로,이 논문이있다 : 당신이 상대하고 같은 몇 가지 문제를 다루는 것 Computing the Convex Hull of a Simple Polygon on the Sphere (1996)이

Answer 3

모든 점이 반구 내에 있으면 (즉, 지구의 중심을 통과하여 한면에 모든 곡면이있는 절단면을 찾을 수 있다면) 중앙 일명 지니고있는 니모닉 투영을 지구 중심을 절단면에 평행 한 평면에 맞 춥니 다. 그런 다음 모든 큰 원이 투영에서 직선이되므로 투영의 볼록한 선체가 지구의 올바른 볼록 선체로 다시 매핑됩니다. "Gnomonic Projection"섹션 here에서 경도 선을 보면 위도/경도가 잘못되었는지 확인할 수 있습니다 (경도선이 직선으로 유지되는 것을 확인하십시오).

(지구를 구형으로 취급하는 것은 여전히 ​​적합하지 않지만 좋은 두 번째 근사입니다. 사실 실제 지구상의 가장 먼 거리 경로상의 점 (일반적으로 WGS84)은 놓여 있지 않습니다. . 중심을 통해 비행기는 그들이 어쩌면 척 당신이 구형으로 얻을 수있는 것보다 더 좋은 근사치를 제공)

Answer 4

FutureNerd :.

당신은 절대적으로 정확합니다. Maxy-B와 똑같은 문제를 응용 프로그램에서 해결해야했습니다. 첫 번째 반복으로서 (lng, lat)를 (x, y)로 처리하고 표준 2D 알고리즘을 실행했습니다. 모든 데이터가 연속적인 미국에 있었기 때문에 아무도 너무 가까이에서 보지 않는 한 괜찮 았습니다. 두 번째 반복으로, 나는 귀하의 접근 방식을 사용하고 개념을 입증했습니다.

포인트는 반드시 동일한 반구에 있어야합니다. 이 반구를 선택하는 것은 중요하지 않습니다. (처음에는 짐작했던 것처럼 포인트의 중심이 아닙니다.) 설명하기 위해 다음의 네 가지 점을 고려하십시오 : (0,0), (-60,0), (+60,0), 북극 (0,90)이있다. 그러나 "중심"을 정의하기로 선택하면 중심이 대칭으로 북극에 놓이고 네 점 모두 북반구에 있습니다. 그러나 네 번째 점을 (-19, 64) 아이슬란드 식으로 바꾸는 것이 좋습니다. 이제 그들의 중심은 북극에 있지 않지만, 아이슬란드쪽으로 비대칭 적으로 이끌려왔다. 그러나 네 가지 사항은 모두 북반구에 있습니다. 또한, 북반구는 북극에 의해 유일하게 정의 된 바와 같이 그들이 공유하는 유일한 반구입니다. 따라서이 "극"을 계산하는 것은 대수적이 아닌 알고리즘 적이됩니다. 좋은 생각을 자극하는 질문에 대한 https://github.com/VictorDavis/GeoConvexHull