Algorytm do obliczania zasięgu + nakładania się z zestawu łuków

10

Mam plik kształtu zawierający łuki przedstawiające ścieżkę, którą przejechała ciężarówka rozrzucająca nawóz na farmę.

Powiedzmy, że wiem, że szerokość rozrzutu wynosi 30 m, tzn. Ciężarówka może rozrzucać nawóz 15 m po obu stronach pojazdu.

Chcę wygenerować zestaw wielokątów, które pokazują:
1) Całkowity obszar, który otrzymał nawóz
2) Obszary zachodzenia na siebie, tj. W których dwa oddzielne przejścia były zbyt blisko siebie, tak że niektóre części gospodarstwa otrzymały podwójną prawidłową „dawkę” „nawozu.

Naiwnym podejściem jest po prostu tworzenie wielokątów zasięgu jako buforów wokół łuków. Działa to w szczególnym przypadku, w którym linie rozłożenia różnią się od siebie. Jednak ciężarówka mogłaby poruszać się wokół farmy w coraz mniejszej spirali, a prosty bufor nie pokazywałby nakładania się, w którym dwa przejścia spirali były zbyt blisko siebie (jeśli spirala jest pojedynczym łukiem, skończyłbym pojedynczy wielokąt bez nakładających się części).

Jeśli jest to istotne, używam TatukGIS VCL DK, ale naprawdę szukam algorytmu, a nie konkretnego rozwiązania.

Kilka wyjaśnień w odpowiedzi na dotychczasową dyskusję:

1) Nie mogę polegać na danych wektorowych posiadających określone metadane (np. Dzienniki GPS lub szybkość rozsiewu). Pozwalam użytkownikowi wybrać warstwę i określić szerokość rozkładania, a następnie uruchamia się raport.

2) Celem raportu jest naprawdę pokazanie użytkownikowi, jak „wykwalifikowany” był operator pojazdu, gdzie „wykwalifikowany” oznacza „osiągnął najwyższy zasięg przy najmniejszym nakładaniu się”.

3) Czuję się bardziej swobodnie na ziemi wektorowej niż na ziemi rastrowej, więc wolę rozwiązania oparte na wektorach.

Dzięki,

Darren.

dbruning
źródło
1
Zastanawiam się, czy byłoby to podobne do metod przewidujących skumulowane opady w oparciu o prognozowane ścieżki sztormowe.
Kirk Kuykendall

Odpowiedzi:

3

Być może najprostszym rozwiązaniem jest rozbicie pojedynczej geometrii na segmenty i buforowanie tych pojedynczych segmentów: w przypadku spirali buforujesz każdy łuk, a następnie przecinasz poszczególne łuki, aby uzyskać liczbę. Uważaj, aby uniknąć fałszywego nakładania się, nie buforując końców segmentów, tylko po lewej i prawej stronie samych segmentów.

Innym podejściem jest nałożenie siatki wielokątów na dane, a następnie w obrębie każdej komórki siatki buforowanie każdego przecinającego się segmentu linii osobno. Aby być dokładnym, chcesz wziąć komórkę siatki do analizy, buforować ją, a następnie zebrać przecinające się segmenty i buforować je, wykonując analizę w oryginalnym oknie komórki.

Każda z tych opcji powinna dać rozsądne oszacowanie nakładania się. Mogę wymyślić kilka bardziej dokładnych podejść, ale wymagałyby one wiedzy na temat danych.

scw
źródło
Dzięki. Myślałem zgodnie z twoją pierwszą sugestią - rozbicie geometrii na segmenty i buforowanie ich. Myślę, że będę musiał także buforować końce segmentów, aby uzyskać zaokrąglone krawędzie w rogach. Myśląc o przypadku, w którym zaczynam od linii prostopadłej - jeśli nie buforuję końców, skończę z dwoma nakładającymi się prostokątami z brakującym kwadratem na zewnątrz narożnika (trudny do wyrażenia jako tekst!)
dbruning
Myślę, że będę musiał także buforować końce segmentów, aby uzyskać zaokrąglone krawędzie w rogach. Myślałem dalej o przecięciu bufora dla każdego segmentu z buforem dla poprzedniego segmentu, a następnie zgromadzeniu tylko „nowych” części każdego bufora w buforze głównym. Pomysł polega na ignorowaniu nakładania się na poprzedni segment, ale odbiór nakłada się na starsze segmenty.
dbruning
2

