Có một thuật toán hiệu quả để tạo ra một thân lõm 2D?

Question

Có một tập các điểm (2D) từ tệp GIS (bản đồ thành phố), tôi cần tạo đa giác xác định 'đường viền' cho bản đồ đó (ranh giới của nó). Các tham số đầu vào của nó sẽ là các điểm được thiết lập và một 'độ dài cạnh tối đa'. Sau đó nó sẽ xuất ra đa giác tương ứng (có thể không lồi).

Giải pháp tốt nhất mà tôi tìm thấy cho đến nay là tạo các tam giác Delaunay và sau đó loại bỏ các cạnh bên ngoài dài hơn độ dài cạnh tối đa. Sau khi tất cả các cạnh bên ngoài ngắn hơn, tôi chỉ cần loại bỏ các cạnh bên trong và lấy đa giác mà tôi muốn. Vấn đề là, điều này là rất tốn thời gian và tôi tự hỏi nếu có một cách tốt hơn.

Answer 1

This giấy thảo luận về thế hệ hiệu quả của các đa giác đơn giản để mô tả hình dạng của một tập hợp các điểm trong mặt phẳng và cung cấp thuật toán. Ngoài ra còn có một applet Java sử dụng cùng một thuật toán here.

Answer 2

Một trong những cựu sinh viên trong phòng thí nghiệm của chúng tôi đã sử dụng một số kỹ thuật áp dụng cho luận án tiến sĩ của mình. Tôi tin rằng một trong số họ được gọi là "hình dạng alpha" và được tham chiếu trong các giấy tờ sau đây:

http://www.cis.rit.edu/people/faculty/kerekes/pdfs/AIPR_2007_Gurram.pdf

giấy đó đưa ra một số tài liệu tham khảo thêm bạn có thể làm theo.

Answer 3

Một giải pháp gần đúng nhanh (cũng hữu ích cho vỏ lồi) là tìm ranh giới phía bắc và phía nam cho từng phần tử nhỏ phía đông tây.

Dựa trên số lượng chi tiết bạn muốn, tạo một dải kích thước cố định trên/dưới. Đối với mỗi điểm tính toán cột E-W, và sau đó cập nhật giới hạn trên/dưới cho cột đó. Sau khi bạn xử lý tất cả các điểm, bạn có thể nội suy các điểm trên/dưới cho các cột bị bỏ qua.

Bạn cũng nên kiểm tra nhanh trước các hình dạng rất dài và quyết định chia sẻ với bin NS hoặc Ew.

Answer 4

Câu hỏi hay! Tôi đã không cố gắng này ra ở tất cả, nhưng pha đầu tiên của tôi sẽ là phương pháp lặp đi lặp lại này:

1. Tạo một tập N ("không chứa"), và thêm tất cả các điểm trong thiết lập của bạn để N.
2. Chọn 3 điểm từ N ngẫu nhiên để tạo thành một đa giác ban đầu P. Loại bỏ chúng khỏi N.
3. Sử dụng some point-in-polygon algorithm và xem các điểm bằng N. Đối với mỗi điểm trong N, nếu nó bây giờ được chứa bởi P, loại bỏ nó khỏi N. Ngay sau khi bạn tìm thấy một điểm trong N mà vẫn không được chứa trong P, tiếp tục bước 4. Nếu N trở nên trống rỗng, bạn đã hoàn tất.
4. Gọi điểm mà bạn đã tìm thấy A. Tìm dòng trong P gần nhất với A và thêm A ở giữa nó.
5. Quay trở lại bước 3

Tôi nghĩ rằng nó sẽ làm việc miễn là nó hoạt động tốt đủ - một heuristic tốt cho ban đầu 3 điểm của bạn có thể giúp đỡ.

Chúc may mắn!

Answer 5

