Outline âm mưu thuật toán

Question

tôi đã được trao nhiệm vụ này bởi vợ tôi, vì vậy nó là ưu tiên hàng đầu :-)

Tôi có một bộ sưu tập các điểm (trên thực tế Northings & Eastings, nhưng nó không thực sự quan trọng). Tôi muốn lấy những điểm đó và tạo một tập hợp các vectơ đại diện cho đường viền, vì vậy tôi có thể vẽ trên Google Earth.

Vì vậy, một cái gì đó như:

#      # 
      #    #  # 
#    # # 
     # # 

      # 

sẽ cung cấp cho:

#-----------------------#-- 
/       \ --# 
#     #------------/ 
\-----#  /
     \ /
      # 

Một giải pháp có thể, tôi đã đưa ra, là để tính toán vectơ giữa mỗi điểm, và loại bỏ tất cả các vector được chồng chéo bởi một véc tơ khác. Tôi chưa thực hiện điều này (không thực sự chắc chắn như thế nào), nhưng tôi tự hỏi nếu có những cách khác.

Thuật toán chỉ phải chạy một vài lần, vì vậy nếu mất một giờ cho mỗi lần chạy và biểu diễn RAM thì đó không phải là vấn đề.

Answer 1

Xây dựng đa giác ứng cử viên

Nó có vẻ như những gì bạn đang tìm kiếm một đa giác mà

• tất cả các đỉnh của nó là trong quan điểm của bạn thiết lập
• nó chứa tất cả các điểm trong quan điểm của bạn thiết lập

Điều này xác định tập hợp đa giác khả thi của đa giác ứng cử viên đối với tập hợp điểm của bạn.

Convex Hull?

Một hàm mục tiêu có thể là "Trong số các đa giác này, hãy chọn một hàm có số đỉnh tối thiểu." Đó sẽ là thân tàu lồi của bộ điểm của bạn. Các câu trả lời khác giải quyết cách tiếp cận đó, vì vậy tôi sẽ không nói gì thêm về nó.

Một cái gì đó khác ...

Nhưng đó không phải là chức năng khách quan duy nhất bạn có thể chọn. Ví dụ: thay vào đó, bạn có thể có sự cân bằng giữa việc có ít đỉnh hơn, có tổng diện tích ít hơn và có góc ít sắc nét hơn ở các đỉnh. Tôi không biết bất kỳ thuật toán được đặt tên hiện có nào cho vấn đề đó, nhưng nó chắc chắn là một thuật toán thú vị.

Một cách tiếp cận có thể là bắt đầu bằng cách tìm thân lồi, sau đó "kéo" cạnh các đỉnh bên trong tại các vị trí mà chi phí của đỉnh phụ lớn hơn vì lợi ích của việc có tổng diện tích ít hơn.

Ví dụ này:

sẽ trở thành này, bằng cách kéo trong cạnh dọc theo phía trên:

đa giác thứ hai này có thể là một "tự nhiên" phù hợp cho tập hợp điểm, mặc dù nó là không phải thân lồi của tập hợp điểm.

Answer 2

Có thể bạn đang tìm kiếm Convex Hull của các điểm; có một số variety of algorithms để tìm kiếm điều đó.

Answer 3

Here là một thư viện cho việc tìm kiếm thân lồi từ code.google.com

Here là một thư viện github cho điều tương tự, nhưng sử dụng Jarvis của trận đấu Convex Hull Algorithm.

Hy vọng họ sẽ giúp bạn!