tam giác lớn nhất từ ​​một tập hợp các điểm

Question

thể trùng lặp:
How to find largest triangle in convex hull aside from brute force search

Tôi có một tập hợp các điểm ngẫu nhiên mà từ đó tôi muốn tìm tam giác có diện tích lớn người là verticies là mỗi trên một trong những điểm đó.

Cho đến nay tôi đã tìm ra rằng các hình tam giác lớn nhất sẽ chỉ nằm trên các điểm bên ngoài của đám mây điểm (hoặc lồi) vì vậy tôi đã lập trình một chức năng để thực hiện điều đó (sử dụng Graham scan trong thời gian nlogn).

Tuy nhiên đó là nơi tôi bị kẹt. Cách duy nhất tôi có thể tìm ra cách để tìm tam giác lớn nhất từ ​​những điểm này là sử dụng sức mạnh vũ phu ở thời điểm n^3 mà vẫn được chấp nhận trong một trường hợp trung bình vì thuật toán thân lồi thường đá ra phần lớn các điểm. Tuy nhiên, trong trường hợp xấu nhất trong đó các điểm nằm trên một vòng tròn, phương pháp này sẽ thất bại thảm hại.

Có ai biết thuật toán để thực hiện việc này hiệu quả hơn không?

Lưu ý: Tôi biết rằng CGAL có thuật toán này ở đó nhưng chúng không đi vào bất kỳ chi tiết nào về cách thực hiện. Tôi không muốn sử dụng thư viện, tôi muốn tìm hiểu và tự mình lập trình (và cũng cho phép tôi tinh chỉnh nó theo đúng cách tôi muốn nó hoạt động, giống như quét graham, trong đó các triển khai khác nhận điểm collinear tôi không muốn).

Answer 1

Tắt đầu của tôi, có lẽ bạn có thể làm điều gì đó liên quan đến việc sắp xếp/tách bộ sưu tập các điểm thành các nhóm? Có lẽ ... tách các điểm thành ba nhóm (không chắc chắn cách tốt nhất để làm điều đó trong trường hợp này là gì), làm một cái gì đó để loại bỏ những điểm trong mỗi nhóm gần với hai nhóm kia hơn các điểm khác trong cùng một nhóm, và sau đó sử dụng các điểm còn lại để tìm tam giác lớn nhất có thể được tạo ra có một đỉnh trong mỗi nhóm? Điều này thực sự sẽ làm cho trường hợp của tất cả các điểm trên một vòng tròn đơn giản hơn rất nhiều, bởi vì bạn chỉ tập trung vào các điểm gần trung tâm của các vòng cung trong mỗi nhóm, vì chúng sẽ là những điểm trong mỗi nhóm xa nhất từ hai nhóm còn lại.

Tôi không chắc chắn nếu điều này sẽ cung cấp cho bạn kết quả phù hợp cho một số hình tam giác/phân phối các điểm, mặc dù. Có thể có các tình huống mà tam giác kết quả không phải là vùng tối ưu, vì việc nhóm và/hoặc đỉnh chọn không phải là/không phải là tối ưu. Một cái gì đó như thế.

Dù sao, đó là suy nghĩ của tôi về vấn đề này. Tôi hy vọng tôi ít nhất có thể đưa ra cho bạn những ý tưởng về cách làm việc trên nó.

Answer 2

Đây là suy nghĩ về cách đặt xuống O (n nhật ký n). Tôi thực sự không biết gì về hình học tính toán, vì vậy tôi sẽ đánh dấu nó là wiki cộng đồng; xin vui lòng cải thiện về điều này.

Tiền xử lý vỏ lồi bằng cách tìm cho mỗi điểm phạm vi của các đường của đường thẳng qua điểm đó sao cho tập hợp nằm hoàn toàn ở một bên của đường kẻ. Sau đó đảo ngược mối quan hệ này: xây dựng một cây khoảng thời gian cho các sườn có các điểm trong các nút lá, như vậy khi truy vấn với độ dốc bạn tìm thấy các điểm sao cho có một đường tiếp tuyến qua các điểm đó.

Nếu không có ba hoặc nhiều điểm cộng trên thân lồi, có tối đa bốn điểm cho mỗi độ dốc (hai ở mỗi bên), nhưng trong trường hợp các điểm trùng nhau chúng ta có thể bỏ qua các điểm trung gian.

Bây giờ, lặp qua tất cả các cặp điểm (P, Q) trên thân lồi. Chúng tôi muốn tìm điểm R sao cho tam giác PQR có diện tích tối đa. Lấy PQ làm cơ sở của tam giác, chúng ta muốn tối đa hóa chiều cao bằng cách tìm R càng xa đường PQ càng tốt. Đường thẳng qua R song song với PQ phải sao cho tất cả các điểm nằm ở một bên của đường kẻ, vì vậy chúng ta có thể tìm thấy số lượng ứng cử viên bị giới hạn trong thời gian O (log n) bằng cách sử dụng cây khoảng cách được xây dựng trước.

Để cải thiện điều này trong thực tế, hãy thực hiện nhánh và giới hạn trong tập hợp các cặp điểm: tìm một giới hạn trên cho chiều cao của bất kỳ tam giác nào (ví dụ khoảng cách tối đa giữa hai điểm) và loại bỏ bất kỳ cặp nào điểm có khoảng cách nhân với giới hạn trên này nhỏ hơn tam giác lớn nhất được tìm thấy từ trước đến nay.

Answer 3

Tôi nghĩ phương pháp rotating calipers có thể áp dụng tại đây.

Answer 4

Làm thế nào về việc thả một điểm tại một thời điểm từ vỏ lồi? Bắt đầu với vỏ lồi, tính diện tích tam giác được hình thành bởi mỗi ba điểm liền kề (p1p2p3, p2p3p4, v.v.). Tìm hình tam giác với diện tích tối thiểu, sau đó thả phần giữa của ba điểm hình thành tam giác đó. (Nói cách khác, nếu tam giác nhỏ nhất là p3p4p5, hãy thả P4.) Bây giờ bạn có một đa giác lồi với các điểm N-1. Lặp lại các thủ tục tương tự cho đến khi bạn còn lại với ba điểm. Điều này sẽ mất thời gian O (N^2).

Tôi sẽ không ngạc nhiên nếu có một số trường hợp bệnh lý mà điều này không hoạt động, nhưng tôi hy vọng rằng nó sẽ làm việc cho phần lớn các trường hợp. (Nói cách khác, tôi đã không chứng minh điều này, và tôi không có nguồn để trích dẫn.)

Answer 5

Không biết nếu điều này giúp, nhưng nếu bạn chọn hai điểm từ thân lồi và xoay tất cả các điểm của thân tàu sao cho đường kết nối của hai điểm song song với trục x, hoặc điểm có cực đại hoặc điểm có toạ độ y tối thiểu tạo thành tam giác với diện tích lớn nhất cùng với hai điểm được chọn đầu tiên.

Tất nhiên khi bạn đã kiểm tra một điểm cho tất cả các dòng cơ sở có thể, bạn có thể xóa nó khỏi danh sách.