Tìm một ray mà cắt một đa giác nhiều lần càng tốt

Question

Dưới đây là một bài tập thú vị:

Hãy P là một đơn giản, nhưng không nhất thiết phải lồi, đa giác và q một điểm tùy ý không nhất thiết phải ở P.

Thiết kế một thuật toán hiệu quả để tìm phân đoạn đường có nguồn gốc từ q giao cắt số cạnh tối đa của P.

Nói cách khác, nếu đứng tại điểm q, bạn nên nhắm súng theo hướng nào? sẽ đi qua số bức tường lớn nhất?

Một viên đạn qua đỉnh của P chỉ được ghi có cho một bức tường.

Thuật toán O (n log n) là có thể. n là số đỉnh hoặc cạnh, vì nó là một đa giác, số cạnh gần bằng với số đỉnh.

Đây là suy nghĩ của tôi:

Connect q với tất cả các đỉnh (giả sử có N đỉnh) tại P đầu tiên. Sẽ có N dòng, hoặc cặp N-1.

Đường quay cuối cùng phải nằm giữa các cặp này. Vì vậy, chúng ta phải tìm cặp có chứa số lượng cạnh lớn nhất.

Tôi không nghĩ giải pháp này là O (n log n).

Bất kỳ ý tưởng nào?

Answer 1

Vâng, đầu tiên chuyển đổi các điểm tọa độ thành một hệ thống cực tập trung tại P.

• Không mất tính tổng quát, chúng ta hãy chọn chiều kim đồng hồ là đặc biệt đối với các góc phối hợp với.
• Bây giờ chúng ta hãy thực hiện một bước đi theo thứ tự dọc theo tất cả các cạnh của đa giác, và chúng ta hãy chú ý đến điểm bắt đầu và điểm kết thúc của các cạnh đó, nơi đi bộ sẽ đưa chúng ta theo chiều kim đồng hồ theo P.
• Hãy gọi điểm kết thúc của cạnh đó là 'mông' và điểm bắt đầu là 'đầu'. Tất cả điều này nên được thực hiện trong O (n). Bây giờ chúng tôi sẽ phải sắp xếp những cái đầu và butts, vì vậy với quicksort nó có thể là O(nlog(n)). Chúng tôi sắp xếp chúng theo góc của chúng (φ) từ nhỏ nhất, đảm bảo rằng trong trường hợp tọa độ bằng nhau, đầu được coi là nhỏ hơn (điều quan trọng là tuân thủ quy tắc cuối cùng của vấn đề).
• Sau khi hoàn thành, chúng tôi sẽ bắt đầu đi từ the nhỏ nhất, tăng tổng số khi chúng ta gặp phải mông và giảm dần bất cứ khi nào chúng ta gặp đầu, nhận thấy cực đại toàn cầu. . Điều này cũng nên được thực hiện trong O (n), do đó độ phức tạp tổng thể là O(nlog(n)).

Bây giờ bạn sẽ cho tôi biết tại sao bạn lại hỏi loại câu hỏi này?

Answer 2

Tôi đã sử dụng thuật toán của Boris Stitnicky và đã viết giải pháp của tôi trong Java. Nhưng tôi đã chọn hướng ngược chiều kim đồng hồ, và để kiểm tra điểm nào của một khoảng thời gian là điểm bắt đầu và điểm nào là kết thúc của một khoảng thời gian tôi đã sử dụng sản phẩm chéo. Bạn có thể tìm thấy ở đây: https://github.com/Katkov/algorithms/blob/master/BulletAgainstWalls.java