Cắt đường thẳng thành đa giác 2D

Question

Nếu tôi nhận được đoạn đường đủ dài để vượt qua một đa giác nhất định, có thể là đa giác lõm hoặc lồi. Làm cách nào tôi tìm thấy tất cả các phân đoạn ánh sáng giao nhau được chứa trong đa giác?

Nếu vùng mục tiêu không phải là đa giác, nhưng là một tiềm ẩn chức năng đường cong hoặc spline đường cong, làm thế nào để làm điều đó?

Cảm ơn!

Answer 1

Có thực sự không phải là một giải pháp đơn giản cho vấn đề của bạn, đặc biệt là với các đường cong (beziers và splines). Trên đầu trang của các phức tạp của cắt đa giác, có những thách thức đáng kể của việc xây dựng lại các đường cong cắt (giả sử bạn muốn kết quả clipping vẫn còn như beziers và splines và không chỉ 'phẳng' đường xấp xỉ).

Gần đây tôi đã phát hành bản cập nhật beta * cho thư viện đa giác cắt 'Clipper' của tôi mà không làm đường đa giác và cắt dòng (cũng có thể là đường cong). Tuy nhiên, trong khi thư viện chính được viết bằng Delphi, C++ & C#, mã beta mới cho đến nay chỉ trong Delphi mà có thể không giúp bạn. Tuy nhiên, nếu bạn nhìn vào mã bạn sẽ thấy lý do tại sao tôi nói không có giải pháp 'đơn giản'.

• Chỉnh sửa 15 tháng 7 năm 2011: Bản cập nhật này chưa bao giờ vượt quá bản beta này và bây giờ đơn giản là 'bằng chứng-khái niệm'. Nó bây giờ dựa trên một phiên bản cũ của thư viện Clipper của tôi và sẽ cần viết lại chính để duy trì và mở rộng được. (Tại một số giai đoạn I có thể xem lại nó, nhưng hiện tại tôi đang có ý định cải thiện hơn nữa các thư viện lõi.) Tuy nhiên, điều này mã 'proof-of-concept' Delphi có thể được tải here

Answer 2

• Bước một: tìm tất cả các giao lộ điểm, theo bất kỳ thứ tự nào. Đối với đa giác, bạn cần phải tìm giao điểm của đường màu đỏ và mỗi đường của mỗi đoạn. Chỉ cần giải quyết hệ thống của hai phương trình tuyến tính. Nếu giải pháp bị giới hạn trong giới hạn phân khúc đa giác, bạn có giao lộ.
• Bước hai: sắp xếp các điểm được tìm thấy theo vị trí trên đường màu đỏ. Bạn biết rằng điểm đầu tiên và cuối cùng là những điểm bên ngoài. "Outerness" flips với mỗi điểm - bên ngoài-bên trong-bên ngoài và như vậy. Giữa hai điểm bên ngoài liền kề bạn có phân khúc đường bên trong (màu xanh lục). Chỉnh sửa: không đúng ... Bắt đầu với điểm # 0, đoạn # 0 - # 1 là bên trong, tiếp theo là bên ngoài, tiếp theo là bên trong một lần nữa và cứ thế.

Nếu khu vực không phải là đa giác, nhưng được cung cấp bởi một số hàm ẩn, bạn cần tìm vị trí đó bằng đường đỏ (cách tiếp cận phụ thuộc vào hàm, tất nhiên).