Tìm một hình chữ nhật bị chặn bên trong một đa giác lõm/lồi

Question

Tôi đang tìm một phương pháp để tìm hình chữ nhật được căn chỉnh trục bên trong một đa giác lõm hoặc lồi.

Tôi đã tìm kiếm trên web, các giải pháp gần nhất tôi có thể tìm thấy sẽ chỉ vừa với đa giác lồi và không vừa lõm. Ví dụ -

Finding an axis-aligned rectangle inside a polygon

Thành thật mà nói tôi không phải là một Wiz toán lớn, vì vậy tôi thà tìm mẫu mã hoặc một thư viện mã, nhưng tôi đoán tôi có thể xử lý một số toán học bởi bản thân mình, hoặc tìm một người nào đó để giúp tôi với nó.

Nó sẽ thực sự thoải mái nếu các giải pháp có thể là trong Java quá, nhưng có lẽ tôi quá tham lam: P

Sửa: Đáp lại lời nhận xét của Russell, tôi thêm một thông tin chút.

Hình chữ nhật bị chặn phải càng lớn càng tốt. Hình chữ nhật được dùng để chứa văn bản bên trong nó. Tối đa 1 đến 4 từ, với hỗ trợ cho gói văn bản. Vì vậy, nếu ví dụ nó sẽ là quá mỏng, tôi sẽ đặt văn bản theo chiều dọc thay vì theo chiều ngang. Vì vậy, đối với tỷ lệ khung hình, tôi đoán nó cần phải đủ để chứa 1-4 từ hoặc theo chiều dọc hoặc chiều ngang với gói từ. Tôi có thể thay đổi kích thước văn bản nếu hình chữ nhật nhỏ, nhưng tốt nhất là văn bản nên càng lớn càng tốt.

Một yêu cầu khác sẽ tốt hơn nếu định hướng chung của đa giác là đường chéo và văn bản sẽ phù hợp hơn khi được định hướng theo đường chéo, sau đó hình chữ nhật sẽ không nhất thiết phải được căn chỉnh với trục 'nhưng thay vào đó được căn chỉnh với các đường chéo của đa giác. Tôi đoán nhu cầu này đang làm cho điều này thực sự phức tạp, nhưng nếu các bạn nghĩ rằng nó có thể thì nó sẽ rất tuyệt!

Tôi nghĩ rằng tôi đã bao gồm tất cả các yêu cầu ngay bây giờ. : P

Cảm ơn!

Answer 1

Vì bạn muốn làm điều này cho văn bản, tôi cho rằng tốc độ là quan trọng, độ chính xác kém quan trọng. Tôi đề nghị điều này sau đó:

1. Đặt đa giác trên lưới có ô tỷ lệ thuận với kích thước văn bản.
2. Xóa các ô trên ranh giới sử dụng Bresenham's line algorithm..
3. Hủy bỏ các tế bào bên ngoài các tế bào ranh giới (bằng cách làm việc từ các cạnh của lưới điện bên trong.
4. Tìm hình chữ nhật tối đa trên các tế bào còn lại, ví dụ như phương pháp thể hiện here.

Xem thêm Puzzle: Find largest rectangle (maximal rectangle problem).

EDIT: Tôi vừa nhận thấy yêu cầu thuật toán này điều chỉnh nếu đa giác được định hướng ở một góc. Đề xuất của tôi là tìm principle axes của đa giác để kiểm tra hướng, xoay nó để căn chỉnh trục chi phối với trục x và áp dụng thuật toán ở trên.

Ngoài ra, tôi muốn lưu ý rằng "xóa ô" thực sự chỉ có nghĩa là đặt bit trong một mảng 2D đại diện cho ô lưới.

Answer 2

Tôi đã từng triển khai một hệ thống tương tự theo cách thực sự kludgey bằng cách chỉ thực hiện tìm kiếm thông qua các hình chữ nhật có thể và sử dụng Shape.contains() trên chúng. Đó là hơi chậm - có lẽ 1s để bố trí ra địa chỉ Gettsburg trong một hình bầu dục - nhưng hữu ích cho văn bản tĩnh và cho văn bản nhỏ trong hình dạng đơn giản.

Nếu bạn quan tâm, bạn có thể giải nén tệp jar here và xem TextWrappingLayout. Nó có thể phức tạp hơn nhiều so với những gì bạn cần, bởi vì thay vì đặt trong một hình chữ nhật duy nhất nó cố gắng đặt mỗi dòng càng gần mép càng tốt, nhưng bạn có thể thấy ý tưởng cơ bản.