Khoảng cách giữa hai polylines

Question

tôi muốn để tính toán khoảng cách d giữa hai polylines:

Rõ ràng là tôi có thể kiểm tra khoảng cách cho tất cả các cặp dòng phân đoạn và lựa chọn khoảng cách nhỏ nhất, nhưng điều này cách thuật toán sẽ có thời gian chạy là O (n). Có cách tiếp cận nào tốt hơn không?

Answer 1

Divide and Conquer:

• Định nghĩa một cấu trúc dữ liệu đại diện cho một cặp polylines và khoảng cách minimun giữa axis-aligned minimum bounding boxes (AAMBB) của họ: pair = (poly_a, poly_b, d_ab))

• Tạo một hàng đợi rỗng cho pair estructures dữ liệu, sử dụng khoảng cách d_ab làm khóa.

• Tạo một cấu trúc dữ liệu pair với các ô vuông ban đầu và đẩy nó vào hàng đợi.

• Chúng tôi sẽ giữ một biến với khoảng cách tối thiểu giữa các ô được tìm thấy cho đến nay (min_d). Đặt nó thành vô hạn.

• Lặp lại:

  • Pop từ hàng đợi các phần tử với khoảng cách tối thiểu d_ab.

  • Nếu d_ab lớn hơn min_d chúng tôi đã hoàn tất.

  • Nếu bất kỳ của polylines poly_a hoặc poly_b chứa một phân khúc chỉ:

    • Sử dụng brute force để tìm khoảng cách tối thiểu giữa sau đó và cập nhật min_d cho phù hợp.

  • Nếu không:

    • Divide cả polylines poly_a và poly_b một nửa, ví dụ:

      (1-7) --> { (1-4), (4-7) }

      (8-12) --> { (8-10), (10-12) }

    • Làm cho sản phẩm chéo của cả hai gia nhập ts, tạo 4 mới pair cấu trúc dữ liệu và đẩy sau đó vào hàng đợi Q.

Trên trường hợp trung bình, độ phức tạp là O (N * log N), trường hợp xấu nhất có thể O (N²).

Cập nhật: algorithm được triển khai trong Perl.

Answer 2

Cách "chuẩn" cho các vấn đề như vậy là xây dựng sơ đồ Voronoi của các thực thể hình học. Điều này có thể được thực hiện trong thời gian O (N Log N).

Nhưng việc xây dựng sơ đồ như vậy cho các đoạn đường là khó khăn và bạn nên sử dụng các giải pháp đã sẵn sàng như trong CGAL.