Tìm đường phân cách giữa hai đa giác

Question

Có một thuật toán đơn giản nào tìm thấy một đường tách giữa hai đa giác sao cho chúng nằm ở hai bên của đường kẻ không? Hoặc tốt hơn là không ai biết một thư viện làm điều này? Bất kỳ trợ giúp sẽ được đánh giá

EDIT:

Giải pháp của tôi:

tôi đã sử dụng JTS: http://www.vividsolutions.com/jts/JTSHome.htm

Created hai đa giác sử dụng thư viện này và chạy DistanceOp để tìm ra hai điểm gần giữa các đa giác (không nhất thiết phải đỉnh). Sau đó, chỉ cần tính toán một đường vuông góc với đường kết nối chúng.

Answer 1

Hãy để A và B là hai đa giác của bạn. Trước tiên, hãy tìm số convex hull của mỗi, C (A) và C (B). Rõ ràng một đường phân tách A từ B cũng tách C (A) từ C (B). Hãy để a là một điểm trên C (A) và b một điểm trên C (B). Người ta có thể đi bộ một và b xung quanh ranh giới cho đến khi một đường phân cách qua một và b được tìm thấy. Điều này có thể là hoàn thành trong thời gian tuyến tính, nhưng tôi sẽ không mô tả điều đó ngay bây giờ.

Answer 2

Giả sử bạn có đa giác A có điểm A1, B2, A3, ..., AN và đa giác B có điểm B1, B2, B3, ..., BN.

gì bạn có thể làm là để mô tả một dòng từ AX điểm đến BX cho mỗi sự kết hợp có thể (A1 & B1, A1 & B2, ... AN & BN).

Dòng như vậy có thể được mô tả theo định dạng tham số: SomePoint = InicialPoint + Hướng * t và sẽ có thể là ứng cử viên cho một "dòng tách biệt". Giữ nó!

Bây giờ, những gì bạn cần làm là MÔ TẢ MỘT vector KHÁC từ mỗi điểm của mỗi đa giác đến dòng ứng cử viên này. Mỗi dòng đó sẽ có vector hướng của nó.

Nếu sản phẩm chéo của vectơ hướng của mỗi dòng với vectơ hướng của ứng cử viên có cùng hướng (Z-positive hoặc Z-negative), có nghĩa là các điểm đó nằm ở cùng một bên của đường tách (vẫn là ứng viên).

Bây giờ, hãy kiểm tra tất cả các dòng bạn đã mô tả cho từng điểm của mỗi đa giác. Bạn có thể tìm ra nếu tất cả các điểm của đa giác A là ở một bên và tất cả các điểm trong đa giác B là ở phía bên kia ... sau đó bạn tìm thấy dòng bạn muốn. Nếu không, bạn phải thử một dòng ứng viên tiếp theo (AX-BX). Nếu bạn không tìm thấy bất kỳ sự kết hợp nào với tất cả các dòng ứng cử viên có thể, điều đó có nghĩa là bạn có một giao điểm giữa các đa giác.

Tôi không chắc đó là thuật toán tốt nhất/nhanh nhất nhưng tôi chắc chắn nó hoạt động.