Tính phức tạp tính toán và hình dạng làm tổ

Question

Tôi có đường dẫn SVG tùy ý mà tôi cần đóng gói càng hiệu quả càng tốt trong một hình chữ nhật đã cho (càng ít lãng phí không gian càng tốt). Sau khi một số nghiên cứu tôi tìm thấy các thuật toán đóng gói bin mà dường như được giao dịch với các hộp và không cong hình dạng ngẫu nhiên (hình dạng SVG của tôi là khá phức tạp và bao gồm beziers vv).

AFAIK, không có thuật toán xác định để thực sự đóng gói hình dạng trừu tượng.

Tôi muốn được chứng minh là sai ở đây sẽ là lý tưởng (có phương pháp xác định toán học để đóng gói chúng). Trong trường hợp tôi ngay tuy nhiên và không có, những gì sẽ là phương pháp tốt nhất cho vấn đề này

Tên chủ đề là Shape Nesting, Nesting Problem or Nesting Process.

Trong Nesting Shape không có thuật toán đơn/thống nhất hoặc phương pháp toán học để làm tổ hình dạng và thu được lượng rác thải ít nhất có thể.

• Phương pháp 1 là thuật toán đóng gói (tạo ra một ảo bounding hộp cho mỗi hình dạng và sử dụng một thuật toán 2D hình chữ nhật để đóng gói các hộp bounding). Phương pháp này nhanh nhưng hiệu quả nhất liên quan đến không gian chất thải.

