Znajdowanie prostokąta ograniczonego wewnątrz wklęsłego/wypukłego wielokąta

Question

Poszukuję metody znajdowania wyrównanego względem osi prostokąta wewnątrz wielokąta wklęsłego lub wypukłego.

Szukałem w Internecie, najbliższe rozwiązania, jakie mogłem znaleźć, pasowałyby tylko do wypukłego wielokąta, a nie do wklęsłego. Na przykład -

Finding an axis-aligned rectangle inside a polygon

Szczerze mówiąc nie jestem wielkim matematyki wiz, więc wolałbym znaleźć przykłady kodu lub biblioteki kodu, ale myślę, że mogę sobie trochę matematyki przez siebie, albo znaleźć kogoś aby mi w tym pomóc.

Byłoby naprawdę miło, gdyby rozwiązanie może być w Javie też, ale może jestem zbyt zachłanny: P

Edit: W odpowiedzi na komentarz Russella, Dodaję trochę więcej informacji.

Prostokąt ograniczony powinien być jak największy. Prostokąt ma zawierać tekst wewnątrz. Maks. Od 1 do 4 słów, z obsługą zawijania tekstu. Jeśli na przykład byłaby zbyt cienka, umieściłbym tekst w pionie zamiast w poziomie. Tak więc dla proporcji, domyślam się, że musi wystarczyć do umieszczenia 1-4 słów w pionie lub poziomie z zawijaniem słów. Mogę zmienić rozmiar tekstu, jeśli prostokąt jest mały, ale najlepiej tekst powinien być tak duży, jak to możliwe.

Innym wymaganiem, które byłoby miłe, byłoby to, że jeśli ogólna orientacja wielokąta jest przekątna, a tekst będzie pasował znacznie lepiej, gdy jest zorientowany ukośnie, wówczas prostokąt nie musi być wyrównany z osią ", ale zamiast tego powinny być wyrównane z ukośnymi liniami wielokąta. Sądzę, że to żądanie sprawia, że ​​jest to naprawdę trudne, ale jeśli myślicie, że to możliwe, byłoby wspaniale!

Myślę, że już teraz spełniłem wszystkie wymagania. : P

Dzięki!

Answer 1

Ponieważ chcesz zrobić to dla tekstu, założę się, że prędkość jest ważna, a dokładność mniej ważna. Sugeruję to:

1. Umieść wielokąt na siatce z komórkami proporcjonalnymi do wymiarów tekstu.
2. Usuń komórki na granicy za pomocą Bresenham's line algorithm..
3. usunięcia komórek poza komórkami brzegowych (pracując z krawędzi siatki wewnątrz.
4. znaleźć maksymalną prostokąt na pozostałych komórek, na przykład sposób przedstawiony here.

Patrz także Puzzle: Find largest rectangle (maximal rectangle problem).

EDYCJA: Właśnie zauważyłem, że algorytm ten dostosowuje się, jeśli wielokąt jest zorientowany pod kątem. Proponuję znaleźć principle axes wieloboku, aby sprawdzić orientację, obrócić go, aby wyrównać oś dominującą do osi X i zastosować powyższy algorytm.

Ponadto chciałbym zauważyć, że "usunięcie komórki" naprawdę oznacza po prostu ustawienie bitu w tablicy 2D, która reprezentuje komórki siatki.

Answer 2

Kiedyś zaimplementowałem podobny system w naprawdę kludgey, po prostu przeszukując możliwe prostokąty i używając na nich Shape.contains(). Trochę powolny - być może 1s dla układu adresu Gettsburg w owalnym - ale przydatny dla tekstu statycznego i dla małego tekstu w prostych kształtach.

Jeśli jesteś zainteresowany, możesz rozpakować plik JAR here i przejrzeć TextWrappingLayout. Prawdopodobnie jest to o wiele bardziej skomplikowane niż to, czego potrzebujesz, ponieważ zamiast układać w jednym prostokącie, próbuje umieścić każdą linię tak blisko krawędzi, jak to tylko możliwe, ale możesz zobaczyć podstawowy pomysł.