Tôi đã đưa ra một số điểm (tọa độ 2D) và muốn tìm vòng tròn nhỏ nhất, bao gồm tất cả các điểm này. Các thuật toán không phải là rất hiệu quả (trong khi nó sẽ được tốt đẹp tự nhiên).Làm cách nào để tìm vòng tròn tối thiểu bao gồm một số điểm nhất định?
Liên kết rất thú vị nhưng kết quả được đề cập không có cập nhật. Thuật toán của Nimrod Megiddo từ năm 1983 là một giải pháp thời gian tuyến tính nhưng có nhiều thuật toán thực tế hơn, giống như của Welzl, xem [câu trả lời này] (http://stackoverflow.com/a/17329529/734191). – Hbf
Đây là cái gọi là nhỏ kèm theo Balls vấn đề (trong trường hợp của bạn, nhỏ bao quanh vòng), còn được gọi là Miniball. Có một số thuật toán và triển khai trên mạng cho vấn đề này - tất cả những điều sau đây là các giải pháp tuyến tính thời gian (ví dụ, cho n quả bóng, họ chạy trong O (n) nếu bạn xem xét các khía cạnh d cố định, d = 2 trong trường hợp của bạn):
Đối với 2D và 3D, Gärtner's implementation có lẽ là nhanh nhất.
Để có kích thước cao hơn (lên tới 10.000, nói), hãy xem https://github.com/hbf/miniball, đó là việc triển khai thuật toán của Gärtner, Kutz và Fischer (lưu ý: Tôi là một trong những đồng tác giả).
Đối với các kích thước rất, rất cao, lõi-bộ (xấp xỉ) thuật toán sẽ nhanh hơn.
Lưu ý: Nếu bạn đang tìm kiếm một thuật toán để tính toán kèm theo hình cầu nhỏ nhất của lĩnh vực, bạn sẽ tìm thấy một C++ thực hiện trong Computational Geometry Algorithms Library (CGAL). (Bạn không cần sử dụng tất cả CGAL; chỉ cần trích xuất các tệp nguồn và tiêu đề bắt buộc.)
Bản sao có thể có của [Vòng tròn nhỏ nhất bao phủ các điểm đã cho trên mặt phẳng 2D] (http://stackoverflow.com/questions/4901535/nhỏ nhất-vòng tròn-mà-bao-cho-điểm-trên-2d-máy bay); có một câu trả lời giống hệt nhau bởi cùng một người dùng và câu hỏi khác có từ ngữ tốt hơn, theo ý kiến của tôi. Câu trả lời chỉ có liên kết trong phiên bản này cũng không tuyệt vời ... – Benjamin