Alternatywne metody indeksowania dla operacji na punktach

17

Często stosuje się indeks przestrzenny obwiedni, aby poprawić wydajność podczas pracy z dużą liczbą funkcji. W przypadku wykonywania operacji na poszczególnych geometriach z dużą liczbą wierzchołków istnieją podobne strategie optymalizacji?

Na przykład, czy istnieją jakieś struktury danych, które mogą przyspieszyć punkt w operacjach wielokąta lub unii?

algorithm optimization indexing Matthew Snape
źródło
1
Pod maską GIS wykorzystują wiele wyspecjalizowanych struktur danych, w tym różne formy czworokątów, DCEL itp., Które są opisane w podręcznikach geometrii obliczeniowej. Pytasz o te szczegóły implementacji lub pytasz o metody, które mogą być stosowane przez użytkowników w językach skryptowych?
whuber
Dzięki, myślę, że muszę przeczytać podręczniki. Istotą mojego pytania było, w jaki sposób te struktury danych mogą być wcześniej obliczone z wyprzedzeniem. Czy istnieją jakieś wstępnie obliczone implementacje?
Matthew Snape
Matthew, to świetne pytanie. Prawdziwie zorientowany na wydajność GIS oferowałby użytkownikom opcje wstępnego obliczania struktur danych do wielokrotnego zastosowania. Na obecnym etapie oprogramowanie reklamujące się jako „GIS” zwykle oferuje takie wstępne obliczenia jedynie w postaci „indeksów przestrzennych”, podczas gdy bardziej ogólne oprogramowanie, które może również przeprowadzać analizy GIS, takie jak Mathematica (lub w pewnym stopniu R) zaoferuje użytkownikowi znacznie większa kontrola nad takimi rzeczami.
whuber
Myślę, że problem opiera się na „fraktalnej naturze” obiektów 2d oraz na niepewnej i niezrównoważonej gęstości informacji o rozkładzie.
huckfinn

Odpowiedzi:

2

OK tylko dla punktu w wielokącie:

Myślę, że problem opiera się na „fraktalnej naturze” obiektów 2d oraz niepewnym i niezrównoważonym rozkładzie informacji przestrzennej. Jeśli masz regularną siatkę, łatwo jest obliczyć pozycję lub relację komórki. Ale izolina modelu terenu może mieć po bokach nieskomplikowane części, a po drugiej skomplikowane matematycznie (części aktywne morfologicznie, np. Grzbiety, doliny ...).

Indeksowanie próbuje obsłużyć dwie rzeczy:

  1. Szybka rutyna, która daje zestaw wiader, w których zbierasz przedmioty, które możesz przestrzennie odróżnić (wiadra!). A BBoxy są łatwe do obliczenia i obsługi.

  2. Zestaw relacji (nakładanie się, dotyk) w celu rozróżnienia lub powiązania rzeczy przestrzennych (obiektów).

Niestety, BBoxy nie dadzą ci pojęcia, ile punktów jest w każdym BBoxie, jak kształtują się obiekty (dziury, wypukłe, ...) i jak lokalnie rozmieszczone są informacje (90% punktów w lewym górnym rogu BBox). Możesz więc znaleźć członków szybkiej operacji na poziomie obiektu i stracić wiele czasu w budowaniu relacji testu.

Aby zastosować bardziej nieregularne podejście, triangulacja IMO w połączeniu z i quadtrees jest jedną ze strategii, w których można zbliżyć segmentowanie i część budującą relację do indeksu (segment == budowanie relacji).

W przypadku testu Point-in-Polygon-Test możliwe jest zbudowanie nieregularnej pamięci podręcznej przy użyciu:

  1. ! ograniczył triangulację delaunay twojej osłony, z dodatkowymi punktami siatki granicznej do wykrywania poza osłoną
  2. umieść to w schemacie indeksowania poczwórnego z nie więcej niż N trójkątami na pudełko (segmenty fraktalne)
  3. znajdź zestaw trójkątów, do którego należy punkt - liść w kwadracie
  4. znajdź trójkąt, w którym leży punkt (część testowa powyżej maks. N trójkątów)
  5. i poproś o identyfikatory wielokątów wierzchołków trójkąta
  6. jeśli identyfikator jest unikalny, punkt należy do wielokąta, jeśli nie, to jest na zewnątrz

Koszt budowy puszki i czworoboków jest bardzo wysoki i trudny do obliczenia, a czworobok musi równoważyć duże i małe trójkąty (trójkąty, które nie zmieszczą się w mniejszych polach poddrzewa).

Niektóre narzędzia i linki:

Trójkąt - Ograniczenie triangulacji wielokąta

Czwórki - z przykładami źródeł

Repozytorium Stony Brook - Struktury danych i geometria rozproszona

huckfinn
źródło