Geographische Hindernisse in Radius sucht

Question

Ich bin neu hier und Punkte schlecht, so kann ich nur 50 pt Kopfgeld anbieten.

Angenommen, ich habe eine Anwendung eine Suche nach allen Tankstellen innerhalb von 10 Meile Radius von einem bestimmten Standort. Allerdings ist die eine Seite dieses Standortes von einer Bergkette umgeben, die Sie 50 Meilen fahren müssen, um sich fortzubewegen. Sie würden nicht Ergebnisse von der anderen Seite des Berges zurückgeben wollen. Was sind einige gute Algorithmen/Techniken, um mit einem solchen Problem umzugehen? Ich weiß, dass Sie mit Punkt-zu-Punkt-Suchen Pfadkosten verwenden können, aber ich bin nicht sicher, was die Technik mit Radius-Suchen ist. Hier

ein Beispiel:

Die rote Linie ist ein Akkord auf dem Kreis mit Radius von 40 -74 bis 41, -72 lat lang (nicht genau nur sagen) Der Anwender bei 40 , -73 führt eine geografische Radiussuche nach etwas durch, das auch Bereiche über den LI-Ton in Connecticut umfasst, die nicht erreichbar sind. Der Algorithmus sollte wissen, dass es einen Akkord gibt, der den Suchkreis vollständig schneidet und keine Ergebnisse liefert, die auf der anderen Seite dieses Akkords liegen. Es werden also nur Punkte im grünen Bereich zurückgegeben.

Dies sollte ohne Straßennetzwerkanalyse möglich sein, wenn der Programmierer diese Begrenzungslinien definiert. Zum Beispiel kann es in einem Land ein Gebiet geben, in dem es gefährlich ist, es zu passieren, und Sie möchten, dass die Menschen auf beiden Seiten dieses Gebiets auf diese Seite beschränkt sind. Oder eine internationale Grenze usw. Ich frage das nur, weil ich mir ziemlich sicher bin, dass die Leute das machen.

Answer 1

Obwohl die beste Lösung wäre, die Entfernung entlang eines Straßennetzes (anstatt der geraden Entfernung) zu berechnen, z. B. mit ArcGIS Network Analyst, wäre ein schmutziger Hack, gerade Linien zwischen der Mitte Ihres Radius und jedem zu erstellen Station, berechnen Sie dann die Gesamthöhenzunahme entlang des Profils (ein Skript, um dies automatisch zu tun, wird here gegeben). Sie könnten dann einen Schwellenwert festlegen, um diejenigen mit totalen Höhengewinnen abzuweisen, die höher als ein bestimmter Wert sind (diejenigen, die Sie überqueren müssen, um Berge zu erreichen).

EDIT Da Sie scheinbar keine Netzwerkanalyse verwenden, erstellen Sie eine Raster-Kosten-Map, in der der Wert der Schwierigkeit entspricht, dieses Terrain zu überqueren. Dies könnte auf anderen Daten beruhen (d. H. Gewässer, Höhenlage, Landbedeckung usw.). Dann können Sie entweder die Station mit der niedrigsten Kosten zurückgeben oder anhand der Kostenkarte ein Attribut auswählen ...

Eine weitere Option wäre, eine Polygon-Vektorschicht zu erstellen, die die unpassierbaren Zonen (Berge, Gewässer usw.) und Erstellen Sie dann eine Linie zwischen Ihrem Standort und allen Stationen im Umkreis. Mit Select by Location können Sie sehen, ob diese Linie eines der unpassierbaren Polygone schneidet. Wenn dies der Fall ist, heben Sie die Auswahl der Station auf.

Das beste Werkzeug für die Aufgabe ist noch Analyse Netzwerk ...

Answer 2

Sie sollten Ihre Metrik ändern, was „in der Nähe“ bedeutet dann. In Ihrem Beispiel 10 Meilen in der Nähe von Meams 10 Meilen Luftlinie. Sie können jedoch lieber nach Tankstellen fragen, wo der kürzeste Weg nicht länger als 16 km ist.

Sie können auch beide Ansätze kombinieren und zuerst alle umliegenden Punkte abfragen und diese dann filtern, d. H. Indem Sie die Routenlängen berechnen.

Wenn Sie mehr in den Algorithmen sind, würde ich vorschlagen, dass Sie Wegfindung Algorithmen für Navigationsassistenten betrachten.

Answer 3

Lösung, die möglicherweise näher an dem ist, was Sie fragen, ist Standorte aller Tankstellen in der Region zu nehmen, fügen Sie Schnittpunkte zwischen Kreis und Ihre Sperrzone Grenzlinien und führen dann topologische Sortierung auf resultierende Knoten in 2 -dimensionaler Raum. Das Finden von Tankstellen in einem bestimmten Gebiet ist so einfach wie das Zurückgeben von Werten, die innerhalb eines gegebenen Bereichs liegen, da die Einträge in einem Satz sortiert sind.

Weitere Informationen finden Sie in den Kapiteln 5.10.1 und 15.2 in Steven Skienn'a "Algorithm Design Manual". Die Boost-Graph-Bibliothek ermöglicht die Implementierung eines topologischen Sortieralgorithmus.

Ich denke immer noch, dass dies streng genommen ein Graphproblem ist, also ist "10 Meilen Radius" nicht das, was Ihr Algorithmus verwenden würde, um Übereinstimmungen zu finden, sondern eher eine Straßenentfernung. Eine gute Lösung sollte auch Faktoren wie Geschwindigkeitsbegrenzung auf Straßen, Einbahnstraßen usw. umfassen und es dem Benutzer ermöglichen, in die Kostenfunktion für die beste Übereinstimmung einzubeziehen.