Thuật toán đóng gói hiệu quả cho các đa giác không đều

Question

Tôi đang tìm một thuật toán đóng gói sẽ làm giảm đa giác bất thường thành hình chữ nhật và hình tam giác bên phải. Thuật toán nên cố gắng sử dụng càng ít hình dạng càng tốt và nên tương đối dễ thực hiện (do khó khăn của thử thách). Nó cũng nên thích hình chữ nhật trên hình tam giác nếu có thể.

Nếu có thể, câu trả lời cho câu hỏi này sẽ giải thích các chẩn đoán chung được sử dụng trong thuật toán được đề xuất.

Điều này sẽ chạy trong thời gian xác định cho các đa giác bất thường có ít hơn 100 đỉnh.

Mục đích là tạo ra sự phân tích "hợp lý" của đa giác bất thường cho một giáo dân.

Phương pháp heuristic đầu tiên được áp dụng cho giải pháp sẽ xác định xem đa giác có thường xuyên hay không đều. Trong trường hợp của một đa giác thường xuyên, chúng tôi sẽ sử dụng phương pháp nêu trong bài tương tự của tôi về polys thường xuyên: Efficient Packing Algorithm for Regular Polygons

alt text http://img401.imageshack.us/img401/6551/samplebj.jpg

Answer 1

Tôi không biết nếu điều này sẽ cung cấp cho câu trả lời tối ưu, nhưng nó sẽ ít nhất trả lời:

1. Tính toán tam giác Delaunay cho đa giác đã cho. Có các thuật toán chuẩn để thực hiện điều này sẽ chạy rất nhanh với 100 đỉnh hoặc ít hơn (xem, ví dụ: this library here.) Sử dụng một tam giác Delaunay phải đảm bảo rằng bạn không có quá nhiều hình tam giác dài và mỏng.
2. Chia mọi hình tam giác không đúng thành hai hình tam giác bên phải bằng cách thả độ cao từ góc lớn nhất sang phía đối diện.
3. Tìm kiếm các hình tam giác mà bạn có thể kết hợp thành hình chữ nhật: bất kỳ hai hình tam giác bên phải đồng nhất nào (không phải hình ảnh phản chiếu) có chung một cạnh huyền. Tôi nghi ngờ sẽ không có quá nhiều trong số này trong trường hợp chung trừ khi đa giác bất thường của bạn đã có rất nhiều góc độ bên phải để bắt đầu.

Tôi nhận ra đó là rất nhiều chi tiết để điền vào, nhưng tôi nghĩ rằng bắt đầu với một tam giác Delaunay có lẽ là con đường để đi. Các tam giác Delaunay trong mặt phẳng có thể được tính toán một cách hiệu quả và nhìn chung chúng trông khá "tự nhiên". CHỈNH SỬA THÊM: kể từ khi chúng tôi đang ở trong heuristicville đặc biệt, ngoài các thuật toán tham lam đang được thảo luận trong câu trả lời khác, bạn cũng nên xem xét một số loại chiến lược phân chia và chinh phục. Nếu hình dạng không lồi như ví dụ của bạn, hãy chia nó thành hình dạng lồi bằng cách liên tục cắt từ đỉnh phản xạ sang đỉnh khác theo cách gần nhất để chia góc phản xạ càng tốt. Một khi bạn đã chia hình thành các phần lồi, tôi sẽ xem xét tiếp theo chia các phần lồi thành từng mảnh với các "căn cứ" đẹp, các mảnh có ít nhất một bên có hai góc nhọn hoặc góc phải ở hai đầu của nó. Nếu bất kỳ phần nào không có một "cơ sở", bạn sẽ có thể chia nó thành hai dọc theo một đường kính của mảnh, và nhận được hai phần mới mà mỗi cái có một "cơ sở" (tôi nghĩ). Điều này sẽ làm giảm vấn đề để đối phó với đa giác lồi mà là kinda-sorta hình thang, và từ đó một thuật toán tham lam nên làm tốt. Tôi nghĩ rằng thuật toán này sẽ chia nhỏ hình dạng ban đầu một cách khá tự nhiên cho đến khi bạn nhận được các mảnh hình thang kinda-sorta.

Answer 2

Tôi muốn tôi có thời gian để chơi với điều này, bởi vì nó có vẻ giống như một vấn đề thực sự thú vị!

Suy nghĩ đầu tiên của tôi (nhìn vào sơ đồ của bạn ở trên) sẽ là tìm 2 góc vuông liền kề quay cùng hướng.Tôi chắc chắn rằng sẽ không bắt mọi trường hợp mà một hình chữ nhật sẽ giúp đỡ, nhưng từ quan điểm của người dùng, đó là một trường hợp hiển nhiên (góc vuông ở bên ngoài = này phải là một hình chữ nhật).

Khi bạn đã tìm thấy một cặp góc liền kề, hãy đo chiều dài của chân ngắn hơn và có một hình chữ nhật. Trừ này từ đa giác còn lại để gạch, và lặp lại. Khi không có hình chữ nhật bên ngoài rõ ràng hơn để loại bỏ, sau đó làm điều lát gạch bình thường của bạn (câu trả lời của Peter âm thanh tuyệt vời) về điều đó.

Disclaimer: Tôi không phải chuyên gia về vấn đề này, và tôi đã thậm chí không thử nó ...