Tôi muốn tìm xoay và vị trí cho đa giác để tối đa hóa mức độ lớn của nó trong phạm vi ràng buộc trong một đa giác lớn hơn.Tìm đa giác diện tích tối đa được ghi trong đa giác lớn hơn
ý tưởng hiện tại là sử dụng scipy optimization routines để tối ưu hóa vị trí và luân chuyển các thông số để tối đa hóa các tham số scaling, và shapely để thêm một hạn chế mà đa giác được chứa. Điều này có vẻ như nó sẽ chậm và không đặc biệt thanh lịch.
Các ý tưởng khác?
Sự cố này có vẻ như có thể là NP-Hard. Cho một giải pháp ứng cử viên, bạn không thể chắc chắn rằng đó là giải pháp tốt nhất. Có vẻ như bạn cần phải cố gắng sử dụng một số loại tìm kiếm ngẫu nhiên gia tăng.
Nếu đa giác bên trong được chia tỷ lệ tối đa, thì có ít nhất 4 cặp "đỉnh bên trong - cạnh bên ngoài" hoặc "cạnh ngoài - cạnh trong" nơi đỉnh nằm trên cạnh.
Hãy lấy tất cả 4s cặp cạnh theo chiều dọc. Đối với mỗi người chúng ta có được hệ phương trình tuyến tính cho hai tọa độ điểm tham chiếu. Nếu nó có một giải pháp, chúng tôi xác minh rằng không có giao lộ và nếu OK, chúng tôi nhớ tọa độ và kích thước của đa giác nội bộ.
Đây là giải pháp chính xác nhưng chậm. Mặt khác, thói quen tối ưu hóa scipy có khả năng tìm thấy một tối đa địa phương mà không phải là một toàn cầu.
Các đa giác đơn giản này có phải không? Có giới hạn về số lượng mặt không? –
Có, chỉ đơn giản là đa giác. Một số người trong số họ có thể có trên thứ tự của 100 bên. – daedalus12
Tôi đang cố gắng tìm ra điều gì đó tương tự - bạn có thể cho tôi biết thói quen bạn đang sử dụng từ scipy không? –