W jaki sposób różne systemy GIS determinują wnętrze wielokąta?

11

Interesuje mnie zrozumienie, w jaki sposób systemy GIS i ich dane kodują wielokąty.

W szczególności, w jaki sposób rozwiązują niejednoznaczność wnętrza wielokąta na kuli?

Tło: w 2D wybranie strony granicy, która ma skończony obszar, jest banalne, ponieważ płaszczyzna 2D jest nieskończona. Jednak kula jest skończona, więc nie można wiedzieć, która strona jest w środku, bez poczynienia dodatkowych założeń.

Możliwe znane mi podejścia:

  1. Reguła po prawej : granice zewnętrzne są zawsze określone w kolejności zgodnej z ruchem wskazówek zegara, a otwory są określone w kolejności przeciwnej do ruchu wskazówek zegara. (Oczywiście jest też reguła po lewej stronie).
  2. Najmniejszy obszar : dla każdego pierścienia zawsze wybieraj stronę o najmniejszym obszarze. Nie jestem pewien, jak określiłbyś wielokąt o dużym zasięgu: być może pusty pierścień zewnętrzny z dziurami?
  3. Prostokątny : Po prostu rozważ rzut prostokątny na nieskończonej płaszczyźnie 2D. Zakłada się jednak, że funkcje są posiekane na antemerydynie, w przeciwnym razie wymagana byłaby awaria jednej z dwóch powyższych metod.

Moje osobiste preferencje to pierwsze podejście, ale interesuje mnie, czy jest to powszechne w standardowych systemach GIS.

Jason Davies
źródło

Odpowiedzi:

3

Główne systemy GIS i ich metody rozwiązywania wrodzonej dwuznaczności:

  • ESRI : zasada prawej stopy.
  • ArcGIS : zasada prawej stopy.
  • SQL Server 2012 : reguła lewej stopy. Przed SQL Server 2012 wielokąty większe niż półkula zgłaszały błąd.

GeoJSON nie określa kolejności.

Jason Davies
źródło
1
Zmieniona specyfikacja GeoJSON ( tools.ietf.org/html/rfc7946 ) określa, że ​​„Pierścienie wielokątów MUSZĄ być zgodne z prawą zasadą orientacji (pierścienie zewnętrzne przeciwnie do ruchu wskazówek zegara, pierścienie wewnętrzne zgodnie z ruchem wskazówek zegara)”.
perrygeo,
1

Jeśli dobrze rozumiem twoje pytanie, chcesz wiedzieć, jak GIS wykonuje punkt w teście wielokąta kulistego. Oto algorytm, który znalazłem na geospatialmethods.org :

  1. Połącz punkt ze znanym punktem zewnętrznym za pomocą wielkiego łuku koła.
  2. Dla każdego łuku wielkiego koła, który jest bokiem sferycznego testu wielokąta, jeśli przecina on łuk zbudowany w kroku # 1 i policzy liczbę przecięć.
  3. Jeśli całkowita liczba przecięć jest nieparzysta, dany punkt znajduje się wewnątrz sferycznego wielokąta. jeśli łączna liczba przecięć jest równa, punkt znajduje się poza sferycznym wielokątem.

Wydaje mi się, że nadal opiera się on na algorytmie planarnym konstruowania promienia testowego od punktu, o którym mowa, do punktu, o którym wiadomo, że znajduje się poza wielokątem, a następnie zliczania, o ile krawędzi wspomnianego promienia krzyżuje się promień.

Jest również szczegółowo omówione w artykule NASA JPL na temat algorytmów wielokątów na kuli . Jest na stronie 11. Istnieją oczywiście pewne optymalizacje:

Po pierwsze, unikaj wykonywania kosztownych obliczeniowo sferycznych obliczeń trygonometrii, gdy jest to możliwe, sprawdzając promień testowy względem wstępnie obliczonej ramki granicznej przed spojrzeniem na krawędzie wielokąta. Jeśli promień testowy przecina obwiednię, Q jest sprawdzane względem każdego z wierzchołków wielokąta. Nie ma sensu sprawdzać, czy Q znajduje się w tym momencie na krawędzi, ponieważ zostanie to ujawnione, gdy zostaną przeprowadzone testy przecięcia, a resztę krawędzi można w tym czasie pominąć.

Myślę, że papier będzie dla ciebie najciekawszy :)

RK
źródło
To wydaje się odpowiadać na inne pytanie. Nie przecinająca się, zamknięta polilinia dzieli sferę na dwa połączone elementy. PO zastanawia się, w jaki sposób GIS określa - lub jak się mówi - który z tych elementów należy uważać za „wewnątrz”, a który „na zewnątrz”? Przytoczona strona internetowa omawia ten problem pod nagłówkiem „Zgadnij punkt zewnętrzny”, podkreślając, że zgaduje tylko, który element ma być w środku.
whuber
Och ... drań. Nie zrozumiałem jego pytania. Połączyłem go ze sferyczną wersją punktu w teście wielokąta. Zmienię to, jak tylko znajdę odpowiedź.
RK
Doceniam znalezione przez Ciebie referencje, więc mam nadzieję, że uda Ci się je uwzględnić w poprawionej odpowiedzi :-).
whuber
Też mam nadzieję. A może po prostu zadam pytanie i sam na nie odpowiem ;-) Szkoda byłoby je zmarnować.
RK
1
Dzięki za szczegółową odpowiedź! Niestety, jak wskazuje @whuber, to nie odpowiada na moje konkretne pytanie. :) Naszkicowałem możliwe podejścia, aby rozwiązać wewnętrzną niejednoznaczność tego, gdzie znajduje się wnętrze wielokąta, ale interesuje mnie wiedza na temat tego, jakie podejście przyjmuje rzeczywiste oprogramowanie GIS.
Jason Davies