Thân lồi (kinh độ, vĩ độ) trên bề mặt hình cầu

Question

Thuật toán thân lồi tiêu chuẩn sẽ không hoạt động với kinh độ (kinh độ, vĩ độ) vì thuật toán chuẩn cho rằng bạn muốn vỏ của một tập hợp các điểm Descartes. Các vĩ độ kinh độ là không phải là Descartes, bởi vì kinh độ "quấn quanh" ở mức chống kinh tuyến (+/- 180 độ). Tức là, hai độ về phía đông kinh độ 179 là -179.

Vì vậy, nếu tập hợp các điểm của bạn xảy ra để trải dài chống kinh tuyến, bạn sẽ tính toán vỏ giả mạo trải dài trên toàn thế giới không chính xác.

Bất kỳ đề xuất nào về thủ thuật tôi có thể áp dụng với thuật toán thân lồi tiêu chuẩn để sửa lỗi này hoặc các con trỏ tới thuật toán thân tàu "địa lý"?

Bây giờ tôi nghĩ về điều đó, có những trường hợp thú vị hơn để xem xét hơn là trải rộng chống lại người đàn ông. Hãy xem xét một "ban nhạc" của các điểm bao quanh trái đất - vỏ lồi của nó sẽ không có giới hạn đông/tây. Hoặc hơn nữa, vỏ lồi của {(0,0), (0, 90), (0, -90), (90, 0), (-90, 0), (180, 0)} là gì? - nó dường như chứa toàn bộ bề mặt của trái đất, vậy điểm nào nằm trên chu vi của nó?

Answer 1

thuật toán thân lồi Chuẩn không bị đánh bại bởi các gói - có các tọa độ trên bề mặt Trái đất nhưng do một vấn đề cơ bản hơn. Bề mặt của một hình cầu (chúng ta hãy quên không hoàn toàn của Trái đất) không phải là một không gian Euclide vì vậy hình học Euclide không hoạt động, và các hành trình thân lồi giả định rằng không gian cơ bản là Euclide (chỉ cho tôi cái không t, làm ơn) sẽ không hoạt động.

Bề mặt của hình cầu phù hợp với các khái niệm về số elliptic geometry trong đó các đường là các vòng tròn lớn và điểm đối xứng được coi là cùng một điểm. Bạn đã bắt đầu trải nghiệm các vấn đề phát sinh từ việc cố gắng áp dụng khái niệm Euclide về lồi vào không gian hình elip.

Một cách tiếp cận mở cho bạn sẽ là áp dụng các định nghĩa của geodesic convexity và thực hiện một thói quen thân lồi trắc địa. Điều đó trông khá lông. Và nó có thể không tạo ra kết quả phù hợp với mong đợi của bạn (thường là Euclide). Trong nhiều trường hợp, đối với 3 điểm tùy ý, vỏ lồi hóa ra là toàn bộ bề mặt của hình cầu.

Một cách tiếp cận khác, được sử dụng bởi các nhà điều hành và bản đồ thông qua các độ tuổi, sẽ là một phần của bề mặt hình cầu (một phần chứa tất cả các điểm của bạn) vào không gian Euclide (đó là chủ đề của bản đồ và tôi đã thắng) 't làm phiền bạn với tài liệu tham khảo để các tài liệu rộng rãi trong đó) và để tìm ra vỏ lồi của các điểm dự kiến. Chiếu khu vực bạn quan tâm lên trên mặt phẳng và điều chỉnh tọa độ sao cho chúng không quấn quanh; ví dụ: nếu bạn quan tâm đến Pháp, bạn có thể điều chỉnh tất cả các kinh độ bằng cách thêm 30deg để cả nước được điều phối bởi số + ve.

Khi tôi đang viết, ý tưởng được đề xuất trong câu trả lời của @ Li-aung Yip, sử dụng thuật toán lồi 3D lồi, tấn công tôi là sai lầm.Thân lồi 3D của tập hợp các điểm bề mặt sẽ bao gồm các điểm, cạnh và khuôn mặt nằm bên trong hình cầu. Những nghĩa đen này không tồn tại trên bề mặt 2D của hình cầu và chỉ thay đổi những khó khăn của bạn từ vật lộn với khái niệm không hoàn toàn đúng trong 2D thành sai hoàn toàn trong 3D. Hơn nữa, tôi đã học được từ bài viết Wikipedia tôi đã tham chiếu rằng một bán cầu kín (tức là một trong đó bao gồm 'xích đạo') không lồi trong hình học của bề mặt của hình cầu.

