Jak znaleźć najdalszy punkt z zestawu istniejących punktów?

17

Mam zestaw punktów jako plik kształtu i chcę znaleźć (współrzędne) nowego punktu, który będzie miał możliwie największą odległość od każdego z istniejących punktów. Czy to jest możliwe? Jeśli tak, czy jest jakiś przykładowy kod VB? Dzięki Demetris

arcgis-10.0 arcobjects vba vb.net Demetris
źródło
Czy masz na myśli, że chcesz nowego punktu dla każdego już istniejącego punktu lub jednego punktu, który jest w jakiś sposób „najdalszy” od nich wszystkich? A najdalej, czy masz na myśli „drugą stronę globu”? Jeśli tak, możesz po prostu pomnożyć szerokość geograficzną przez -1 i dodać 180 do długości geograficznej (odejmując 360, jeśli wartość wynikowa wynosi> 180), jeśli masz je w stopniach dziesiętnych.
nmpeterson
Myślę, że interesujące byłoby pytanie: biorąc pod uwagę istniejące punkty rozproszone po całym świecie, znajdź nowy punkt na kuli ziemskiej najdalej od wszystkich istniejących punktów.
Kirk Kuykendall
Byłby to faktycznie punkt na końcu trójkąta równoramiennego, w którym odległość jest ograniczona tylko tym, jak daleko chcesz się posunąć. Jeśli dobrze przeczytałem pytanie, chcesz uzyskać punkt najdalej od nich obu? Na równi?
Hairy
1
Och, mój post stworzył fantastyczną dyskusję i materiał! NMpeterson: Po pierwsze, muszę powiedzieć, że moje punkty znajdują się na niewielkim płaskim obszarze; więc nie ma potrzeby obliczania globu. Szukam drugiego podniesionego problemu; jeden punkt, który jest jakoś „najdalej” od wszystkich istniejących punktów. Skoncentruj się na tym.
Demetris
Zastanawiam się, czy jakikolwiek przykładowy kod VB jest dostępny zgodnie z pierwotnym pytaniem. Być może taki kod jest już oczywisty, biorąc pod uwagę odpowiedzi ekspertów. Ale jako początkujący mam nadzieję zacząć od odtworzenia rozwiązania dostarczonego przez Whuber. Z góry przepraszam za podanie tego jako odpowiedzi zamiast komentarza.

Odpowiedzi:

12

Zalecenie Kirka Kuykendalla dotyczące skonstruowania sferycznego diagramu Voronoi (wielokąty Thiessena) jest dobre, ale może wymagać pewnych technicznych problemów. W międzyczasie można alternatywnie zastosować standardowe rozwiązanie rastrowe, jak opisano w innym wątku . Użyj odległości sferycznych zamiast odległości euklidesowych.

Oto przykład wykorzystujący pięć punktów, podany jako (lat, lon):

 82.7051   -145.256
 60.3321     81.2881
-17.076     105.125
-38.792    -122.686
  0.000     180.000

Mapa odległości

Ta sferyczna mapa odległości obejmuje glob od -180 do 180 stopni długości w poziomie i od -90 do 90 stopni w pionie. Punkty są pokazane dużymi czerwonymi kropkami. Odległości rosną wraz z jasnością. Widoczne grzbiety muszą być fragmentami wielkich kręgów. Mała czarna kropka w pobliżu (-15,268, -2,04352) oznacza punkt maksymalnej odległości 11 227 km. (Odległości obliczono w elipsoidalnym układzie odniesienia ITRF00).

Rozdzielczość tej siatki wynosi jeden stopień. Aby uzyskać bardziej precyzyjne rozwiązanie, można powiększyć taki punkt (i dowolne inne maksimum lokalne o wystarczająco zbliżonej wartości do maksimum globalnego) i powtórzyć obliczenia na siatce o mniejszej, ale wyższej rozdzielczości.

Whuber
źródło
o wiele ładniejszy niż wektory. Nie jestem pewien, dlaczego myślałem, że rastry wymagają modelu płaskiej ziemi.
Kirk Kuykendall
Dość, tak, ale nieefektywnie. Byłoby miło, gdyby działało oparte na wektorze sferyczne rozwiązanie Voronoi.
whuber
@ Whuber: Jak można automatycznie uzyskać współrzędne czarnego punktu? ”
Demetris,
@Demetris Jednym ze sposobów jest obliczenie maksymalnej wartości na siatce, wybranie wszystkich komórek równych tej wartości i użycie współrzędnych środka tej komórki.
whuber
@ Whuber: Wielkie dzięki. To jest dobry pomysł. Jednak muszę przyciąć wyjściowy raster na podstawie klasy obiektów (wielokąta unikatowego). Mogę to zrobić?
Demetris,
8

wprowadź opis zdjęcia tutaj

Nigdy tego nie próbowałem, ale wygląda na to, że to zadziała:

Stwórz trójwymiarowy schemat kuli. Powstałe wielokąty zostaną z grubsza wyśrodkowane na oryginalnych istniejących punktach (nasionach).

Pętlę przez każdy wynikowy wierzchołek, aby znaleźć ten, który jest najdalej od najbliższego istniejącego punktu. Ten punkt powinien być najbardziej odległym punktem na świecie.

