Tôi đang tìm một thuật toán đóng gói sẽ làm giảm đa giác thông 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).Thuật toán đóng gói hiệu quả cho các đa giác thông thường
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.
Tôi nghĩ câu trả lời khá đơn giản đối với các đa giác thông thường.
Tìm trục đối xứng và vẽ một đường thẳng giữa mỗi đỉnh và gương của nó. Điều này chia đa giác thành hình thang. Mỗi hình thang có thể được biến thành một hình chữ nhật và hai tam giác vuông.
Bạn có thể nhận thêm một số tín dụng bằng cách chứng minh rằng điều này tạo ra số lượng gạch tối thiểu. :) – Svante
Tôi tin rằng điều này thực sự là tối ưu :-) – Mau
Không. Nó không phải lúc nào cũng tối ưu. Lấy ví dụ một hình lục giác thông thường với hai cạnh song song với trục x = 0. Sau đó, thuật toán này tạo ra 2 hình chữ nhật và 4 tam giác vuông, nhưng 1 hình chữ nhật và 4 hình tam giác là đủ. Tuy nhiên, giải pháp có thể đủ tốt và dễ thực hiện. – abc
Nó không phải là hình chữ nhật cụ thể + hình tam giác bên phải, nhưng một điểm nghiên cứu tốt để xem xét các đa giác tesselating là Voronoi Diagrams and Delaunay Triangulations và here và here. Trong thực tế, nếu "hình tam giác vừa phải" đủ tốt, chúng được đảm bảo để tạo hình tam giác cho bạn và bạn luôn có thể chia tam giác thành hai tam giác vuông, nếu bạn thực sự cần những hình tam giác đó. Hoặc bạn có thể cắt bỏ "mẹo" của hình tam giác để tạo hình tam giác bên phải và một số hình chữ nhật ra khỏi hình tam giác bên phải.
Bạn cũng có thể thử ear-clipping, hoặc bằng cách quét xuyên tâm, nếu bạn biết bạn có đa giác khá thường xuyên hoặc bằng cách "cắt đoạn lồi lớn nhất". Sau đó, chia từng tam giác còn lại thành hai để tạo tam giác vuông.
polygon http://static.eruciform.com/images/polygon.png
Bạn có thể thử để làm phá vỡ ít bằng cách quét một cách rồi đến bên kia để tạo ra một hình thang và chia nó khác nhau, nhưng sau đó bạn phải làm một kiểm tra để đảm bảo rằng quét dòng của bạn hasn 't vượt qua một dòng khác ở đâu đó. Bạn luôn có thể kẹp tai, ngay cả với một cái gì đó thực tế fractal.
Tuy nhiên, điều này đôi khi tạo ra hình tam giác rất mỏng. Bạn có thể thực hiện heuristics, như "take the big", thay vì cắt liên tục dọc theo cạnh, nhưng phải mất nhiều thời gian hơn, tiếp cận O (n^2). Delaunay/Vornoi sẽ làm điều đó nhanh hơn trong hầu hết các trường hợp, với hình tam giác nhỏ hơn.
Tuyệt đối phải là hình chữ nhật và hình tam giác bên phải. Tôi biết nghe có vẻ kỳ lạ, nhưng đó là yêu cầu của người dùng. Đã cập nhật – Steve
. bạn có thể biến bất kỳ hình tam giác nào thành hình tam giác và hình chữ nhật bên phải một cách dễ dàng. – eruciform
Tam giác Delaunay không lý tưởng ở đây vì chúng giới thiệu các điểm bổ sung, không cần thiết ở giữa. Mỗi điểm trong số đó có thể được "kéo" tới một đỉnh đa giác lân cận và bạn được để lại với một tập hợp tam giác nhỏ hơn. –
Bạn có thể thử "cắt" the largest rectangle that can fit in the polygon, để lại một số thức ăn thừa. Tiếp tục lặp lại việc cắt hình chữ nhật trên các thức ăn thừa, cho đến khi bạn kết thúc với các miếng hình tam giác. Sau đó, bạn có thể chia chúng thành hai tam giác vuông nếu cần thiết. Tôi không biết nếu điều này sẽ luôn luôn mang lại các giải pháp mà sẽ cung cấp cho bạn hình chữ nhật số tiền ít nhất và hình tam giác bên phải.
Tôi nghĩ rằng đây không phải là một ý tưởng hay: ăn đi càng nhiều diện tích càng tốt với hình chữ nhật đầu tiên sẽ không để bạn với hình dạng "dễ nhất" sau đó. – Mau
không rõ yêu cầu của anh ta là gì. ít nhất là tổng số hình dạng hoặc hầu hết diện tích trong ít hình dạng nhất ... – eruciform
Đối với đa giác thông thường, nó vẫn sẽ cung cấp cho bạn hình dạng "đẹp". Một lần nữa, tôi không biết nếu điều này sẽ cung cấp cho bạn các giải pháp "tối ưu nhất". –
đây có phải là lớp học thuật toán hay lớp đồ họa máy tính không? – eruciform
Nó không phải dành cho một lớp học. Tôi không đi học. – Steve
Trong thực tế, tôi có thể sẵn sàng cung cấp cho một người có thể trả lời câu hỏi cũng một lời mời làm việc nếu họ có thể lập trình cho iPhone, máy tính để bàn Mac và .net. ;) – Steve