Нахождение средних точек между двумя линиями фигуры

Question

У меня есть фигура в системе координат, которую вы можете увидеть здесь:

Как вы можете видеть, он состоит из 2 в основном параллельных линий, и я хочу вместо двух линий сделать только одну линию, проходящую через середину этих двух строк, например:

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

Вот код, который я использую для построения:

from matplotlib import pyplot as plt

fig = plt.figure()
ax = fig.add_subplot(111)

A = 155, 158, 182, 186, 195, 256, 263, 275, 284, 317, 317, 317, 316, 316, 312, 310, 305, 295, 296, 300, 294, 288, 280, 266, 251, 194, 189, 188, 187, 183, 142, 126, 101, 101, 101, 131, 189, 232, 290, 306, 309, 309, 309, 288, 266, 227, 218, 214, 208, 175, 156, 134, 89 , 79 , 72 , 58 , 57 , 56 , 69 , 87 , 132, 154, 167, 196, 234, 252, 260, 274, 281, 281, 281, 233, 201, 176, 132, 110, 90 , 74 , 74 , 74 , 75 , 75 , 77 , 94 , 108, 151
B = 475, 475, 492, 492, 492, 519, 521, 524, 524, 524, 495, 494, 488, 487, 471, 471, 471, 484, 488, 492, 496, 499, 499, 499, 492, 467, 467, 467, 467, 467, 436, 420, 397, 387, 375, 360, 329, 284, 224, 178, 170, 163, 142, 132, 122, 122, 122, 124, 128, 133, 136, 136, 136, 126, 119, 124, 134, 146, 152, 161, 161, 161, 158, 151, 151, 151, 152, 153, 158, 165, 178, 248, 283, 308, 329, 340, 358, 374, 381, 382, 386, 388, 400, 421, 437, 475


plt.plot(A, B)
for xy in zip(A, B):
    ax.annotate('(%s, %s)' % xy, xy=xy, textcoords='data')  # <--

plt.grid()
plt.show()

Answer 1

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

Вот простая реализация, использующая KMeans

from sklearn.cluster import KMeans
import numpy as np

A = 155, 158, 182, 186, 195, 256, 263, 275, 284, 317, 317, 317, 316, 316, 312, 310, 305, 295, 296, 300, 294, 288, 280, 266, 251, 194, 189, 188, 187, 183, 142, 126, 101, 101, 101, 131, 189, 232, 290, 306, 309, 309, 309, 288, 266, 227, 218, 214, 208, 175, 156, 134, 89 , 79 , 72 , 58 , 57 , 56 , 69 , 87 , 132, 154, 167, 196, 234, 252, 260, 274, 281, 281, 281, 233, 201, 176, 132, 110, 90 , 74 , 74 , 74 , 75 , 75 , 77 , 94 , 108, 151
B = 475, 475, 492, 492, 492, 519, 521, 524, 524, 524, 495, 494, 488, 487, 471, 471, 471, 484, 488, 492, 496, 499, 499, 499, 492, 467, 467, 467, 467, 467, 436, 420, 397, 387, 375, 360, 329, 284, 224, 178, 170, 163, 142, 132, 122, 122, 122, 124, 128, 133, 136, 136, 136, 126, 119, 124, 134, 146, 152, 161, 161, 161, 158, 151, 151, 151, 152, 153, 158, 165, 178, 248, 283, 308, 329, 340, 358, 374, 381, 382, 386, 388, 400, 421, 437, 475

df=pd.DataFrame([list(A),list(B)]).T
df.columns=['A','B']

km = KMeans(n_clusters=20).fit(df)
pts=km.cluster_centers_[km.labels_]

Вот вывод:

plt.plot(pts[:,0],pts[:,1])
plt.plot(X, Y)

Вот центроиды:

plt.plot(km.cluster_centers_[:,0], km.cluster_centers_[:,1],'.')
plt.plot(X, Y)

Вам нужно поиграться с количеством кластеров, но вы можете получить довольно точные приближения. Вот с 12 центроидами:

km = KMeans(n_clusters=12).fit(df)
pts=km.cluster_centers_[km.labels_]
plt.plot(pts[:,0], pts[:,1])
plt.plot(X, Y)