Brak rozwiązania, ale niektóre dane wejściowe:

Problem ten wydaje się podobny do problemu wykrywania koalescencji linii w generalizacji mapy . Dzieje się tak, gdy duży styl jest nakładany na falistą linię (symbol nakłada się na siebie):

wprowadź opis zdjęcia tutaj

Ten dokument s. 176–180 (w języku francuskim… przepraszam) podaje algorytmy do wykrywania takich samo-przecinających się części. Zasada jest taka, jak zaproponowano przez scw , aby użyć pojedynczego bufora bocznego każdego segmentu złożonego z segmentu plus 0, 1 lub 2 łuki kół. JTS zawiera implementację tego bufora po jednej stronie, która może być użyteczna.

Julien
źródło
Dlaczego martwisz się wykrywaniem skrzyżowań? A dlaczego proponujesz bufory „jednostronne”? Żaden z tych problemów nie wydaje się być istotny.
whuber
Ma to na celu wykrycie, gdzie ciężarówka rozrzuca nawóz kilkakrotnie, czyli tam, gdzie obszar rozsiewu krzyżuje się.
Julien
2

W rozwiązaniu wektorowym ominie się potencjalnie krytyczną zmienną : czas, a przez to szybkość rozprzestrzeniania się. Gdy ciągnik porusza się szybciej, mniej nawozu jest rozrzucane na jednostkę powierzchni, a gdy porusza się wolniej (zwalniając w zakręt i przyspieszając o jeden), rozprowadza więcej nawozu na jednostkę powierzchni. Ponadto, jeśli ciągnik rozrzuca materiał podczas skrętu, materiał będzie bardziej skoncentrowany w kierunku wnętrza zakrętu, a mniej skoncentrowany w kierunku na zewnątrz.

Dane czasowe byłyby dostępne w zapisie GPS postępu ciągnika. Nachylenia (przebyta odległość podzielona przez upływ czasu) oszacują prędkości w każdym punkcie. Alternatywnie można (jako przybliżenie) założyć stałą prędkość wewnątrz pola i wolniejszą prędkość w rozsądnym buforze wewnętrznym granicy pola.

Reprezentacja rastrowa poradzi sobie z tymi problemami. Rasteryzuj ścieżkę ciągnika. Spowoduje to ustawienie wszystkich komórek nieprzecinanych przez ciągnik na wartości NoData (lub na zero). Gdyby ciągnik poruszał się ze standardową, stałą prędkością, wystarczyłoby wprowadzić stałą wartość do każdej z komórek danych. Teraz, na przykład, jeśli ciągnik poruszałby się z dwukrotnie większą prędkością, (przypuszczalnie) jego szybkość stosowania byłaby o połowę mniejsza, a można to przedstawić poprzez zmniejszenie o połowę wartości w komórkach.

Zasadniczo wartością do umieszczenia w dowolnej komórce jest dawka aplikacji na jednostkę powierzchni . Jeśli ciągnik równomiernie rozrzuca x kg nawozu na sekundę do 15 mz każdej strony podczas jazdy z prędkością y m / s, wówczas rozrzuca x / y kg / s / [m / s] / (2 * 15 m) = x / (30 lat ) Kg / m ^ 2 nawozu. Zatem x / (30 lat ) to wartość, którą należy wprowadzić do każdej komórki. podano x, ay obliczono na podstawie danych GPS.

Samo-skrzyżowania zasadniczo nie stanowią problemu . Jeśli ścieżka ciągnika przecina się sama, dodawaj wkłady za każdym razem, gdy przekręca komórkę. W tym celu może to wymagać specjalnego przetwarzania, w zależności od sposobu tworzenia siatki i możliwości oprogramowania GIS.

Po wykonaniu tego przygotowania reszta jest szybka i łatwa: ogniskowa suma tej siatki, przy użyciu okrągłego sąsiedztwa o promieniu 15 m, znajduje skumulowaną ilość rozproszoną na jednostkę powierzchni w każdej komórce.

