Rozważ region (2D) wypełniony losowo liniami (patrz rysunek). Jesteśmy zainteresowani wypełnieniem pustych przestrzeni między liniami, w tym czterema krawędziami granicznymi w następujący sposób:
0 - maksymalizacja wielkości paczek;
1- kształt wypełnienia paczek jest kwadratowy wyrównany poziomo lub pionowo;
2- kształt wypełnienia paczek jest kwadratowy, tzn. Luźne wyrównanie ;
3- kształt wypełnienia paczek to dowolny czworokąt. nasze oryginalne pytanie
Na razie istnieją trzy różne scenariusze.
Zauważ, że linie są [x1,y1,x2,y2]ustawione na punkt formalny , liczby rzeczywiste.
[* * *] Pomysły dotyczące możliwych rozwiązań / algorytmów / fragmentów kodu / itp. Są mile widziane.
Aktualizacja 1: Mogliśmy zarządzać rozwiązaniem dla pierwszego przypadku:
Kroki to:
1- linie
2- rasteryzacja linii w mapę bitową
3- wyszukiwanie pobliskich komórek dla każdej komórki o pożądanym kolorze (tj. Tego samego koloru) z funkcją celu, aby zmaksymalizować obszar, tj. liczba komórek.
Działa dobrze, ale obejmuje tylko pierwszy scenariusz i jest również powolny.
Aktualizacja 2:
Zakładamy, że czytelnik zna koncepcję wypełniania przestrzeni-układania płytek. Możesz skorzystać z linku, aby uzyskać inspirację. Pamiętaj jednak, że nasz problem jest inny. Ponieważ nie wypełniamy losowo pustej przestrzeni i nie wybieramy wielkości losowo. Rozwiązanie powinno być iteracyjne. We wszystkich przypadkach nie ma ograniczenia liczby montowanych paczek. Rzeczywiście, użytkownik musi ograniczyć liczbę iteracji, wybierając na przykład minimalny obszar dla paczek. Jest to oczywiste w podanym powyżej przykładzie, w którym dyskretyzowaliśmy linie na piksele o określonym rozmiarze. Oznacza to, że procedura powinna trwać do momentu zapełnienia całego pustego obszaru z zachowaniem kryterium np. Maksymalnego obszaru paczek.
Aktualizacja 3:
streszczenie:
Jednym z zastosowań jest ustalenie rozmieszczenia nienaruszonych, nienaruszonych bloków „skalnych” w mocno spękanej „kopalni”. Może to być bardzo pomocne w wielu aspektach, w tym w projektowaniu odwiertów, ocenie finansowej itp.
Opis: w
przypadku kopalni skał dekoracyjnych (kamienia), produktów, które są blokami nietkniętych skał pociętych w prostokątne kostki, cena jest ściśle zależna od wielkości blok. Ekstrakcja bloku z odpowiedniego obszaru, tj. Bez poważnego pęknięcia, będzie pożądana, jeśli ilość pozostałych części będzie jak najmniejsza. Zwykle małe kawałki skał nie mają względnej wartości ekonomicznej i są uważane za odpady.
Pytanie w tym poście dotyczy rozwiązań tego rodzaju problemu.
Matematyczny widok problemu można określić w następujący sposób:
2D: Znajdź wszystkie prostokąty, które można wyodrębnić z danego regionu 2D, z niektórymi liniami zoptymalizowanymi pod kątem większego rozmiaru prostokąta.
3D: Znajdź wszystkie prostokątne kostki, które można wyodrębnić z danego regionu 3D za pomocą niektórych płaszczyzn (lepiej: wielokątów) zoptymalizowanych pod kątem większego rozmiaru bloku.
Ponieważ jest to część trwających badań, niektóre pytania zadane w komentarzach poniżej nie zawierają pewnych odpowiedzi, które możemy udzielić. Uważamy, że podane tu informacje są w rzeczywistości wystarczające, aby uzyskać ogólny obraz problemu. Niemniej jednak podajemy pewne szczegółowe informacje na temat korzyści dla społeczności.
Możesz nałożyć pewne ograniczenia na rozwiązanie ostatecznego pytania, chociaż uważamy, że zawsze można dodać więcej później. Na przykład wykonaj następujące czynności: {przypadek 2D}
Najlepszy rozmiar bloku (prostokąt optymalny ekonomicznie) do wyodrębnienia w wyżej wymienionych warunkach 1x1 mpodano 10x10 mdla regionu w przykładzie. Jest to jedno ograniczenie zdefiniowane na podstawie wartości ekonomicznej. Niech będzie minimalny możliwy do wykonania rozmiar do cięcia itp0.15x0.15 m; więc to drugi limit wielkości.
Powyższy rysunek pokazuje funkcję wartości ekonomicznej w zależności od wielkości bloku. Więc w tym konkretnym przypadku każdy kawałek skały mniejszy niż 0.15x0.15 mzwykły odpad. Rozmiar bloku nie będzie większy niż 1.7x1.7 mze względu na ograniczenia operacyjne.
Odpowiedzi:
Mam pomysł, w jaki sposób iteracyjnie pracujesz od dużych bloków do mniejszych bloków za pomocą FME (Safe Software). Dla przypomnienia, nie pracuję dla nich, ale wydaje mi się, że chwalą ich narzędzie ...
Spłucz i powtórz tyle razy, ile to konieczne, za każdym razem używając mniejszych płytek. Dołączyłem początek stołu warsztatowego, którego użyłbym jako jedno podejście.
Na podstawie twojego (ładnie szczegółowego) opisu, na razie będzie działać tylko z opcją 1. Nie poświęcając jeszcze zbyt wiele czasu.
W każdym razie jest to tylko jedno podejście, od którego chciałbym przynajmniej odfiltrować pszenicę z plew.
źródło