Với các điểm 2D là ranh giới của một hình dạng bất thường, một hình dạng có thể không lồi và có thể có lỗ bên trong, có một thuật toán để tìm vòng tròn lớn nhất phù hợp với ranh giới không?Cách tìm vòng tròn lớn nhất nằm trong ranh giới được lấy mẫu?
Tôi đã thực hiện một chút tìm kiếm và tôi tìm thấy các thuật toán gần gũi, chẳng hạn như vấn đề vòng tròn trống lớn nhất, nhưng không có gì tôi tìm thấy cho đến nay khớp với các ràng buộc mà tôi có.
Sự cố không được xác định rõ vì tập hợp các điểm không ràng buộc bất kỳ khu vực nào. Ranh giới bạn đề cập nên là một số đường cong, có thể là đa giác. Nếu không có điều đó bạn không thể nói rằng có những lỗ hổng bên trong, và cũng không thể yêu cầu vòng tròn nằm trong ranh giới. Với định nghĩa này, bạn có thể tạo vòng tròn có kích thước bất kỳ trên "bên ngoài" chạm vào một vài điểm được đặt.
Nếu bạn sử dụng đa giác để chỉ định ranh giới, liên kết của Aioobe là tốt nhất. Nếu bạn xác định lại vấn đề để tìm vòng tròn bán kính tối đa chạm vào ít nhất 3 điểm của tập hợp đã cho, thì nó giống với việc kiểm tra cho circumcircles của Dalaunay triangulation.
Một thuật toán rất ngớ ngẩn :) (có khả năng một cái gì đó nhanh hơn là có thể)
Vòng tròn lớn nhất nên chạm ít nhất 3 đối tượng (object là một trong hai đỉnh hoặc dòng).
Vì vậy, bạn có thể đếm tất cả các kết hợp O (n^3), xây dựng một vòng tròn cho mỗi cái, kiểm tra xem nó nằm bên trong khu vực (O (n)) và chọn lớn nhất. Hoàn toàn - O (n^4).
Câu trả lời này có chính xác 0 nội dung thông tin. –
@JimMischel: Vô nghĩa. Quan sát rằng một vòng tròn lớn nhất luôn chạm 3 điểm làm giảm bộ giải pháp có khả năng cần phải được tìm kiếm thông qua để tìm tối ưu từ kích thước vô hạn đến đa thức. –
Động lực. Hình dạng được đưa ra bởi các điểm mà mẫu hình dạng đầu tiên nhắc tôi về khái niệm alpha shapes và mối quan hệ của chúng với cấu trúc liên kết liên tục. Xem các hình ảnh có liên quan này slides.
Nhưng dù sao, hình dạng alpha có mối quan hệ mật thiết với các điểm Voronoi diagram, là điểm kép (dưới dạng biểu đồ phẳng) đến Delaunay triangulation.
Giải pháp. gì tôi đề nghị là phải xem xét tất cả các nút Voronoi và lấy nút với bán kính giải phóng mặt bằng lớn nhất (khoảng cách đến các điểm Định nghĩa của nó) như là điểm bạn tìm kiếm:
Trong bối cảnh kép của triangulations Delaunay nút này tương ứng với tam giác Delaunay có đường tròn ngoại vi lớn nhất.
Giải pháp này cũng được thúc đẩy bởi vấn đề vòng tròn được ghi tối đa trong hình học tính toán.
Một cách khác để xem xét đó là giải thích về cỏ của sơ đồ Voronoi: Hãy xem xét cháy cỏ bắt đầu tại mỗi điểm đầu vào. Ngọn lửa phát triển theo từng hướng với tốc độ đơn vị. Điểm màu đỏ ở giữa là điểm mới nhất để đạt được trong thân lồi.
Phân tích & triển khai. Độ phức tạp về thời gian của thuật toán là O (n log n) cho sơ đồ Voronoi và O (n) để tìm nút Voronoi có độ thanh thải lớn nhất. Triển khai cổ điển là qhull. Có vẻ là một thực hiện C + + trong boost mà làm điều đó cho bạn. Nhưng bất kỳ mã tam giác Delaunay nào cũng sẽ ổn.
Các vấn đề có thể xảy ra. Nếu hình dạng tương tự như một lá thư Omega - có một túi lớn - thì nút Voronoi có độ hở lớn nhất là "bên ngoài" hình dạng Omega. Do đó, người ta sẽ cần nắm bắt tốt hơn khái niệm "bên trong" và "bên ngoài" của một hình dạng lấy mẫu. Ở đây một lần nữa hình dạng alpha được đề cập ban đầu có thể giúp, c.f. a survey bởi Edelsbrunner, người đã phát minh ra hình dạng alpha.
bản sao có thể có của [Vòng tròn tối đa bên trong đa giác không lồi] (http://stackoverflow.com/questions/4279478/maximum-circle-inside-a-non-convex-polygon) – aioobe
Bạn có muốn dễ triển khai nhất không hoặc bạn muốn có hiệu suất máy tính tốt nhất? Số điểm tối đa sẽ là bao nhiêu? –
Vấn đề đó trông giống như một thuật toán di truyền sẽ tạo ra một tốt, mặc dù có thể không phải là giải pháp tốt nhất, nhanh chóng. – rossum