• Phương pháp thứ 2 là một số loại xoay gia tăng. Thuật toán xoay hình dạng ở các bước gia tăng và kiểm tra xem nó có vừa khít trong không gian không. Điều này là tốt hơn so với phương pháp đóng gói liên quan đến không gian chất thải nhưng nó là chậm chạp và đôi khi nó treo một máy tính hiện đại (Hãy tưởng tượng xoay mỗi hình dạng ở mức 1 độ và kiểm tra xem nó có phù hợp không. sẽ là ok nhưng những gì xảy ra tại > 20 hình dạng?

một số ví dụ lớp học khác để đạt được một giải pháp cho vấn đề này?

Answer 1

[Edit1] câu trả lời mới

là gì

như đã đề cập trước khi bin-đóng gói là NP đầy đủ (cứng) để quên về giải pháp đại số phương pháp gọi là:

1. tạo và thử nghiệm

   hoặc là bạn kiểm tra tất cả các khả năng của vấn đề và nhớ giải pháp tốt nhất hoặc từng bước thêm các mục (không phải tất cả cùng một lúc) từng cái một với cùng một cách. Đó là cơ bản những gì bạn đang làm bây giờ mà không có heuristic thích hợp là unusably chậm. Nhưng có hiệu quả không gian tốt nhất (người đầu tiên là tốt hơn nhiều nhưng chậm hơn nhiều) O(N!)

2. tận dụng lợi thế của phân loại tài liệu theo kích thước

   cái gì đó như this nó là nhanh hơn nhiều gần như O(N.log(N)) (theo sử dụng sắp xếp thuật toán). Hiệu quả không gian phụ thuộc rất lớn vào phạm vi kích thước của các mục và số lượng.Đối với hình chữ nhật, đây là phương pháp tốt nhất (nhanh nhất và có thể sử dụng ngay cả đối với N>1000). Đối với hình dạng phức tạp là thế này không phải là một cách tốt, nhưng nhìn vào nó anyway có thể bạn nhận được một số ý tưởng ...

3. sử dụng mạng Neural

   Đây là cách tiếp cận cực kỳ mơ hồ mà không cần bất kỳ lệnh của giải pháp nhưng tốt nhất có thể không gian hiệu quả/tỷ lệ thời gian chạy

4. tôi nghĩ rằng có thể có một số cách tiếp cận lĩnh vực ngoài kia

   tôi gieo một vài để tạo bố trí đồ thị. Tất cả các mục tạo ra các lĩnh vực (gian hàng hấp dẫn và đẩy lùi) để chúng chuyển sang trạng thái bán ổn định.

   • Lúc đầu tất cả các mục là tại các vị trí ngẫu nhiên
   • Khi phong trào dừng nhớ giải pháp tốt nhất và lắc tất cả các mục một chút hoặc ngẫu nhiên vị trí của họ một lần nữa.
   • Cycle vài lần này

   Cách tiếp cận này là nhanh hơn nhiều sau đó genere và thử nghiệm và có thể cung cấp giải pháp rất gần với nó, nhưng nó có thể treo ở địa phương min/max hoặc dao động nếu các lĩnh vực không phải là lựa chọn tối ưu. Ví dụ, tất cả các mục có thể có lực hấp dẫn không đổi với nhau và lực đẩy trở nên mạnh hơn chỉ khi các vật phẩm rất gần. Bạn phải ngăn chặn chồng chéo các vật phẩm (hoặc bằng cách đẩy mạnh hơn hoặc bằng các thử nghiệm va chạm). Bạn cũng phải tạo ra một số khoảnh khắc xoay ví dụ với lực đẩy đó. Nó khác trên bất kỳ đỉnh nào để nó tạo ra một khoảnh khắc quay (có thể tự động căn chỉnh các mặt tương tự gần nhau hơn). Ngoài ra, bạn có thể có trạng thái bán ổn định với khoảng cách lớn giữa các vật phẩm và sau khi tìm ra giải pháp tốt nhất chỉ cần tắt các trường đẩy để chúng dính vào nhau. Đôi khi nó có thể có kết quả tốt hơn một số lần không ... đây là ví dụ tốt đẹp cho tính toán bố trí đồ thị

   • Logic to strategically place items in a container with minimum overlapping connections
   • Demo from the same QA

   Và đây giải cho cách đặt thanh trượt trong 2D:

   • How to implement a constraint solver for 2-D geometry?

---

[Edit0] câu trả lời cũ trước khi tái trình các câu hỏi

Tôi không rõ những gì bạn muốn đạt được.

1. có hình ảnh SVG và muốn tách riêng bộ phận của nó với các khu vực hình chữ nhật
   • như điền như có thể
   • không gian trống ít nhất trong họ
   • không thay đổi hình dạng trong hình ảnh
2. có hình ảnh svg và muốn thay đổi hình dạng của nó theo một số mục đích
   • nếu đây là trường hợp một số thông tin bổ sung là cần thiết

[giải pháp cho 1]

1. tạo ra một danh sách các điểm cho toàn bộ SVG trong không gian SVG toàn cầu (tất cả các điểm được chuyển)
   • cho dòng bạn cần thêm 2 điểm
   • cho hình chữ nhật 4 điểm
   • tròn/elip/bezier/eliptic arc 8 điểm
2. tìm trung tâm địa phương của khối
   • sử dụng classical approach
   • hoặc có thể tăng tốc bằng những tính toán mật độ trung bình của điểm cho mỗi x, trục y riêng và sau đó chỉ cần kiểm tra tất cả các kết hợp của các vị trí tìm thấy của tối đa địa phương của mật độ nếu họ thực sự là trung tâm cụm phụ hay không.
3. tất cả các trung tâm cụm tiểu là trung tâm của khu vực của bạn
   • bây giờ tìm thấy những điểm xa nhất mà vẫn là một phần của cụm của bạn (là đủ gần để điểm hàng xóm)
   • tạo diện tích hình chữ nhật đó bao gồm tất cả các điểm từ cụm phụ.
   • bạn cũng có thể loại bỏ tất cả các điểm đã qua sử dụng từ danh sách
4. lặp lại fro tất cả các tiểu cụm hợp lệ
   • cho đến khi tất cả các điểm được sử dụng

khác không chính xác nhưng cách tiếp cận đơn giản hơn là :

1. tìm kích thước SVG
2. tạo bản đồ phẳng của svg với độ chính xác ví dụ như int map [256] [256].
   • kích thước của bản đồ có thể liên tục hoặc với các khía cạnh giống như SVG
3. bản đồ rõ ràng với 0
4. cho bất kỳ điểm nào của SVG liên quan thiết lập điểm bản đồ đến 1 (hoặc inc hoặc bất cứ điều gì)
5. bản đồ bây giờ chỉ cần segmentate và bạn sẽ phải tìm đối tượng của bạn
   • sau khi phân đoạn mà bạn có vị trí và kích thước của tất cả các đối tượng
   • nên f inding hộp bounding nên dễ

Answer 2

Bạn có thể bắt đầu với một biến thể của thuật toán bin-đóng gói hình chữ nhật và thêm quay. Có một phương pháp "Guillotine bin packer" và bạn có thể tải xuống một bài báo và thư viện tại github.