2010-06-18 21 views
7

Jak określić, czy punkt znajduje się wewnątrz, czy na zewnątrz wieloboku, który leży na powierzchni Ziemi?Czy punkt wewnątrz lub na zewnątrz wieloboku, który znajduje się na powierzchni kuli ziemskiej?

Wnętrze wieloboku można określić za pomocą reguły prawej ręki, tj. wewnątrz wielokąta znajduje się po prawej stronie, gdy chodzisz po wielokącie.

wielokątne może

  1. kołowy albo słup
  2. Cross 180 Długość
  3. obejmować więcej niż 50% w świecie

Jako świecie jest kulą normalny przejście promień Algorytmy nie działają poprawnie.

+0

Twoje pytanie nie jest bardzo jasne: wielokąty nie może być zakrzywiona (z definicji), więc jesteś zamiast pytać, jak ustalić czy punkt znajduje się na powierzchni kuli? To naprawdę proste: jest na powierzchni, jeśli odległość do środka kuli == promień kuli. –

+1

Wierzę, że ma na myśli, że jeśli wykonasz serię punktów na kuli i skonstruujesz zamknięty kształt między nimi. Lepsze punkty dotyczące łączenia punktów wielokątów w krawędzie wydają się niejednoznaczne (można je połączyć bezpośrednio, a następnie rzutować na kulę, może?) – Akusete

+0

prawda, wielokąt w moim świecie to seria punktów na kuli i konstruuję zamknięty kształt między nimi – richard

Odpowiedz

2

W rzeczywistości normalne podejście do śledzenia i nawijania promieni działa dobrze na powierzchni kuli, z niewielką regulacją.

Na powierzchni kuli "linia prosta" to wielkie koło, a odległości są mierzone w jednostkach kątowych, a nie w metrach lub calach. Aby narysować promień z dowolnego punktu na powierzchni kuli, po prostu uformuj wielki okrąg przez ten arbitralny punkt i dowolny inny punkt na powierzchni kuli. Aby zachować czystość matematyczną, wybierz drugi punkt o wartości pi/2 od miejsca, którego testujesz. Zastosuj zwykłą regułę parzystą-nieparzystą do wielkiego koła i wielokąta testowego.

Zasada zwijania przekłada się również bezpośrednio z linii prostych w płaszczyźnie na (segmenty) wielkich okręgów na kuli.

Wszystko, czego potrzebujesz teraz, to implementacje Java podstawowych operacji geometrii sferycznej. Nie mam żadnych zaleceń na ten temat, ale myślę, że Internet pomoże. Na matematykę zacznij od Mathworld.

Innym podejściem byłoby rzutowanie punktów i wielokątów z powierzchni kuli na płaszczyznę - jak to przewidują mapy - na topologiczny związek niewinności nie będzie miała wpływu taka transformacja.

Aha, i musisz zdecydować, co zrobić, jeśli wielokąt opisuje wielki krąg

+1

Nie musisz niczego decydować, jeśli twój wielokąt opisuje wielkie koło. Nadal istnieje wnętrze i fasada. –

2

Użyj płaszczyzn zamiast promieni. "Linia" na powierzchni sfery zdefiniowanej przez dwa punkty jest łukiem wielkiego koła (koła, którego środek jest środkiem kuli) i jest również zawarta w płaszczyźnie zawierającej te dwa punkty i środek kuli .

Sprawdź, czy punkt jest "większy" lub "mniejszy" od odpowiedniej płaszczyzny dla każdej krawędzi "wieloboku", aby określić, po której stronie "linii" jest ona włączona.

+0

Dzięki, rozumiem podstawową teorię. Czy wiesz o api Java, które to robi? Albo gdzieś mogę znaleźć algorytm? – richard

+1

NASA dostarcza pakiet SDK Java o otwartym kodzie źródłowym o nazwie WorldWind do zastosowań geoprzestrzennych. Może to być przesada w stosunku do potrzeb, ale może dostarczyć więcej pomysłów na aplikację. http://worldwind.arc.nasa.gov/java/ – Tansir1

+0

Rozwiązałbym to jak problem z matematyką. Znajdź formułę dla samolotu z trzech punktów na płaszczyźnie, podłącz swój punkt do formuły i zobacz, po której stronie płaszczyzny jest on włączony. Pójdź, spłucz, powtórz. Użyłbym raczej współrzędnych xyz niż cylindrycznych/sferycznych układów współrzędnych, tylko dlatego, że samoloty są w ten sposób prostsze. Ponieważ nie jestem zaznajomiony z twoim algorytmem przecinania promieni, nie wiem, jak dostosować to podejście, ale podejrzewam, że jest to wykonalne. – Slartibartfast