Điền vào hình dạng 2D tùy ý với tập hợp các hình chữ nhật

Question

Tôi có một bộ hình chữ nhật và hình dạng tùy ý trong không gian 2D. Hình dạng là không cần thiết một đa giác (nó có thể là một vòng tròn), và hình chữ nhật có chiều rộng và chiều cao khác nhau. Nhiệm vụ là để gần đúng hình dạng với hình chữ nhật càng gần càng tốt. Tôi không thể thay đổi kích thước hình chữ nhật, nhưng xoay vòng được cho phép.

Nghe có vẻ rất giống với packing problem và bao gồm vấn đề nhưng bao gồm khu vực không phải là hình chữ nhật ...

Tôi đoán đó là NP vấn đề, và tôi khá chắc chắn cần phải có một số giấy tờ cho thấy chẩn đoán tốt để giải quyết nó , nhưng tôi không biết phải làm gì với google? Tôi nên bắt đầu từ đâu?

Cập nhật: Một ý tưởng chỉ xuất hiện trong tâm trí của tôi nhưng tôi không chắc liệu nó có đáng để điều tra hay không. Điều gì sẽ xảy ra nếu chúng ta xem xét giới hạn hình dạng như một khuôn vật lý chứa đầy nước. Mỗi hình chữ nhật được coi là một hạt tích điện dương với kích thước. Bây giờ thả hình chữ nhật nhỏ nhất vào nó. Sau đó thả tiếp theo kích thước tại điểm ngẫu nhiên. Nếu hình chữ nhật quá gần, chúng đẩy nhau. Tiếp tục thêm hình chữ nhật cho đến khi tất cả được sử dụng. Phương pháp này có thể hoạt động không?

Answer 1

Tôi nghĩ bạn có thể tìm các thuật toán tạo bố cục đóng gói và tự động. Thuật toán tạo bố cục VLSI tự động có thể cần những thứ tương tự, giống như các câu hỏi bố trí dệt ...

Giấy này Hegedüs: Algorithms for covering polygons by rectangles dường như giải quyết một vấn đề tương tự. Và kể từ khi bài báo này bắt đầu từ năm 1982, có thể sẽ thú vị khi nhìn vào số papers which cite this one. Ngoài ra, this meeting dường như đang thảo luận các vấn đề nghiên cứu liên quan đến vấn đề này, vì vậy có thể là điểm bắt đầu cho từ khóa hoặc tên người nghiên cứu trong ý tưởng này.

Tôi không biết liệu nghiên cứu hình học tính toán có thuật toán cho vấn đề cụ thể của bạn hay không hoặc liệu các thuật toán này có dễ thực hiện hay không. Đây là cách tôi sẽ tiếp cận nó nếu tôi phải làm điều đó mà không thể tìm kiếm công việc trước đó. Đây chỉ là một hướng, cho đến nay không phải là một giải pháp ...

Xây dựng nó như là một vấn đề tối ưu hóa. Bạn có các biến rời rạc trong đó hình chữ nhật bạn chọn (có hoặc không) và các biến liên tục (vị trí và hướng của tam giác). Bây giờ bạn có thể thiết lập hai tối ưu hóa độc lập: một tối ưu hóa rời rạc mà chọn hình chữ nhật; và liên tục tối ưu hóa vị trí và hướng một khi hình chữ nhật được đưa ra. Interleave hai tối ưu hóa. Tất nhiên khó khăn nằm trong việc xây dựng các tối ưu hóa và thiết kế năng lượng lỗi của bạn sao cho nó không bị kẹt trong một số cấu hình lạ (minima cục bộ). Tôi cố gắng để có được liên tục như là một vấn đề least squares như vậy mà tôi có thể sử dụng thư viện tối ưu hóa tiêu chuẩn.

Answer 2

Tôi nghĩ vấn đề này phù hợp để giải quyết bằng thuật toán di truyền và/hoặc thuật toán chiến lược tiến hóa. Tôi đã thực hiện vấn đề đóng gói hộp tương tự với sự trợ giúp của thuật toán chiến lược tiến hóa của một số loại. Kiểm tra này ra in my blog.

