Hộp hình chữ nhật nhỏ nhất bao quanh một đa diện

Question

Tôi đang tìm một thuật toán tìm thấy hộp nhỏ nhất bao quanh một đa diện.

Ý tưởng của tôi là như sau: tìm mặt lớn nhất và di chuyển phần cứng sao cho mặt thẳng hàng với trục x. Tìm cạnh lớn nhất tiếp theo đáp ứng bên này, và căn chỉnh nó càng gần càng tốt với trục z, trong khi rời phía bên kia trên x. Sau đó, tính toán sự khác biệt lớn nhất trong x, y và z. Sử dụng các kích thước đó để tạo hình dạng xung quanh và sau đó chuyển hộp trở lại vị trí ban đầu của đối tượng.

Có chiến lược hiệu quả hơn cho việc này không? Ý tưởng của tôi có bỏ qua một số trường hợp góc không?

Chỉnh sửa: Hiện tại giả sử đối tượng bị giới hạn là lồi. Mặc dù, một câu trả lời cho trường hợp chung cũng sẽ được hoan nghênh.

Answer 1

Vấn đề của việc tìm kiếm tối thiểu (khối lượng) hộp cho đa diện lồi đã được nghiên cứu bởi O'Rourke, người đề xuất một thuật toán O(n^3):

J. O-Rourke. Tìm hộp kèm theo tối thiểu. Tạp chí Quốc tế Máy tính & Thông tin Khoa học, 1985, 14 (3), tr.183.

thuật toán O'Rourke của thấy hộp kèm theo tối thiểu cho một tập hợp các điểm trong R^3 - nhưng điều này rõ ràng là tương đương với việc tìm kiếm hộp kèm theo cho đa diện hình thành như thân lồi của các điểm-bộ cơ bản.

Trái với những gì người ta có thể mong đợi (và cách tiếp cận các bạn đã mô tả, nếu tôi đã hiểu bạn một cách chính xác), hộp tối thiểu không nhất thiết phải theo định hướng như vậy mà một mặt của đa diện là đồng phẳng với một khuôn mặt của hộp ! Lưu ý hoạt ảnh được hiển thị here cho một hình tứ diện đơn giản.

Nếu bạn hài lòng với ý tưởng chỉ cần tìm một hộp kèm theo đó là tương đối nhỏ, chứ không phải là các hộp kèm theo nhỏ nhất, có thể có khác (nhanh hơn) chẩn đoán có thể áp dụng ...