Kirk Kuykendall
źródło
To świetny pomysł (+1). Ale jak wygląda kulisty schemat Voronoi, gdy wszystkie punkty leżą na wspólnej półkuli? Kod, do którego się odwołujesz, otrzymuje go z wypukłym kadłubem, ale wygląda na to, że nie zadziała.
whuber
hmm, tak, myślę, że nawet jeśli nie wszystkie są na wspólnej półkuli, będzie jeden wielokąt, który nie ma punktu początkowego. Co się stanie, jeśli skonstruujesz dla niego punkt za pomocą antypodalnego punktu centroidu wypukłych kadłubów? Następnie, oprócz zapętlenia przez każdy wierzchołek, ten wypukły punkt antypody zostałby zbadany, aby sprawdzić, czy znajduje się dalej od swoich sąsiadów niż maksymalna odległość wierzchołka.
Kirk Kuykendall
Tak myślałem początkowo, ale punkty antypodalne stworzą sztuczne wielokąty. Pomyśl na przykład, co by się stało na twojej ilustracji, gdyby uwzględniono antypoda do każdego punktu! Prawdopodobnie istnieje rozwiązanie tego rodzaju, ale wydaje się, że nie jest to proste.
whuber
1

Możesz użyć funkcji odległości ważonej kosztem, aby określić, jak daleko jest każda komórka w twoim rastrze od wszystkich innych punktów.

djq
źródło
Jakiego kosztu byś użył?
whuber
Jeśli ustawisz koszt na jedną jednostkę; możesz określić, jaki byłby najdalszy punkt na podstawie odległości.
djq
@whuber Chociaż być może nie jest to inne niż obliczanie wspomnianego już podejścia do odległości euklidesowej.
djq
To odległość euklidesowa. W rzeczywistości to nie wszystko: to dziwny rodzaj ośmiokątnej odległości (koła są w rzeczywistości ośmiokątami). W tej sytuacji (odległości tylko od punktów, bez barier) obliczanie odległości euklidesowej lub sferycznej siatki odległości jest znacznie dokładniejsze i znacznie szybsze, zamiast próbować do tego wykorzystać CostDistance.
whuber
Nie jestem pewien, czy ważona kosztem funkcja odległości pomogłaby, ponieważ potrzebuję współrzędnych tylko jednego punktu i mam ekscytujący wektorowy zestaw punktów, ale spróbuję. Dzięki.
Demetris
1

O ile mi wiadomo, tę analizę „ Polaka niedostępności ” należy wykonać iteracyjnie.

Iteracyjne podejście rastrowe byłoby odpowiednie, jeśli patrzysz na mały obszar z minimalnymi zniekształceniami wynikającymi z projekcji. Dla każdej komórki obliczyć odległość do wszystkich punktów, a następnie przyjąć minimalną odległość. Komórka o najwyższej wartości jest biegunem. Aby to zrobić, możesz również użyć odległości euklidesowej w programie Analityka przestrzennego.

Iteracyjne podejście wektorowe jest bardziej skomplikowane. Garcia-Castellanos i in. 2007 opisują metodę iteracyjną opartą na kulistej ziemi. Wygląda na to, że udostępnili swój kod C online . Mogę sobie wyobrazić, jak to zrobić w Arc za pomocą buforów, ale nadal byłoby to iteracyjne i powolne.

dmahr
źródło
0

możesz użyć Odległość punktu (Analiza) Narzędzie tworzy tabelę z odległościami między dwoma zestawami punktów. jeśli używany jest domyślny promień wyszukiwania, obliczane są odległości od wszystkich punktów wejściowych do wszystkich punktów w pobliżu. Tabela wyjściowa może być dość duża. Na przykład, jeśli obie funkcje wejściowe i bliskie mają 1000 punktów każda, wówczas tabela wyjściowa może zawierać milion rekordów.

salehamra
źródło
Jak można to zastosować do znalezienia współrzędnych nowego punktu, który nie pojawia się na wejściu? Być może źle odczytałeś pytanie?
whuber
0

Najdalszy punkt w twoim zestawie punktów byłby odwrotny do najbardziej wewnętrznego punktu w twoim zestawie. Na przykład, jeśli twój najbardziej wewnętrzny punkt w twoim zestawie miał współrzędne 49 stopni na północ i -144 stopni na wschód, wtedy punkt odwrotny i najdalszy miałby współrzędne 49 stopni na południe i 36 stopni na zachód. Nie jest to do końca prawdą, ponieważ Ziemia nie jest idealnie kulista, a raczej geoidalna; dlatego poprawność punktu wynikowego zależy w dużej mierze od tego, jakiego systemu rzutowania i geograficznego (ortograficznego, ortorektalizowanego ...) używasz. Pomocne może być znalezienie odwrotności dla całego zestawu (przesłanie antypodu dla zestawu), a następnie przeprowadzenie analizy powierzchni w terenie objętym zestawem punktów antypodu, ponieważ teren może być bardzo duży. Zakładam, że twoje pytanie nie dotyczy żadnych punktów na ciałach pozaziemskich, takich jak inne planety lub księżyce. Przepraszam, Nie mam dla ciebie kodu VB. 🙄

Jurij Szewczuk
źródło
Punkt znajdujący się najdalej od wszystkich innych punktów w zestawie byłby najbardziej wewnętrzny (taki, który jest najdalej od wszystkich najbardziej zewnętrznych punktów wzdłuż krawędzi), i nadal byłby najbliżej każdego punktu bezpośrednio obok niego, niezależnie od tego. To analiza skupień, a nie zabawa. Prawdopodobnie lepiej jest przyjrzeć się tym samym atomom ładunku w fizyce. ”
Jurij Szewczuk