Unir líneas cuando no se conoce la dirección

Estoy luchando con este problema. Tengo una polilínea compuesta de varios segmentos. Cada segmento está formado por puntos, cada punto identificado en el espacio 3D por coordenadas y elevación. Juntos, si se trazan, los segmentos forman una línea más o menos continua (podría haber saltos entre segmentos), pero los segmentos en sí no son consecutivos, ni los puntos de todos los segmentos siguen la misma dirección de desplazamiento.
La pregunta es: ¿cómo puedo crear, usando Python preferiblemente, una sola línea de estos segmentos no consecutivos para que pueda medir la distancia entre los puntos y la longitud total de la línea?
Ni siquiera sé cuál de los segmentos es el primero o el último de la línea, pero de alguna manera tengo que ponerlos en la secuencia correcta y asegurarme de que todos apunten en la misma dirección para poder medirlos.
gracias por cualquier ayuda Estaré encantado de proporcionar información adicional, datos, etc. Destaco que no estoy pidiendo el código de Python real (no es que lo rechace ...), solo la estrategia. Beto

Los segmentos se pueden usar para formar un gráfico abstracto G en el que juegan el papel de nodos . Considere un nodo que es el segmento (arco) desde el punto P hasta el punto Q, PQ. Deje que R sea el punto final más cercano entre todos los otros puntos finales del segmento a P y deje que S sea el otro punto final del segmento de R. G entonces contiene un borde del nodo PQ al nodo RS y etiquetaremos este borde con los puntos P y R.

Si queremos tener éxito, entonces G es un gráfico lineal o un solo ciclo. Puede detectar cuál es cuál almacenando los grados de los nodos a medida que crea los bordes. (El grado de un nodo cuenta los bordes que emanan de ese nodo). Todos los nodos, excepto posiblemente dos de ellos, deben tener grado 2. Los otros dos deben tener grado 2 (para un ciclo) o grado 1: esto los marca como Los extremos de la polilínea. En el primer caso, elija cualquier nodo para comenzar a construir la polilínea; en el segundo caso, elija uno de los de grado 1. Cualquier otra combinación de grados es un error.

La polilínea se inicializa en el nodo inicial (un arco). Observe uno de los bordes e incidentes en este nodo: su otro nodo le indica qué arco debe procesar a continuación y su etiqueta le indica qué vértices de esos arcos debe unir. (Una los vértices con un nuevo segmento de línea si no tienen coordenadas idénticas.) Actualización de la creciente polilínea de esta manera y, al mismo tiempo, el borde remove e partir de la gráfica G . Continúe hasta que se produzca un error (e informe que los bordes no forman una polilínea conectada sin ramificación) o que se eliminen todos los bordes. Si no se genera ningún error, genere la polilínea que creó.

Ejemplo

En la figura, los arcos son AB, CD, EF y FG. Los nodos del gráfico son, por lo tanto, {AB, CD, EF, FG}. Los bordes son AB - CD (etiquetado con B y C), CD-EF (etiquetado con E y F) y EF - FG (etiquetado con F y F). Los grados de AB y FG son 1, mientras que los grados de CD y EF son 2. Aquí hay un esquema del gráfico abstracto y sus etiquetas de borde:

Comencemos arbitrariamente con FG, uno de los nodos de grado uno. Debido a que tiene grado 1, hay un borde único EF - FG conectado a él, etiquetado con F. Inicialice la polilínea con el arco G -> F. Debido a que la etiqueta designa un punto final común de GF y EF, no tenemos que hacer una nueva conexión. Retire el borde EF - FG del gráfico y extienda la polilínea con EF a través de G -> F -> E.

Esta eliminación de bordes reduce el grado de EF de 2 a 1, dejándolo con un solo borde para formar un CD con etiqueta con E y D. Esto le indica que extienda la polilínea de E a D (con un nuevo segmento de línea allí) y de allí en adelante CD de arco: G -> F -> E -> D -> C. De la misma manera, después de eliminar el borde ED - CD, extenderá la polilínea más hasta su forma final G -> F -> E -> D -> C -> B -> A. Se detiene porque se han eliminado todos los bordes del gráfico: esto indica que el procedimiento fue exitoso.

Siguiendo con la respuesta de whuber, si está buscando hacer esto en Python, eche un vistazo a la biblioteca NetworkX que tiene todo tipo de funcionalidad relacionada con gráficos, nodos y bordes. Creo que es la Transversales funciones que implementan lo whuber está describiendo. También incluye la funcionalidad básica de dibujo.

Una vez que tenga sus órdenes de línea, puede construir fácilmente geometrías en Shapely para realizar análisis de tipo SIG adicionales, o mostrar en MatPlotLib, exportar a GeoJSON, etc.

¿Calcularía la distancia entre cada segmento inicial y final y luego uniría los que tienen la distancia más corta entre ellos?

Tiene muchos segmentos, sin un orden u orientación específicos. No sabes cuáles se tocan o se superponen, y cuáles son simplemente cercanas.

Para cada segmento, solo el comienzo y el punto final son importantes. El objetivo es hacer una gran polilínea, supongo que la orientación de esa polilínea no es importante.

En ese caso, haría algún tipo de conjunto / matriz de segmentos, comience con el primero, que es completamente aleatorio.

En pseudocódigo hacer algo como

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

¿Algo como eso? Ese es un nivel muy alto. Necesitará manejar casos límite. Supongo que sabe o podría la mayor brecha / distancia posible, porque necesitará poder excluir de alguna manera los puntos encontrados: si el punto más cercano posible está en el otro extremo de la polilínea, entonces no es una opción :) La forma más fácil de manejar eso es definir una distancia máxima de separación. Esto también limitará el número de puntos que tendrá que mirar para cada segmento.

[EDITAR: detalle el find_segment_closes_to]

Para dejar absolutamente claro cómo encontraría el segmento de cierre, primero escribiré un enfoque muy burdo:

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     

Este es un enfoque muy burdo, que iterará sobre todos los segmentos y verificará cada punto final que sea el más cercano.

Idealmente, tendría una estructura de datos en la que podría solicitar todos los puntos de inicio y finalización que se encuentran dentro del rango y solo encontrar el punto más cercano entre ellos.

¿Eso ayuda? Espero que te ayude a comenzar.