Whuber
źródło
1
+1 wydaje się, że gdybyś miał narzędzie, które pozwalało jądrze (reprezentującemu traktor) poruszać się wzdłuż ścieżki (zamiast wzdłuż każdego rzędu), ten problem byłby łatwiejszy do opanowania.
Kirk Kuykendall
@Kirk Nie ma potrzeby podążania ścieżką, wierszami lub czymkolwiek innym z jądrem. Ważne jest, aby docenić zmianę punktu widzenia, która towarzyszy sumie ogniskowej: zamiast patrzeć na problem jako na rozprzestrzenianie się materiału z ścieżki punktów, spójrz na to jak na obliczenie, ile materiału gromadzi się w każdym punkcie pola . Oczywiście to ten sam problem z tym samym rozwiązaniem. Podejście oparte na ruchomym jądrze (i proponowane podejścia buforujące) mają pierwszy punkt widzenia; suma ogniskowa, druga. Ale dostępne jest narzędzie sumy ogniskowej; obliczenia dotyczące ruchomego jądra nie są.
Whuber
Uważam, że przedstawione przez ciebie podejście rastrowe byłoby najlepszą metodą, gdybyśmy znali prędkość i szybkość rozsiewu. Niestety w tym konkretnym scenariuszu nie znamy żadnego. Nasz użytkownik końcowy może wybrać dowolną warstwę jako dane wejściowe do tego raportu pokrycia i nie możemy polegać na geometrii posiadającej określone metadane.
dbruning
@dbruning To podejście nie wymaga znanych prędkości / prędkości rozprzestrzeniania; pozwala tylko na nie (+ dokładniejszy model rzeczywistości), jeśli je masz. Będzie to jednak wymagało nieco progowania i zliczania komórek, aby uzyskać pożądane miary (całkowite pokrycie obszaru; obszar nakładania się) z systemu, a także pomieszane kompromisy w dokładności.
Dan S.
@bruning Jeśli nie znasz dawki rozsiewu, otrzymasz względną dawkę rozsiewu. Jeśli nie znasz prędkości, nadal wiesz (lub powinieneś wiedzieć), w jaki sposób ludzie prowadzą ciągniki i powinieneś być w stanie uzyskać rozsądne szacunki prędkości względnych. Zakładając stałe prędkości i stałe dawki rozsiewu, nadal otrzymasz rozsądne odpowiedzi; uzgodnią odpowiedzi oparte na buforze na prostych odcinkach tras ciągnika; i prawdopodobnie będą bardziej realistyczne w zakrzywionych częściach.
whuber
2

Nie jestem w 100% pewien co do protokołu StackExchange, więc zamieszczam to jako odpowiedź na moje pytanie. Tak czy inaczej to odpowiedź.

Podstawowym algorytmem jest:
1. Podziel dowolną geometrię na warstwie na segmenty nie dłuższe niż 1/2 szerokości rozrzutu.
2. Dla każdego segmentu:
- Utwórz „bufor toczny”, patrząc do tyłu wzdłuż kształtu i buforując wszystkie poprzednie segmenty, w których skumulowana długość tych segmentów jest mniejsza niż szerokość rozrzutu (promień zderzaka = 1/2 szerokości rozrzutu)
- Utwórz „bufor następnego segmentu” tylko następnego segmentu (promień bufora = 1/2 szerokości rozrzutu)
- odejmij „bufor toczny” od „bufora następnego segmentu”, aby uzyskać „nowy bufor”
- dołącz do wszystkich „nowego bufora” wielokąty razem, aby uzyskać pojedynczy wielokąt na kształt.

Zasadniczo pozwala to kierowcy pojazdu rozrzutnika wykonywać skręty pod kątem prostym (lub szerszym) bez kary nakładania się, ale jeśli zawrócą zbyt ostro, aby rozłożyć się na „starej ziemi”, zaczynamy nakładać się.

Nakłada się na niebiesko

Spirala wygląda tak, jak chcę:

spirala

dbruning
źródło