Dies ist ein Problem, auf das ich häufig gestoßen bin, und ich suche nach einem effektiveren Weg, es zu lösen. Schauen Sie sich diese Bilder an:

Angenommen, Sie möchten den kürzesten Abstand zwischen dem roten Punkt und einem Liniensegment a ermittelnn. Angenommen, Sie kennen nur den Start- / Endpunkt (x, y) der Segmente und den Punkt. Dies kann nun in O (n) geschehen, wobei n die Liniensegmente sind, indem jeder Abstand zwischen dem Punkt und einem Liniensegment überprüft wird. Dies ist IMO nicht effektiv, da im schlimmsten Fall n-1 Entfernungsprüfungen durchgeführt werden müssen, bis die richtige gefunden wurde.

Dies kann ein echtes Leistungsproblem für n = 1000 f sein. (was eine wahrscheinliche Zahl ist), insbesondere wenn die Entfernungsberechnung nicht nur im euklidischen Raum nach dem Satz von Pythagoras erfolgt, sondern beispielsweise nach einer geodätischen Methode wie der Haversin-Formel oder der von Vincenty.

Dies ist ein allgemeines Problem in verschiedenen Situationen:

Liegt der Punkt innerhalb eines Radius der Eckpunkte?Welche Scheitelpunktmenge ist dem Punkt am nächsten?Ist der Punkt von Liniensegmenten umgeben?

Um diese Fragen zu beantworten, ist der einzige Ansatz, den ich kenne, O (n). Jetzt würde ich gerne wissen, ob es eine Datenstruktur oder eine andere Strategie gibt, um diese Probleme effizienter zu lösen.

Um es kurz zu machen: Ich suche einen Weg, auf dem die Liniensegmente / Eckpunkte irgendwie "gefiltert" werden können, um eine Reihe potenzieller Kandidaten zu erhalten, bevor ich mit meinen Entfernungsberechnungen beginne. Etwas, um die Komplexität auf O (m) zu reduzieren, wobei m <n ist.