Wybrałem ten dział, ponieważ najbardziej pasuje mi on do tego zagadnienia.
Na początku pozwolę sobie opisać założenia oraz problem z którym mam do czynienia.
- Użytkownik rysuje dowolny kształt.
dajemy możliwość każdemu wyrysowania ścieżki, która po zakończeniu tworzy daną figurę geometryczną. Zakładamy że najprostszą figurą jest trójkąt, a najbardziej złożoną wielokąt z n-bokami. - Algorytm spośród dostępnej bazy prostokątów musi wybrać tylko te, które zmieszczą się w wyrysowanym wielokącie
I właśnie pkt 2 jest problemem. Pozwolę sobie załączyć grafikę do reprezentacji problemu:
Jak określić maksymalny rozmiar prostokąta, który może zostać wpisany w tę figurę? Mamy tutaj 2 składowe
- wcięcie wielokąta w prawym górnym rogu, które znacznie zmniejsza wielkość wpisanej figury
- pochylenie wszystkich krawędzi pod różnymi kątami w stosunku do osi OX oraz OY - wymagana jest rotacja wpasowywanego elementu.
I tak tutaj - dla tego przykładu interesującym mnie wymiarem jest niebieska linia oznaczona jako "max X", analogicznie muszę dopasować długość max 2 boku.
Szukałem dość długo jakiegoś równania bądź zależności, która pozwoli mi rozpocząć pracę nad takim algorytmem. Niestety nic sensownego nie znalazłem.
O ile sytuacja gdzie mamy wpisać prostokąt w trójkąt bądź inny prostokąt gdzie krawędzie są prostopadłe do osi OX czy OY nie wydaje sie trudne, o tyle kwestie bardziej złożonych figur oraz ich możliwych rotacji to już inna bajka.
Może ktoś kiedyś miał do czynienia z podobnym problemem? Szukam rozwiązania, które działa nie musi być idealne.
Jeśli algorytm radziłby sobie tylko z dopasowaniem (bez rotacji) to jest to dla mnie punkt wyjścia i już jakieś wstępne określenie maksymalnego kształtu.
dodam także, że całość będzie wykonywana w JS w oparciu o rysowanie svg (biblioteka https://svgjs.com/docs/3.0/)
Musi to być narzędzie webowe stąd też wybór tej technologii.