Bao gồm một khu vực tùy ý với các vòng tròn có bán kính bằng nhau

Question

Thuật toán hoạt động bao phủ một vùng tùy ý với các vòng tròn bán kính bằng nhau như thế nào?

Bán kính của hình tròn và kích thước và hình dạng của khu vực tùy ý được cung cấp. Khu vực phải được bao phủ với ít vòng tròn nhất có thể. Các vòng tròn có thể trùng lặp.

Có thuật toán nào xử lý việc này không?

Answer 1

Nếu không biết thêm về các ràng buộc của bạn, tôi khuyên bạn nên sử dụng lớp phủ thường xuyên của mặt phẳng, với các đĩa tương ứng với hình lục giác thông thường của ốp lát lục giác. Sau đó giữ tất cả các đĩa giao nhau với hình dạng.

Answer 2

Hope tôi đã hiểu câu hỏi của bạn đúng ...

Nó có thể được chứng minh rằng sáu phương Đóng gói (HCP) của lĩnh vực bao gồm khối lượng tối đa, sử dụng các lĩnh vực. Do đó, tôi giả định rằng việc thực hiện HCP với các vòng kết nối cũng sẽ bao gồm diện tích tối đa bằng các vòng kết nối. Khẳng định khu vực của bạn với hình tam giác và đặt một vòng tròn với tâm ở mỗi đỉnh của tam giác, với bán kính một nửa chiều dài cạnh của tam giác. Xem this để biết hình ảnh của thuật toán tôi đang nói đến.

Lưu ý: Điều này tương tự như close packing of atoms in a unit cell.

EDIT: Phương pháp trước đây của tôi bao gồm nhiều khu vực nhất có thể, không bị trùng lặp. Nếu chồng chéo được cho phép, sau đó (tôi tin rằng) phương pháp sau đây sẽ bao gồm toàn bộ khu vực với chồng chéo tối thiểu.

Như bạn có thể biết, chỉ có 3 dấu chấm của không gian 2D với đa giác thông thường - sử dụng hình vuông, hình tam giác hoặc hình lục giác. Chiến lược là để chấm dứt bằng cách sử dụng một trong các đa giác này và sau đó hủy đăng ký vòng kết nối cho mọi đa giác. Một hình lục giác sẽ lãng phí khu vực tối thiểu bằng cách sử dụng phương pháp này.

Do đó, từ bán kính của vòng tròn đã cho, tính toán kích thước của hình lục giác cần thiết, chấm dứt khu vực bằng hình lục giác và sau đó bỏ vòng tròn vào mỗi hình lục giác.

NB:Eric Bainville đề xuất phương pháp tương tự.

-- Flaviu Cipcigan

Answer 3

Tôi biết câu hỏi đó có thể là một chút lỗi thời nhưng gần đây tôi có một vấn đề tương tự với bao gồm khu vực địa lý với vòng tròn bằng cách sử dụng lưới lục giác và đây là cách tôi giải quyết nó:

1. của tôi dữ liệu đầu vào là bán kính của vòng tròn được cho theo mét và tọa độ biên giới của khu vực
2. trước tiên tôi tìm thấy hình chữ nhật có viền bao quanh khu vực đã cho
3. sau đó bắt đầu từ dưới cùng bên trái theo khoảng cách bằng cách tăng gấp đôi chiều cao của tam giác được sử dụng để xây dựng hình lục giác (cạnh của nó giống với bán kính của vòng tròn của tôi) và mang 0 độ sử dụng công thức của Vincenty
4. cho mỗi điểm tôi tìm thấy, tôi kiểm tra xem nó có giao nhau không khu vực đầu vào của tôi, nếu tôi lưu nó, cách khác tôi bỏ qua nó
5. khi tôi đến cạnh tôi làm một kiểm tra thêm để đảm bảo rằng tôi sẽ nhận được tất cả các điểm bên trong là
6. Tôi di chuyển điểm bằng cách mang 60 độ, kiểm tra nó, sau đó đến 120 độ, kiểm tra lại
7. quay lại bước thứ ba nhưng bây giờ tôi di chuyển các điểm bằng cách mang 180 độ
8. và cạnh lại một lần nữa kiểm tra và sau đó giống như ở bước 6 nhưng trước tiên 120 độ sau đó 60 độ
9. tiếp tục cho đến khi bạn đã đến cạnh trên của hình chữ nhật

như trong hình ảnh nhất định, tất nhiên bạn có thể tăng độ chính xác bằng cách giảm bán kính vòng tròn

Tôi biết rằng đây không phải là lựa chọn tốt nhất nhưng nó hoạt động khá tốt đối với tôi.

Tôi hy vọng nó khá dễ hiểu và sẽ giúp mọi người.