Linien verbinden, wenn die Richtung nicht bekannt ist

Ich kämpfe mit diesem Problem. Ich habe eine Polylinie, die aus mehreren Segmenten besteht. Jedes Segment besteht aus Punkten, wobei jeder Punkt im 3D-Raum durch Koordinaten und Höhe identifiziert wird. Zusammen bilden die Segmente beim Zeichnen eine mehr oder weniger durchgehende Linie (es kann zu Unterbrechungen zwischen den Segmenten kommen), aber die Segmente selbst sind nicht aufeinanderfolgend, und die Punkte aller Segmente folgen nicht der gleichen Fahrtrichtung.
Die Frage ist: Wie kann ich mit Python vorzugsweise eine einzelne Linie aus diesen nicht aufeinander folgenden Segmenten erstellen, damit ich den Abstand zwischen Punkten und die Gesamtlänge der Linie messen kann.
Ich weiß nicht einmal, welches der Segmente das erste oder das letzte in der Zeile ist, aber irgendwie muss ich sie in die richtige Reihenfolge bringen und sicherstellen, dass sie alle in die gleiche Richtung zeigen, damit ich sie messen kann.
Vielen Dank für jede Hilfe. Ich werde gerne zusätzliche Informationen, Daten usw. bereitstellen. Ich betone, ich frage nicht nach dem tatsächlichen Python-Code (nicht, dass ich ihn ablehnen würde ...), sondern nur nach der Strategie. Bob

Die Segmente können verwendet werden, um einen abstrakten Graphen G zu bilden, in dem sie die Rolle von Knoten spielen . Betrachten Sie einen Knoten, der das Segment (Bogen) von Punkt P zu Punkt Q, PQ ist. Sei R der nächstgelegene Endpunkt unter allen anderen Segmentendpunkten zu P und sei S der andere Endpunkt des R-Segments. G enthält dann eine Kante vom Knoten PQ zum Knoten RS, und wir werden diese Kante mit den Punkten P und R beschriften.

Wenn wir erfolgreich sein wollen, ist G entweder ein linearer Graph oder ein einzelner Zyklus. Sie können erkennen, welche welche ist, indem Sie die Grade der Knoten speichern, während Sie die Kanten erstellen. (Der Grad eines Knotens zählt die Kanten, die von diesem Knoten ausgehen.) Alle Knoten, außer möglicherweise zwei, müssen Grad 2 haben. Die anderen beiden müssen beide Grad 2 (für einen Zyklus) oder Grad 1 haben. Dies markiert sie als die Enden der Polylinie. Wählen Sie im ersten Fall einen beliebigen Knoten aus, um mit dem Aufbau der Polylinie zu beginnen. Wählen Sie im zweiten Fall einen der Grade 1 aus. Jede andere Kombination von Graden ist ein Fehler.

Die Polylinie wird am Startknoten (einem Bogen) initialisiert. Blick auf eine der Kanten e Vorfall auf diesem Knoten: seinen anderen Knoten Sie sagt , die neben verarbeiten Bogen und das Etikett sagt Ihnen , welche Eckpunkte dieser Bögen zu verbinden. (Join die Ecken mit einem neuen Liniensegment , wenn sie nicht identisch Koordinaten haben.) Aktualisieren die wachsende Polylinie in dieser Art und Weise und zur gleichen Zeit, entfernen Kante e aus dem Graphen G . Fahren Sie fort, bis entweder ein Fehler auftritt (und melden Sie, dass die Kanten keine nicht verzweigte verbundene Polylinie bilden) oder alle Kanten entfernt sind. Wenn kein Fehler auftritt, geben Sie die von Ihnen erstellte Polylinie aus.

Beispiel

In der Abbildung sind die Bögen AB, CD, EF und FG. Die Knoten des Graphen sind daher {AB, CD, EF, FG}. Die Kanten sind AB-CD (mit B und C gekennzeichnet), CD-EF (mit E und F gekennzeichnet) und EF-FG (mit F und F gekennzeichnet). Die Grade von AB und FG sind 1, während die Grade von CD und EF 2 sind. Hier ist eine schematische Darstellung des abstrakten Graphen und seiner Kantenbeschriftungen:

Beginnen wir willkürlich mit FG, einem der Knoten ersten Grades. Da es Grad 1 hat, ist eine eindeutige Kante EF - FG damit verbunden, die mit F gekennzeichnet ist. Initialisieren Sie die Polylinie mit dem Bogen G -> F. Da das Etikett einen gemeinsamen Endpunkt von GF und EF angibt, müssen wir keine neue Verbindung herstellen. Entfernen Sie die Kante EF - FG aus dem Diagramm und verlängern Sie die Polylinie mit EF über G -> F -> E.

