Ответ 1

Я прошу прощения за длинный ответ заранее: P (проблема не такая простая).

Давайте начнем с перезаписи проблемы. Поиск линии, соединяющей все точки, можно переформулировать как кратчайшую проблему пути в графе, где (1) узлы графа являются точками в пространстве, (2) каждый node связан с двумя его ближайшими соседями, и (3) кратчайший путь проходит через каждый из узлов только один раз. Последнее ограничение является очень важным (и довольно сложно оптимизировать). По сути, проблема заключается в том, чтобы найти перестановку длины N, где перестановка относится к порядку каждого из узлов (N - общее количество узлов) в пути.

Найти все возможные перестановки и оценить их стоимость слишком дорого (есть перестановки N!, если я не ошибаюсь, что слишком велико для проблем). Ниже я предлагаю подход, который найдет лучшие перестановки N (оптимальная перестановка для каждой из точек N), а затем найдет перестановку (из тех N), которая минимизирует ошибку/стоимость.

1. Создайте случайную проблему с неупорядоченными точками

Теперь давайте начнем создавать проблему с образцом:

import matplotlib.pyplot as plt
import numpy as np

x = np.linspace(0, 2 * np.pi, 100)
y = np.sin(x)

plt.plot(x, y)
plt.show()

И здесь несортированная версия точек [x, y] для имитации случайных точек в пространстве, связанных в строке:

idx = np.random.permutation(x.size)
x = x[idx]
y = y[idx]

plt.plot(x, y)
plt.show()

Задача состоит в том, чтобы затем упорядочить эти точки, чтобы восстановить их первоначальный порядок, чтобы линия была построена правильно.

2. Создайте граф 2-NN между узлами

Мы можем сначала переставить точки в массиве [N, 2]:

points = np.c_[x, y]

Затем мы можем начать с создания ближайшего соседнего графа для подключения каждого из узлов к двум ближайшим соседям:

from sklearn.neighbors import NearestNeighbors

clf = NearestNeighbors(2).fit(points)
G = clf.kneighbors_graph()

G - разреженная матрица N x N, где каждая строка представляет собой node, а ненулевые элементы столбцов - евклидово расстояние до этих точек.

Затем мы можем использовать networkx для построения графика из этой разреженной матрицы:

import networkx as nx

T = nx.from_scipy_sparse_matrix(G)

3. Найти кратчайший путь из источника

И здесь начинается волшебство: мы можем извлечь пути, используя dfs_preorder_nodes, который по существу создаст путь через все узлы ( проходя через каждую из них ровно один раз), учитывая начальный node (если не указан, будет выбран 0 node).

order = list(nx.dfs_preorder_nodes(T, 0))

xx = x[order]
yy = y[order]

plt.plot(xx, yy)
plt.show()

Ну, не так уж плохо, но мы можем заметить, что реконструкция не оптимальна. Это связано с тем, что точка 0 в неупорядоченном списке лежит посредине линии, то есть она сначала идет в одном направлении, а затем возвращается и заканчивается в другом направлении.

4. Найдите путь с наименьшими затратами из всех источников

Итак, чтобы получить оптимальный порядок, мы можем просто получить лучший порядок для всех узлов:

paths = [list(nx.dfs_preorder_nodes(T, i)) for i in range(len(points))]

Теперь, когда у нас есть оптимальный путь, начинающийся с каждого из узлов N = 100, мы можем отбросить их и найти ту, которая минимизирует расстояния между соединениями (проблема оптимизации):

mindist = np.inf
minidx = 0

for i in range(len(points)):
    p = paths[i]           # order of nodes
    ordered = points[p]    # ordered nodes
    # find cost of that order by the sum of euclidean distances between points (i) and (i+1)
    cost = (((ordered[:-1] - ordered[1:])**2).sum(1)).sum()
    if cost < mindist:
        mindist = cost
        minidx = i

Точки упорядочены для каждого из оптимальных путей, а затем вычисляется стоимость (путем вычисления евклидова расстояния между всеми парами точек i и i+1). Если путь начинается с точки start или end, он будет иметь наименьшую стоимость, поскольку все узлы будут последовательно. С другой стороны, если путь начинается с node, который лежит в середине линии, в какой-то момент стоимость будет очень высокой, так как она должна будет перемещаться с конца (или начала) линии на начальная позиция для изучения в другом направлении. Путь, который минимизирует эту стоимость, - это путь, начинающийся в оптимальной точке.

opt_order = paths[minidx]

Теперь мы можем восстановить порядок должным образом:

xx = x[opt_order]
yy = y[opt_order]

plt.plot(xx, yy)
plt.show()

Ответ 2

Одним из возможных решений является использование подхода ближайших соседей, возможно с помощью KDTree. Scikit-learn имеет приятный интерфейс. Затем это можно использовать для построения графического представления с использованием networkx. Это будет действительно работать, только если линия, которую нужно нарисовать, должна пройти через ближайших соседей:

from sklearn.neighbors import KDTree
import numpy as np
import networkx as nx

G = nx.Graph()  # A graph to hold the nearest neighbours

X = [(0, 1), (1, 1), (3, 2), (5, 4)]  # Some list of points in 2D
tree = KDTree(X, leaf_size=2, metric='euclidean')  # Create a distance tree

# Now loop over your points and find the two nearest neighbours
# If the first and last points are also the start and end points of the line you can use X[1:-1]
for p in X
    dist, ind = tree.query(p, k=3)
    print ind

    # ind Indexes represent nodes on a graph
    # Two nearest points are at indexes 1 and 2. 
    # Use these to form edges on graph
    # p is the current point in the list
    G.add_node(p)
    n1, l1 = X[ind[0][1]], dist[0][1]  # The next nearest point
    n2, l2 = X[ind[0][2]], dist[0][2]  # The following nearest point  
    G.add_edge(p, n1)
    G.add_edge(p, n2)


print G.edges()  # A list of all the connections between points
print nx.shortest_path(G, source=(0,1), target=(5,4))
>>> [(0, 1), (1, 1), (3, 2), (5, 4)]  # A list of ordered points

Обновление. Если начальная и конечная точки неизвестны, и ваши данные достаточно хорошо разделены, вы можете найти их, просмотрев клики на графике. Начальная и конечная точки образуют клику. Если самый длинный край удаляется из клики, он создает свободный граф на графике, который может использоваться как начальная и конечная точки. Например, начальная и конечная точки в этом списке отображаются посередине:

X = [(0, 1), (0, 0), (2, 1),  (3, 2),  (9, 4), (5, 4)]

После построения графика, теперь его случай удаления самого длинного края из кликов, чтобы найти свободные концы графика:

def find_longest_edge(l):
    e1 = G[l[0]][l[1]]['weight']
    e2 = G[l[0]][l[2]]['weight']
    e3 = G[l[1]][l[2]]['weight']
    if e2 < e1 > e3:
        return (l[0], l[1])
    elif e1 < e2 > e3:
        return (l[0], l[2])
    elif e1 < e3 > e2:
    return (l[1], l[2])

end_cliques = [i for i in list(nx.find_cliques(G)) if len(i) == 3]
edge_lengths = [find_longest_edge(i) for i in end_cliques]
G.remove_edges_from(edge_lengths)
edges = G.edges()

start_end = [n for n,nbrs in G.adjacency_iter() if len(nbrs.keys()) == 1]
print nx.shortest_path(G, source=start_end[0], target=start_end[1])
>>> [(0, 0), (0, 1), (2, 1), (3, 2), (5, 4), (9, 4)]  # The correct path