Những kẻ here tuyên bố đã phát triển phương pháp tiếp cận láng giềng gần nhất để xác định thân lõm của một tập hợp các điểm hoạt động "gần như tuyến tính về số điểm". Đáng buồn thay giấy của họ dường như được bảo vệ rất tốt và bạn sẽ phải yêu cầu them cho nó.

Dưới đây là một số good set of references bao gồm các yếu tố trên và có thể dẫn bạn đến một phương pháp tốt hơn.

Answer 6

Một giải pháp đơn giản là đi bộ xung quanh cạnh của đa giác.Với một lợi thế cạnh hiện tại OM ranh giới kết nối điểm P0 và P1, điểm tiếp theo trên ranh giới P2 sẽ là điểm với A nhỏ nhất có thể, nơi

H01 = bearing from P0 to P1 
H12 = bearing from P1 to P2 
A = fmod(H12-H01+360, 360) 
|P2-P1| <= MaxEdgeLength 

Sau đó, bạn thiết lập

P0 <- P1 
P1 <- P2 

và lặp lại cho đến khi bạn quay lại nơi bạn bắt đầu.

Đây vẫn là O (N^2) vì vậy bạn sẽ muốn sắp xếp danh sách điểm của mình một chút. Bạn có thể giới hạn tập hợp các điểm bạn cần xem xét ở mỗi lần lặp nếu bạn sắp xếp các điểm trên, nói rằng, điểm của chúng từ trọng tâm của thành phố.

Answer 7

Câu trả lời vẫn có thể là thú vị cho người khác: Người ta có thể áp dụng một biến thể của thuật toán vuông diễu hành, áp dụng (1) trong thân tàu lõm, và (2) sau đó vào (ví dụ 3) quy mô khác nhau rằng tôi phụ thuộc vào mật độ điểm trung bình. Thang đo cần phải là bội số của nhau, chẳng hạn bạn xây dựng một lưới mà bạn có thể sử dụng để lấy mẫu hiệu quả. Điều này cho phép nhanh chóng tìm các mẫu rỗng = các ô vuông, các mẫu hoàn toàn nằm trong một "cụm/đám mây" của các điểm và các mẫu nằm ở giữa. Loại thứ hai sau đó có thể được sử dụng để xác định dễ dàng poly-line đại diện cho một phần của thân lõm.

Tất cả mọi thứ là tuyến tính trong phương pháp này, không có tam giác là cần thiết, nó không sử dụng hình dạng alpha và nó là khác nhau từ thương mại/cấp bằng sáng chế cung cấp như mô tả ở đây (http://www.concavehull.com/)

Answer 8

Bạn có thể thực hiện điều đó trong QGIS bằng plugin này; https://github.com/detlevn/QGIS-ConcaveHull-Plugin

Tùy thuộc vào cách bạn cần nó tương tác với dữ liệu của bạn, có lẽ đáng để xem cách thực hiện tại đây.

Answer 9

Là một tham chiếu được chấp nhận một cách dữ dội, PostGIS bắt đầu bằng một lồi và sau đó lồng vào, bạn có thể thấy nó ở đây.

https://github.com/postgis/postgis/blob/380583da73227ca1a52da0e0b3413b92ae69af9d/postgis/postgis.sql.in#L5819

Answer 10

Các Bing Maps V8 tương tác SDK có một lựa chọn thân lõm trong các hoạt động hình tiên tiến.

https://www.bing.com/mapspreview/sdkrelease/mapcontrol/isdk/advancedshapeoperations?toWww=1&redig=D53FACBB1A00423195C53D841EA0D14E#JS

Trong ArcGIS 10.5.1, phần mở rộng phân tích 3D có một công cụ tích tối thiểu Bounding với các loại hình học của thân tàu lõm, hình cầu, phong bì, hoặc thân lồi. Nó có thể được sử dụng ở bất kỳ cấp độ giấy phép nào.

Có một thuật toán thân lõm ở đây: https://github.com/mapbox/concaveman