Wie finde ich den entferntesten Punkt aus einer Reihe vorhandener Punkte?

17

Ich habe eine Reihe von Punkten als Shapefile und ich möchte (die Koordinaten) eines neuen Punktes finden, der den größtmöglichen Abstand von jedem der vorhandenen Punkte hat. Ist das möglich? Wenn ja, gibt es ein Beispiel für einen VB-Code? Danke Demetris

arcgis-10.0 arcobjects vba vb.net Demetris
quelle
Meinen Sie, Sie möchten einen neuen Punkt für jeden bereits vorhandenen Punkt oder einen Punkt, der von allen irgendwie "am weitesten" entfernt ist? Und meinst du mit "die andere Seite der Welt" am weitesten? In diesem Fall können Sie den Breitengrad einfach mit -1 multiplizieren und den Längengrad um 180 erhöhen (abzüglich 360, wenn der resultierende Wert> 180 ist), wenn Sie sie in Dezimalgrad haben.
nmpeterson
Ich denke, die interessante Frage wäre: Finden Sie bei vorhandenen Punkten, die über den Globus verstreut sind, einen neuen Punkt auf dem Globus, der von allen vorhandenen Punkten am weitesten entfernt ist.
Kirk Kuykendall
Es wäre praktisch der Punkt am Ende eines gleichschenkligen Dreiecks, an dem die Entfernung nur durch die gewünschte Entfernung begrenzt ist. Wenn ich die Frage richtig gelesen habe, möchten Sie den Punkt, der von beiden am weitesten entfernt ist? Gleichermaßen?
Behaarte
1
Oh! Mein Beitrag hat eine fantastische Diskussion und Material erstellt! NMpeterson: Erstens muss ich sagen, dass meine Punkte in einem kleinen flachen Bereich liegen. Es sind also keine Globusberechnungen erforderlich. Ich suche nach der zweiten aufgeworfenen Frage; dh ein Punkt, der irgendwie "am weitesten" von allen vorhandenen Punkten entfernt ist. Konzentrieren Sie sich bitte darauf.
Demetris
Ich frage mich, ob ein Beispiel-VB-Code verfügbar ist, wie in der ursprünglichen Frage angefordert. Möglicherweise ist ein solcher Code angesichts der Antworten der Experten bereits offensichtlich. Aber als Anfänger hoffe ich, zunächst die freundlicherweise von whuber bereitgestellte Lösung neu zu erstellen. Ich entschuldige mich im Voraus dafür, dass ich dies als Antwort anstelle eines Kommentars ausspreche.

Antworten:

12

Kirk Kuykendalls Empfehlung, ein kugelförmiges Voronoi-Diagramm (Thiessen-Polygone) zu konstruieren, ist gut, könnte aber technische Probleme bereiten. In der Zwischenzeit kann alternativ die in einem anderen Thread beschriebene Standard-Raster-Lösung angewendet werden . Verwenden Sie sphärische Abstände anstelle von euklidischen Abständen.

Hier ist ein Beispiel mit fünf Punkten, hier angegeben als (lat, lon):

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

Entfernungskarte

Diese sphärische Entfernungskarte umspannt den Globus horizontal von -180 bis 180 Grad und vertikal von -90 bis 90 Grad. Die Punkte werden mit großen roten Punkten angezeigt. Die Abstände nehmen mit der Helligkeit zu. Die sichtbaren Grate müssen Teile großer Kreise sein. Der kleine schwarze Punkt bei (-15.3268, -2.04352) markiert den Punkt der maximalen Entfernung von 11.227 km. (Die Entfernungen wurden im ITRF00-Ellipsoid-Datum berechnet.)

Die Auflösung dieses Gitters beträgt ein Grad. Um eine genauere Lösung zu erhalten, können Sie in einen solchen Punkt zoomen (und in ein beliebiges anderes lokales Maximum mit einem Wert, der dem globalen Maximum ausreichend nahe kommt) und die Berechnung in einem kleineren, aber höher auflösenden Raster wiederholen.

