Złożoność obliczeniowa i zagnieżdżanie kształtów
Mam ścieżki abirtrary SVG, które muszę spakować tak efektywnie, jak to możliwe w obrębie danego prostokąta (jako mniej odpadów jak to możliwe). Po kilku badaniach znalazłem algorytmy pakowania bin, które wydają się zajmować pudełkami i nie zakrzywionymi losowymi kształtami (moje kształty SVG są dość złożone i obejmują beziers itp.).
AFAIK, nie ma deterministycznego algorytmu do faktycznego pakowania abstrakcyjnych kształtów.
Chciałbym się tutaj udowodnić, że byłby idealny (posiadanie matematycznej deterministycznej metody ich pakowania). Jeśli jednak mam rację i nie ma, jakie byłoby najlepsze podejście do tego problemu
Nazwa podmiotu toZagnieżdżanie kształtów, problem zagnieżdżania lub proces zagnieżdżania.
W zagnieżdżaniu kształtów nie ma jednego / jednolitego algorytmu lub metody matematycznej do zagnieżdżania kształtów i uzyskiwania możliwie najmniejszej ilości odpadów kosmicznych.
Pierwsza metoda to algorytm pakowania (tworzy wyimaginowaną ramkę ograniczającą dla każdego kształtu i wykorzystuje prostokątny algorytm 2D do spakowania ramek ograniczających). Ta metoda jest szybka, ale najmniej skuteczna w odniesieniu do odpadów kosmicznych.
Druga metoda to pewien rodzaj przyrostowego obrotu. Algorytm obraca kształt w przyrostowych krokach i sprawdza, czy pasuje do przestrzeni. Jest to lepsze niż metoda pakowania w odniesieniu do odpadów kosmicznych, ale jest żmudnie powolna,
Jakie są inneprzykłady w klasie za rozwiązanie tego problemu?