Vì vậy, nếu bạn sẽ sử dụng cách tiếp cận như vậy - mã hóa vào nhiễm sắc hộp:

• tọa độ x
• tọa độ y
• góc

Sau đó cố gắng hạn chế tối đa tập thể dục như function-

y = w1 * box_intersection_area + W2 * box_area_out_of_shape + w3 * average_circle_radius_in_free_space

Chọn trọng lượng W1, W2, W3 như ảnh hưởng đến tầm quan trọng của yếu tố này. Khi thuật toán di truyền sẽ tìm thấy một phần giải pháp - loại bỏ các hộp mà vẫn chồng chéo với nhau hoặc ra khỏi hình dạng - và bạn sẽ có ít nhất là hợp pháp (nhưng không cần thiết tối ưu) giải pháp.

chúc may mắn trong vấn đề thú vị này!

Answer 3

Đó là NP thực sự khó khăn và vì nó có ứng dụng công nghệ cao, chiến lược gần đúng hiệu quả tương đối thậm chí không bằng sáng chế, hãy để một mình xuất bản giấy tờ.

Điều tốt nhất bạn có thể làm với ngân sách hạn chế là bắt đầu bằng cách giới hạn sự cố. Giả sử rằng tất cả các hình chữ nhật đều giống nhau, Giả sử rằng tất cả các hình chữ nhật là các phần con nhị phân của hình chữ nhật chuẩn của bạn cũng được cho phép vì bạn có thể đóng gói chúng một cách hiệu quả để phù hợp với bộ phận cốt lõi của bạn. Đối với các điểm phụ, bạn cũng có thể tạo thành một số lược đồ cố định cho hình chữ nhật lõi dán để bao gồm một vài hình dạng lớn hơn với tỷ lệ khác nhau đáng kể. Giả sử rằng bạn có thể thay đổi kích thước của hình chữ nhật/ô chuẩn của bạn miễn là phần còn lại (lược đồ đóng gói sẵn và dán) vẫn giữ nguyên - điều này cung cấp cho bạn các tham số để quyết định kích thước gần đúng của hình chữ nhật lõi dựa trên hình chữ nhật bạn được cung cấp.

Giờ đây, bạn có thể phát với tỷ lệ khung hình để ước tính lỗi mà hệ thống giới hạn như vậy có thể đảm bảo. Đối với các lần lặp đầu tiên giả định rằng nó có thể có lỗi 50% với lược đồ phân chia đơn giản và sau đó thay đổi lược đồ để giảm lỗi nhưng không làm tăng độ phức tạp tiệm cận trước khi đóng gói. Vào cuối ngày, bạn luôn chỉ gán các hình chữ nhật đã cho trước của bạn đã được tính toán trước và bây giờ cố định lưới và nhị phân phụ - có nghĩa là bạn không cố gắng để làm một bố trí hoặc backtrack ở tất cả - bạn luôn luôn hài lòng với gần đúng đầu tiên phù hợp với lưới điện.

Làm việc xác định các lớp hình chữ nhật phù hợp với giản đồ của bạn - đó là một lần nữa để giữ cho toàn bộ quá trình đảo ngược - bạn sẽ không bao giờ thực sự phù hợp với những gì bạn đã cung cấp - bạn đang xác định những gì bạn phải đưa ra để làm vững chắc nó - sau đó bạn punt phần còn lại là lỗi vì nó là xấp xỉ.

Sau đó, bạn có thể cố gắng làm nhiều hơn một chút, nhưng không nhiều hơn nữa - bất kỳ sự cố nào trong quá trình quay trở lại hoặc đóng đinh sai số nhỏ tùy ý và nó theo cấp số mũ.

Nếu bạn đang ở cơ sở nghiên cứu và có thể nhận được một số thời gian siêu máy tính - hãy chạy một tập hợp tìm kiếm đầy đủ với hỗn hợp bệnh lý ở đó để xem cách đóng gói tối ưu như thế nào và xem liệu bạn có thể lấy thêm một vài phân chia lược đồ và/hoặc các lớp của bộ chữ nhật.

Điều đó là đủ trong 2 năm đầu tiên hoặc nghiên cứu :-)