whuber
quelle
viel schöner als Vektoren. Ich bin nicht sicher, warum ich dachte, dass Raster ein flaches Erdmodell erfordern.
Kirk Kuykendall
Schön, ja, aber ineffizient. Es wäre schön zu sehen, wie die vektorbasierte sphärische Voronoi-Lösung funktioniert.
whuber
@Whuber: Wie können Sie automatisch die Koordinaten des schwarzen Punktes ermitteln? "
Demetris
@Demetris Eine Möglichkeit besteht darin, den Maximalwert im Raster zu berechnen, alle Zellen auszuwählen, die diesem Wert entsprechen, und die Koordinaten des Mittelpunkts dieser Zelle zu verwenden.
whuber
@Whuber: Vielen Dank. Das ist eine gute Idee. Ich muss das Ausgabe-Raster jedoch basierend auf einer Feature-Class (einem eindeutigen Polygon) ausschneiden. Kann ich das tun?
Demetris
8

Bildbeschreibung hier eingeben

Ich habe das noch nie ausprobiert, aber es scheint, als würde das funktionieren:

Erstellen Sie ein 3D-Voronoi-Diagramm der Kugel. Diese resultierenden Polygone werden grob auf den ursprünglich vorhandenen (Startpunkt-) Punkten zentriert.

Durchlaufen Sie jeden resultierenden Scheitelpunkt, um denjenigen zu finden, der am weitesten von seinem nächsten existierenden Punkt entfernt ist. Dieser Punkt sollte der am weitesten entfernte Punkt der Welt sein.

Kirk Kuykendall
quelle
Dies ist eine großartige Idee (+1). Aber wie sieht das sphärische Voronoi-Diagramm aus, wenn alle Punkte in einer gemeinsamen Hemisphäre liegen? Der Code, auf den Sie verweisen, erhält ihn mit einer konvexen Hülle, aber das scheint nicht zu funktionieren.
whuber
hmm, ja, ich denke auch wenn sie nicht alle in einer gemeinsamen Hemisphäre sind, wird es ein Polygon geben, dem ein Startpunkt fehlt. Was wäre, wenn Sie einen Punkt dafür konstruierten, indem Sie den antipodalen Punkt des Schwerpunkts der konvexen Hüllen verwendeten? Zusätzlich zum Durchlaufen jedes Scheitelpunkts wird dann geprüft, ob dieser konvexe Antipodenpunkt weiter von seinen Nachbarn entfernt ist als der maximale Scheitelpunktabstand.
Kirk Kuykendall
Das war mein erster Gedanke, aber die antipodalen Punkte werden künstliche Polygone erzeugen. Überlegen Sie, was in Ihrer Illustration passieren würde, wenn zum Beispiel der Antipode zu jedem Punkt enthalten wäre! Es gibt wahrscheinlich eine Lösung dieser Art, aber es scheint nicht einfach zu sein.
whuber
1

Mithilfe einer kostengewichteten Distanzfunktion können Sie ermitteln, wie weit jede Zelle in Ihrem Raster von allen anderen Punkten entfernt ist.

djq
quelle
Welche Kosten würden Sie verwenden?
whuber
Wenn Sie die Kosten auf eine Einheit festlegen; Sie können anhand der Entfernung den am weitesten entfernten Punkt bestimmen.
29.
@whuber Obwohl dies vielleicht nicht anders ist als die Berechnung des bereits erwähnten euklidischen Distanzansatzes.
29.
Das ist euklidische Distanz. Eigentlich ist es nicht einmal das: Es ist eine seltsame Art von achteckigem Abstand (Kreise sind eigentlich Achtecke). In dieser Situation (Entfernungen nur von Punkten, ohne Hindernisse) ist es viel genauer und schneller, entweder eine euklidische Entfernung oder ein sphärisches Entfernungsgitter direkt zu berechnen, anstatt zu versuchen, CostDistance dafür zu nutzen.
whuber
Ich bin mir nicht sicher, ob eine kostengewichtete Entfernungsfunktion helfen würde, da ich nur die Koordinaten eines Punktes benötige und einen spannenden Vektorsatz von Punkten habe, aber ich werde es versuchen. Vielen Dank.
Demetris
1

