it-swarm-vi.tech

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

Có một tập hợ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 đặt và 'độ 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 tôi tìm thấy cho đến nay là tạo ra các tam giác Delaunay và sau đó loại bỏ các cạnh bên ngoài dài hơn chiều dài Edge tối đa. Sau khi tất cả các cạnh bên ngoài ngắn hơn thế, tôi chỉ cần loại bỏ các cạnh bên trong và lấy đa giác tôi muốn. Vấn đề là, điều này rất tốn thời gian và tôi tự hỏi liệu có cách nào tốt hơn không.

59
Fabio Ceconello

This paper thảo luận về Tạo đa giác đơn giản hiệu quả để 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 Java applet sử dụng cùng một thuật toán ở đây .

2
Amirali

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ố chúng được gọi là "hình dạng alpha" và được tham chiếu trong bài báo sau:

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

Bài viết đó cung cấp cho một số tài liệu tham khảo thêm bạn có thể làm theo.

10
nsanders

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

Mọi thứ đều tuyến tính theo cách tiếp cận này, không cần tam giác hóa, nó không sử dụng hình dạng alpha và nó khác với cung cấp thương mại/bằng sáng chế như được mô tả ở đây ( http://www.concavehull.com/ )

2
monnoo

Những kẻ ở đây tuyên bố đã phát triển một cách tiếp cận k lân cận gần nhất để xác định vỏ lõm của một tập hợp các điểm hoạt động "gần như tuyến tính trên 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 hỏi họ cho nó.

Đây là một bộ tài liệu tham khảo tốt bao gồm những điều trên và có thể dẫn bạn tìm một cách tiếp cận tốt hơn.

2
Vinko Vrsalovic

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 Edge hiện tại om ranh giới nối các điểm P0 và P1, điểm tiếp theo trên ranh giới P2 sẽ là điểm có A nhỏ nhất có thể, trong đó

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

Sau đó, bạn đặt

P0 <- P1
P1 <- P2

và lặp lại cho đến khi bạn quay trở 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, giả sử, điểm mang của chúng từ tâm của thành phố.

1
Mike F

Bạn có thể làm điều đó trong QGIS với 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 để kiểm tra xem nó đã được thực hiện ở đây như thế nào.

1
Cameron

Câu hỏi hay! Tôi chưa từng thử điều này, nhưng phát súng đầu tiên của tôi sẽ là phương pháp lặp lại này:

  1. Tạo một bộ N ("không chứa") và thêm tất cả các điểm trong bộ của bạn vào N.
  2. Chọn ngẫu nhiên 3 điểm từ N để tạo thành đa giác ban đầu P. Xóa chúng khỏi N.
  3. Sử dụng một số thuật toán đa giác điểm và xem xét các điểm trong N. Với mỗi điểm trong N, nếu bây giờ nó được chứa bởi P, hãy xóa nó khỏi N. Ngay khi bạn tìm thấy một điểm trong N không có trong P, tiếp tục bước 4. Nếu N trở nên trống rỗng, bạn đã hoàn thành.
  4. Gọi điểm bạn đã tìm thấy A. Tìm đường thẳng trong P gần nhất với A và thêm A vào giữa nó.
  5. Quay trở lại bước 3

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

Chúc may mắn!

1
Rob Dickerson

Là một tài liệu tham khảo được chấp nhận rộng rãi, PostGIS bắt đầu với một lồi và sau đó lồng nó vào, bạn có thể thấy nó ở đây.

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

0
Evan Carroll

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

Dựa trên mức độ chi tiết bạn muốn, tạo một mảng có kích thước cố định của giới hạn trên/dưới . Với mỗi điểm tính toán cột E-W nào trong đó 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ỏ lỡ.

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

0
Martin Beckett