Diese Kantenentfernung verringert den EF-Grad von 2 auf 1, sodass eine einzelne Kante für die mit E und D gekennzeichnete CD verbleibt. Dies weist Sie an, die Polylinie von E nach D (mit einem neuen Liniensegment dort) und von dort entlang zu verlängern Bogen CD: G -> F -> E -> D -> C. Auf die gleiche Weise verlängern Sie nach dem Entfernen der Kante ED - CD die Polylinie weiter bis zu ihrer endgültigen Form G -> F -> E -> D -> C -> B -> A. Sie stoppen, weil alle Kanten aus dem Diagramm entfernt wurden. Dies zeigt an, dass der Vorgang erfolgreich war.

Wenn Sie dies nach der Antwort von whuber in Python tun möchten, sehen Sie sich die NetworkX-Bibliothek an , die alle möglichen Funktionen in Bezug auf Diagramme, Knoten und Kanten bietet. Ich denke, es sind die Traversal- Funktionen, die implementieren, was whuber beschreibt. Es enthält auch grundlegende Zeichenfunktionen.

Sobald Sie Ihre Linienreihenfolgen haben, können Sie in Shapely problemlos Geometrien erstellen , um weitere GIS-Typanalysen durchzuführen, oder in MatPlotLib anzeigen, nach GeoJSON exportieren usw.

Ich würde den Abstand zwischen jedem Startsegment und Endsegment berechnen und dann diejenigen mit dem kürzesten Abstand zwischen ihnen verbinden.

Sie haben viele Segmente, keine bestimmte Reihenfolge oder Ausrichtung. Sie wissen nicht, welche tatsächlich berühren oder überlappen und welche nur nahe beieinander liegen.

Für jedes Segment ist nur der Anfangs- und Endpunkt wichtig. Das Ziel ist es, eine große Polylinie zu erstellen. Die Ausrichtung dieser Polylinie ist nicht wichtig, denke ich.

In diesem Fall würde ich eine Art Satz / Array von Segmenten erstellen, beginnend mit dem ersten, der völlig zufällig ist.

Im Pseudocode mache so etwas

all_segments = set of all segments

# take the first segment out of set
new_polyline = all_segments.pop

until all_segments.empty?
  start_segm = find_segment_closest_to(new_polyline.start_point)
  remove_from_all_segments(start_segm)
  expand_polyline_at_begin(new_polyline, start_segm) 
  end_segm = find_segment_closest_to(new_polyline.end_point)
  expand_polyline_at_end(new_polyline, end_segm)
  remove_from_all_segments(end_segm)
end

So ähnlich? Das ist ein sehr hohes Niveau. Sie müssen Grenzfälle behandeln. Ich vermute, Sie kennen oder könnten die größtmögliche Lücke / Entfernung kennen, weil Sie in der Lage sein müssen, gefundene Punkte irgendwie auszuschließen: Wenn sich der nächstmögliche Punkt am anderen Ende der Polylinie befindet, ist dies keine Option :) Die Der einfachste Weg, dies zu handhaben, besteht darin, einen maximalen Spaltabstand zu definieren. Dies begrenzt auch die Anzahl der Punkte, die Sie für jedes Segment suchen müssen.

[EDIT: Detail die find_segment_closes_to]

Um absolut klar zu machen, wie ich das Closes-Segment finden würde, werde ich zunächst einen sehr groben Ansatz schreiben:

def find_segment_closes_to(point)
  closest_point = nothing
  closest_distance = MAX_GAP_RANGE
  all_segments.each do |segment|
    if distance(segment.end_point, point) < closest_distance
      closest_point = segment.end_point
      closest_segment = segment
      closest_distance = distance(segment.end_point, point)
   else if distance(segment.start_point, point) < closest_distance
      closest_point = segment.start_point
      closest_segment = segment
      closest_distance = distance(segment.start_point, point)
    end       
  end  
  # the closest segment
  return closest_segment
end     

Dies ist ein sehr grober Ansatz, der alle Segmente durchläuft und nach jedem Endpunkt sucht, der am nächsten liegt.

Idealerweise hätten Sie eine Datenstruktur, in der Sie nach allen Start- und Endpunkten fragen könnten, die in Reichweite liegen, und nur den nächstgelegenen Punkt unter diesen finden könnten.

Hilft das? Ich hoffe, es bringt Sie zum Laufen.