Answer 2

Thay vì xem xét dữ liệu của bạn dưới dạng dữ liệu kinh độ vĩ độ, thay vào đó bạn có thể xem xét dữ liệu đó trong không gian 3D và áp dụng 3D convex hull algorithm? Bạn có thể tìm thấy vỏ lồi 2D mà bạn mong muốn bằng cách phân tích vỏ lồi 3D.

Điều này trả về cho bạn các thuật toán được truyền đi tốt cho vỏ lồi (ví dụ trong ba chiều) và không có vấn đề gì với việc quấn quanh các tọa độ.

Cách khác, có giấy này: Computing the Convex Hull of a Simple Polygon on the Sphere (1996) mà dường như để đối phó với một số vấn đề tương tự mà bạn đang làm việc với (phối hợp bọc xung quanh, vv)

Answer 3

Nếu tất cả các điểm của bạn nằm trong bán cầu (nghĩa là, nếu bạn có thể tìm thấy một mặt phẳng cắt qua trung tâm của trái đất đặt tất cả ở một bên), thì bạn có thể thực hiện phép chiếu trung tâm aka gnomic trung tâm của Trái Đất đến một mặt phẳng song song với mặt phẳng cắt. Sau đó, tất cả các vòng tròn tuyệt vời sẽ trở thành các đường thẳng trong hình chiếu và do đó phần thân lồi trong bản chiếu sẽ ánh xạ trở lại một thân lồi chính xác trên Trái đất. Bạn có thể thấy các điểm vĩ độ/điểm sai như thế nào bằng cách xem các đường vĩ độ trong phần "Phép chiếu Gnomonic" here (lưu ý rằng các đường kinh tuyến vẫn thẳng).

(Xử lý trái đất dưới dạng hình cầu vẫn không hoàn toàn đúng, nhưng đó là phép tính xấp xỉ thứ hai tốt. Tôi không nghĩ điểm trên đường đi thật xa nhất trên Trái đất thực tế hơn (nói WGS84) nói chung nằm trên . một chiếc máy bay thông qua trung tâm có lẽ giả vờ họ làm mang đến cho bạn một xấp xỉ tốt hơn so với những gì bạn nhận được với một quả cầu)

Answer 4

FutureNerd:.

bạn đang hoàn toàn chính xác. Tôi đã phải giải quyết vấn đề chính xác giống như Maxy-B cho ứng dụng của tôi. Là một lần lặp đầu tiên, tôi chỉ xử lý (lng, lat) là (x, y) và chạy một thuật toán 2D chuẩn. Điều này làm việc tốt miễn là không ai nhìn quá gần, bởi vì tất cả dữ liệu của tôi ở Hoa Kỳ tiếp giáp Như một sự lặp lại thứ hai, mặc dù, tôi đã sử dụng cách tiếp cận của bạn và đã chứng minh khái niệm.

Các điểm PHẢI nằm trong cùng một bán cầu. Khi nó quay ra, chọn bán cầu này là không tầm thường (nó không chỉ là trung tâm của điểm, như tôi đã đoán ban đầu.) Để minh họa, hãy xem xét bốn điểm sau đây: (0,0), (-60,0), (+60,0) dọc đường xích đạo và (0,90) cực bắc. Tuy nhiên bạn chọn để xác định "trung tâm", trung tâm của họ nằm trên cực bắc bởi tính đối xứng và tất cả bốn điểm ở Bắc bán cầu. Tuy nhiên, hãy cân nhắc thay thế điểm thứ tư bằng, nói (-19, 64) iceland. Bây giờ trung tâm của họ KHÔNG ở cực bắc, nhưng không đối xứng được vẽ về phía iceland. Tuy nhiên, tất cả bốn điểm vẫn còn ở Bắc bán cầu. Hơn nữa, Bắc bán cầu, như được xác định duy nhất bởi Bắc Cực, là bán cầu chỉ họ chia sẻ. Vì vậy, tính toán "cực" này trở thành thuật toán, chứ không phải đại số.

Xem kho của tôi cho mã Python: https://github.com/VictorDavis/GeoConvexHull