Wypełnianie przestrzeni między losowymi liniami 2D

23

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.

wprowadź opis zdjęcia tutaj


Aktualizacja 1: Mogliśmy zarządzać rozwiązaniem dla pierwszego przypadku:
wprowadź opis zdjęcia tutaj
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.
wprowadź opis zdjęcia tutaj
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.

Deweloper
źródło
3
@RK - Nie zgadzam się. Już wyraźnie stwierdził, czego szukają. Oczywiście istnieje wiele możliwych rozwiązań, ale nic nie stoi na przeszkodzie, aby wszystkie były przydatne i zagłosowały.
GIS-Jonathan
1
Ponieważ jest to pytanie algorytmowe, które może być dość trudne z matematyki, możesz spróbować - math.stackexchange.com
GIS-Jonathan
1
Ściśle powiązane: gis.stackexchange.com/questions/27303 . Niniejsze pytanie, jak zauważa @RK, nie ma jednoznacznej odpowiedzi, ponieważ nie jest wystarczająco dobrze postawione. Ile prostokątów jest dozwolonych? Co to znaczy „maksymalizować rozmiar”? Zauważ też, że nie jest to problem „losowego układania płytek”: linie jedynie określają, poprzez ich uzupełnienie, obszary, które można zająć; rozwiązania z pewnością nie będą losowe. Należy również pamiętać, że łatwe uproszczenie jest natychmiast dostępne: problem można rozwiązać osobno w ramach każdego elementu dopełniacza.
whuber
1
@whuber: Cóż, jedną z aplikacji, którymi jesteśmy zainteresowani, jest ustalenie rozmieszczenia nienaruszonych nienaruszonych bloków „skalnych” w mocno spękanej „kopalni”. Wydaje nam się, że GIS wydaje się obiecujący dla tego problemu. Dodaliśmy to również do pytania. Sądzimy, że społeczność GIS może skorzystać z pomysłu na związane z nimi inne szczególne problemy. W każdym razie, to zależy od ciebie, jeśli ją migrujesz;)
Deweloper
4
Jak sugeruje @whuber, to nie jest tak naprawdę pytanie GIS (choć nie obrażam się, że tutaj jest zadawane.) Będziesz miał dużo szczęścia, otrzymując odpowiedź na forum dotyczącym geometrii obliczeniowej lub optymalizacji.
Llaves

Odpowiedzi:

2

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 ...

  1. Użyj „BoundingBoxReplacer” na obszarze zainteresowania.
  2. Przerzuć go do lokalnego układu współrzędnych (na później, gdy będziesz musiał „kafelkować” stopy / metry).
  3. Buforuj linie za pomocą transformatora „Bufferer”. Potrzebujesz tylko dowolnego rozmiaru, powiedzmy 0,01 stopy / metry. To, czego szukamy tutaj, to wielokąt linii dla następnego kroku.
  4. Dodaj transformator „Tiler”. Określ duży (szacowany lub inny) rozmiar kafelka w stopach lub metrach. To, co tu robimy, to układanie interesującego obszaru w kwadratowe bloki. W zależności od zestawu danych zacznij od dużych, aby naprawdę uzyskać duże wartości odstające.
  5. Dodaj transformator „Clipper”. To, co tutaj robimy, polega zasadniczo na podzieleniu zestawu danych, aby zobaczyć, które kafelki są dobre / złe. Na wyjściu płytki, które znajdują się w środku, są za duże. Jednak płytki „Zewnętrzne” są wystarczająco duże i gotowe do cięcia ...
  6. Tutaj jest skomplikowane, ale nie trudne ... Zamierzamy zapętlić transformator, aby ponownie użyć oryginalnego BoundingBox, ale wyciąć obszary, które są już gotowe do cięcia. Tak więc dodaj maszynkę i poprowadź Maszynę jako płytki wyjściowe na wcześniejszym wyjściu Maszynki. Teraz mamy jeden wielokąt, który jest gotowy do pracy.
  7. Użyj ponownie glazury, tym razem określając mniejszy kafelek. Na przykład, jeśli wcześniej użyłeś płytek o długości 100 metrów, wypróbuj 90 metrów.
  8. Dodaj kolejny obcinacz, przy czym obcinacz wejściowy to buforowane linie, a obcinacz wejściowy to mniejsze płytki jako wejście.

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.

Przykład płytki FME

Matthew Brucker
źródło