Soweit ich weiß, muss diese " Pole of Inaccessability " -Analyse iterativ durchgeführt werden.

Ein iterativer Rasteransatz wäre angemessen, solange Sie einen kleinen Bereich mit minimaler Verzerrung durch die Projektion betrachten. Berechnen Sie für jede Zelle den Abstand zu allen Punkten und nehmen Sie dann den Mindestabstand. Die Zelle mit dem höchsten Wert ist der Pol. Sie können dazu auch Euklidische Entfernung in Spatial Analyst verwenden.

Ein iterativer Vektoransatz ist komplizierter. Garcia-Castellanos et al. 2007 beschreiben eine iterative Methode basierend auf einer kugelförmigen Erde. Es scheint, dass sie ihren C-Code online verfügbar gemacht haben . Ich kann mir vorstellen, wie dies in Arc mit Puffern gemacht werden kann, aber es würde immer noch iterativ und langsam sein.

dmahr
quelle
0

Sie können Punktabstand (Analyse) verwenden. Das Werkzeug erstellt eine Tabelle mit Abständen zwischen zwei Punktsätzen. Wenn der Standardsuchradius verwendet wird, werden Entfernungen von allen Eingabepunkten zu allen Nahpunkten berechnet. Die Ausgabetabelle kann sehr groß sein. Wenn beispielsweise sowohl Eingabe- als auch Near-Features jeweils 1.000 Punkte aufweisen, kann die Ausgabetabelle eine Million Datensätze enthalten.

Salehamra
quelle
Wie kann dies angewendet werden, um die Koordinaten eines neuen Punktes zu finden, der nicht in der Eingabe erscheint? Vielleicht haben Sie die Frage falsch verstanden?
Whuber
0

Der am weitesten von Ihrer Punktmenge entfernte Punkt ist der Kehrwert des innersten Punkts in Ihrer Menge. Wenn zum Beispiel Ihr innerster Punkt in Ihrem Satz Koordinaten von 49 Grad Nord und -144 Grad Ost hätte, dann hätten der reziproke und der am weitesten entfernte Punkt Koordinaten von 49 Grad Süd und 36 Grad West. Dies ist nicht ganz richtig, da die Erde nicht perfekt kugelförmig, sondern geoidal ist. Daher hängt die Korrektheit Ihres Ergebnispunkts stark davon ab, welche Projektions- und geografischen Systeme (orthografisch, orthorektifiziert ...) Sie verwenden. Es kann hilfreich sein, einen Kehrwert für den gesamten Satz zu finden (einen Antipode für einen Satz zu übertragen) und dann eine Oberflächenanalyse innerhalb des vom Antipode-Satz von Punkten abgedeckten Geländes durchzuführen, da das Gelände sehr unterschiedlich sein kann. Ich gehe davon aus, dass es bei Ihrer Frage nicht um Punkte auf außerirdischen Körpern wie anderen Planeten oder Monden geht. Es tut uns leid, Ich habe keinen VB-Code für dich. 🙄

Yuriy Shevchuk
quelle
Der Punkt, der am weitesten von allen anderen Punkten in einer Menge entfernt ist, wäre der innerste (einer, der am weitesten von allen äußersten Punkten entlang der Kante entfernt ist), und er wäre dennoch jedem Punkt unmittelbar daneben am nächsten, was auch immer. Dies ist eine Clusteranalyse, die keinen Spaß macht. Es ist wahrscheinlich besser, die gleichen Ladungsatome in der Physik zu untersuchen. “
Yuriy Shevchuk,