Ai đó có thể giải thích các calipers quay cho tôi không?

Question

Tôi đang vật lộn với việc tính toán hình chữ nhật kèm theo nhỏ nhất (tùy ý căn chỉnh) của một tập các điểm.

Tôi đã có thể tính toán vỏ lồi bằng thuật toán graham.

Nơi tôi bị kẹt là bước tiếp theo. Tôi nghĩ về việc sử dụng phương pháp calipers quay, nhưng tôi dường như không thể tìm thấy một lời giải thích đầy đủ về thuật toán.

Answer 1

Nếu bạn có vỏ lồi, thì thuật toán cơ bản dễ dàng. Bạn chỉ cần đi qua mỗi cạnh của thân lồi và xoay các điểm của bạn để cạnh đó dọc theo trục chính, giả sử trục X. Sau đó, bạn tìm thấy một hộp giới hạn trục liên kết của những điểm đó. Chọn bất kỳ hộp giới hạn nào là nhỏ nhất.

Có thể tìm thấy một hộp giới hạn theo trục bằng cách lấy tối thiểu và tối đa trong mỗi thứ nguyên.

Nếu bạn xoay hộp giới hạn của mình theo số tiền ngược lại, giờ đây nó sẽ bao gồm các điểm ban đầu của bạn.

Để làm điều này hiệu quả hơn, hãy lưu ý rằng các điểm duy nhất có thể ảnh hưởng đến hộp giới hạn nằm trên thân lồi.

Để làm cho nó thực sự hiệu quả, lưu ý rằng chỉ có bốn điểm xung quanh vỏ lồi đang chạm vào hộp giới hạn tại một thời điểm (điều này không đúng, nhưng bỏ qua điều đó bây giờ). Nếu bạn xoay các điểm vừa đủ để cạnh tiếp theo được căn chỉnh với hộp giới hạn, thì ba trong số các điểm đó giống nhau và một trong các điểm được thay thế bằng điểm tiếp theo xung quanh thân lồi. Điều này cho phép bạn tạo một thuật toán là tuyến tính trong số điểm trên thân lồi.

Bây giờ có những trường hợp đặc biệt khi hai cạnh song song hoặc vuông góc. Điều này sẽ gây ra hơn bốn điểm để chạm vào hộp giới hạn tại một thời điểm, nhưng nó thực sự không quan trọng. Nếu bạn có một sự lựa chọn giữa hai cạnh song song để sử dụng tiếp theo, bạn chỉ có thể chọn một tùy ý.