Python：在点坐标列表中查找最近的邻居对

Question

我有一份坐标表。元组的第一个元素是片号。第二个和第三个是xy坐标。现在我想找出最近的一组点。所以如果我有6个切片，必须有一个返回列表，其中包含6个坐标对，它们属于彼此。在

示例数据集：

array=[(0.0, 333.56146977926664, 3008.7982175915004),
(0.0, 172.37833716058688, 1649.3905288621663),
(0.0, 77.50966744006188, 2283.89997422016),
(0.0, 116.57814612355257, 581.9223534943867),
(0.0, 340.0307776756536, 2184.111532373366),
(0.0, 313.93527847976634, 318.1736354983754),
(0.0, 547.9143957324791, 1097.8102318962867),
(0.0, 432.92846166979683, 215.97046269421205),
(0.0, 449.53987956249233, 336.3028143050264),
(0.0, 503.6196838777661, 167.45041095890411),
(0.0, 503.75169204737733, 343.3688663282572),
(0.0, 636.3648922234131, 2193.3168988924617),
(0.0, 717.4529664732162, 3457.784309632166),
(0.0, 846.2564443852878, 603.3166955055681),
(0.0, 1535.2396900242939, 3131.323672911694),
(0.0, 1469.1578125128474, 1707.8372376026773),
(0.0, 1396.379645056139, 92.53690691778341),
(0.0, 1415.425816023739, 2627.336980712166),
(0.0, 1486.3829039812647, 2626.749414519906),
(0.0, 1646.0350180728474, 507.73284624177455),
(0.0, 1604.0196393706212, 901.6203629263811),
(0.0, 1842.0375522573343, 1814.7994048597038),
(0.0, 2007.165137614679, 979.321865443425),
(0.0, 2147.671282186245, 1843.2944622254672),
(0.0, 2070.921192867391, 3782.243082598893),
(0.0, 2065.1681055155877, 478.74772182254196),
(0.0, 2104.848780487805, 533.6113821138212),
(0.0, 2380.856736123359, 1090.9250925949254),
(0.0, 2279.9033647854726, 745.2587146163432),
(0.0, 2292.8939526730937, 831.2670902716915),
(0.0, 2474.9004065643826, 3268.4603377155236),
(0.0, 2453.183810923341, 3408.1759735488613),
(0.0, 2585.0363084532373, 2374.9155425659474),
(0.0, 2773.128683566231, 725.2908866474347),
(0.0, 2624.9709841731856, 915.2607786065126),
(0.0, 2714.8521421572996, 971.4124877527389),
(0.0, 2798.4276574009355, 2330.6135276090113),
(0.0, 2783.3074825567405, 934.502365867351),
(0.0, 2865.471879033745, 3063.324635810437),
(0.0, 2908.2407809110628, 1320.8433839479392),
(1.0, 154.6280574750466, 606.6849292530437),
(1.0, 376.7177563593005, 2208.945026828299),
(1.0, 364.8949263599067, 344.15018742067826),
(1.0, 583.3997824789169, 1120.0000411711828),
(1.0, 468.60350318471336, 243.40191082802548),
(1.0, 538.9199157860642, 190.7942831693591),
(1.0, 540.7046009389671, 364.90441314553993),
(1.0, 679.3226418205804, 3433.8067694591027),
(1.0, 673.7542547115934, 2217.11924614506),
(1.0, 889.9705312329176, 620.7821398399841),
(1.0, 1499.330283784636, 3113.874643753002),
(1.0, 1121.688416543088, 3732.0913165266106),
(1.0, 1501.9564873611191, 1734.5836790922503),
(1.0, 1433.621833357739, 118.40620881534632),
(1.0, 1682.7643898580789, 528.6640451282664),
(1.0, 1642.755639624492, 926.4499789827659),
(1.0, 1882.9388528959287, 1840.9367077636455),
(1.0, 2185.5049122512387, 1865.852288185406),
(1.0, 2101.435029585799, 498.7003550295858),
(1.0, 2139.9415746348413, 557.1467759173495),
(1.0, 2413.369506990553, 1121.0576549175898),
(1.0, 2317.6752836026126, 763.9984530766586),
(1.0, 2329.424714229405, 851.9824595979503),
(1.0, 2438.439804695262, 3244.4834643881113),
(1.0, 2420.7388542963886, 3385.5640099626403),
(1.0, 2623.1869865740236, 2399.7963666630476),
(1.0, 2675.525004799386, 812.9451430216932),
(1.0, 2657.7694468189034, 948.9477347661497),
(1.0, 2737.3965619442797, 977.0773562537048),
(1.0, 2758.0705197325856, 1038.3683416001725),
(1.0, 2759.6937973617737, 669.6233511086164),
(1.0, 2836.7935110202584, 2354.228267421443),
(1.0, 2812.892162448116, 961.1602506714414),
(1.0, 428.61883088048717, 1787.5984283811215),
(1.0, 125.98787227509979, 2312.208090267117),
(2.0, 337.10235964928484, 3008.4183779818836),
(2.0, 172.18748968333261, 1650.019251987316),
(2.0, 79.05630596448627, 2285.681286993474),
(2.0, 120.59550561797752, 583.0968845760981),
(2.0, 341.2470033058268, 2182.697769197769),
(2.0, 311.12108963690093, 318.82918379131144),
(2.0, 545.8929083744167, 1095.6975712707547),
(2.0, 429.5308275144852, 221.87297578368742),
(2.0, 448.40031011758623, 337.2594650471637),
(2.0, 500.984451750145, 164.64977760587894),
(2.0, 636.0321566075593, 2195.677728973483),
(2.0, 716.7293186080433, 3460.95140654303),
(2.0, 845.8828675783573, 602.3421387921516),
(2.0, 1535.26017827827, 3127.550027046247),
(2.0, 1158.3666919050597, 3758.0845047239686),
(2.0, 1464.3599847675866, 1709.9265908748323),
(2.0, 1395.8473628318584, 96.62223008849557),
(2.0, 1417.4062823610632, 2615.9252675181224),
(2.0, 1487.533211456429, 2615.8653260207193),
(2.0, 1645.2234663632826, 502.6575851022424),
(2.0, 1609.6065007403229, 898.9125008813368),
(2.0, 1855.3184030907921, 1815.9022279459111),
(2.0, 1870.8715660298424, 1979.6834472179612),
(2.0, 2004.820143884892, 975.848201438849),
(2.0, 2152.2386336712934, 1845.8399522879715),
(2.0, 2064.784335981839, 474.4242905788876),
(2.0, 2101.247747747748, 532.5915915915916),
(2.0, 2378.1860178079924, 1098.1421760767212),
(2.0, 2279.763305997749, 736.8652194886638),
(2.0, 2292.220562217417, 828.8089247100452),
(2.0, 2475.482818773363, 3265.9790945590476),
(2.0, 2460.545879086205, 3408.4455383061972),
(2.0, 2587.7001645639057, 2374.7207167672336),
(2.0, 2777.0123269458654, 733.5197693574959),
(2.0, 2623.891525049658, 918.2103288457295),
(2.0, 2707.5055488701696, 948.1838481080358),
(2.0, 2728.9928986442865, 1012.8095545513235),
(2.0, 2801.1314431698643, 2329.664604518359),
(2.0, 2777.031130820399, 920.7952993348115),
(2.0, 2866.286997193639, 3064.177923292797),
(2.0, 2909.7604712041884, 1317.9070680628272),
(3.0, 157.26388004449086, 1633.8971530944073),
(3.0, 63.67491895078102, 2270.573312702623),
(3.0, 106.90561963190184, 566.6600245398773),
(3.0, 367.2937136901629, 3023.2236402191747),
(3.0, 324.9559239582667, 2168.772604493375),
(3.0, 309.9233307424951, 305.357814310226),
(3.0, 529.6920537916766, 1079.0594923211586),
(3.0, 414.9144941240038, 209.41901931649332),
(3.0, 486.1743528597254, 147.9357282972422),
(3.0, 620.9823211314476, 2181.4336522462563),
(3.0, 747.0673195115955, 3476.260099975416),
(3.0, 830.2220659995038, 587.1107435282441),
(3.0, 1564.271350026497, 3143.328428533576),
(3.0, 1447.2135826080168, 1694.8505366691386),
(3.0, 1379.2560933268524, 82.5819734740643),
(3.0, 1414.0898379970545, 2637.6224840451646),
(3.0, 1458.7942639742464, 2632.1287679250804),
(3.0, 1517.2141613464887, 2632.6935577481136),
(3.0, 1628.7177629761502, 486.4310598852021),
(3.0, 1592.5086746302616, 884.4677901023891),
(3.0, 1846.0530963067265, 1798.3329519786441),
(3.0, 1854.721832632071, 1959.0901622921258),
(3.0, 2140.705506419401, 1827.9028408396168),
(3.0, 2046.6188630490956, 459.6313522825151),
(3.0, 2100.54031783402, 3798.304787129684),
(3.0, 2089.9236276849642, 518.0429594272076),
(3.0, 2362.4917481532502, 1082.4142175546672),
(3.0, 2263.1660548213413, 717.3157427802252),
(3.0, 2275.2605606758834, 812.102534562212),
(3.0, 2502.8201961695036, 3282.5997377120843),
(3.0, 2492.2876712328766, 3424.5829975825945),
(3.0, 2572.046443965517, 2362.7854166666666),
(3.0, 2618.7545978589073, 753.6802834826442),
(3.0, 2600.3548616882345, 902.7820254066247),
(3.0, 2689.188485206103, 918.132850037933),
(3.0, 2822.238917763738, 692.1082028778023),
(3.0, 2713.429400386847, 994.9756838905776),
(3.0, 2785.0664297628546, 2313.4155002779994),
(3.0, 2769.067081895463, 901.3574614931404),
(3.0, 2895.185851318945, 3078.8379450285925),
(3.0, 2894.081445993031, 1303.1498257839721),
(4.0, 323.2980014095852, 2995.5082158679015),
(4.0, 189.00062107109585, 1661.3407749960134),
(4.0, 94.69584245076587, 2304.1963718500742),
(4.0, 138.99071904003, 594.3969250960907),
(4.0, 356.0687429605538, 2199.471494197598),
(4.0, 339.94278226043934, 335.9263649213735),
(4.0, 561.0918771562345, 1107.1995040660424),
(4.0, 444.95715341049004, 240.15735040630386),
(4.0, 515.9579145492189, 174.8035761340109),
(4.0, 521.9724964739069, 361.19340620592385),
(4.0, 652.1437428698973, 2213.3314815733347),
(4.0, 703.7371733205066, 3448.0016033349366),
(4.0, 863.0894711992446, 615.1586402266289),
(4.0, 1519.4442919707187, 3125.3200876862925),
(4.0, 1477.601623813873, 1724.884220058513),
(4.0, 1413.3926438653637, 112.9267779587405),
(4.0, 1473.6105100463678, 2606.236991241628),
(4.0, 1656.7474928951754, 515.9234802208213),
(4.0, 1621.8129663859793, 915.8049565276922),
(4.0, 1876.2702648647105, 1826.619646275608),
(4.0, 1891.8117573483428, 1991.976235146967),
(4.0, 2173.9414860981046, 1854.8787176671942),
(4.0, 2056.983448913546, 3768.833934350439),
(4.0, 2075.197315150224, 487.019603665033),
(4.0, 2117.8430769230768, 548.3425641025641),
(4.0, 2393.594353853348, 1111.8233033653628),
(4.0, 2292.022869692533, 742.7756954612006),
(4.0, 2304.9634436117713, 839.7576311460427),
(4.0, 2459.5847136835887, 3257.187065424575),
(4.0, 2448.2789465232054, 3396.4231572185645),
(4.0, 2601.3766628260187, 2390.8952201389616),
(4.0, 2652.0092467353616, 780.6522145439343),
(4.0, 2645.946173800259, 919.6041319251436),
(4.0, 2736.3547049441786, 956.7454545454545),
(4.0, 2824.591325417979, 814.5812454567482),
(4.0, 2752.9186953438902, 1025.5029543843063),
(4.0, 2815.841896499733, 2343.718099788917),
(4.0, 2799.1525048681183, 923.3706850770047),
(4.0, 2876.0865684798177, 644.4555588202887),
(4.0, 2849.6915052160953, 3051.0775894187777),
(4.0, 2926.4961904761903, 1333.1619047619047),
(5.0, 342.7083988173585, 3010.581102783726),
(5.0, 172.66986024652678, 1644.3937337675723),
(5.0, 79.33176646910553, 2287.3308808501943),
(5.0, 123.69916165562041, 579.1842163016285),
(5.0, 341.2068281113469, 2186.740931219573),
(5.0, 324.24324719150366, 322.68505397864226),
(5.0, 545.4950787372192, 1091.116850511232),
(5.0, 429.0323831242873, 226.10558722919043),
(5.0, 499.3247200058561, 158.63070053436792),
(5.0, 506.5545222465354, 352.4772064186725),
(5.0, 637.0303665431858, 2199.3088808734647),
(5.0, 719.7670217505772, 3464.994248450727),
(5.0, 845.3587260761026, 601.5611619638399),
(5.0, 1536.9222192362013, 3135.167320414663),
(5.0, 1462.9025670193, 1712.0848974329806),
(5.0, 1397.2887252583935, 96.53935013173006),
(5.0, 1389.9905660377358, 2628.7861635220124),
(5.0, 1433.833930046819, 2622.1148443954835),
(5.0, 1491.3909811694748, 2623.4930624380577),
(5.0, 1640.366485013624, 500.02659137914054),
(5.0, 1603.046150785757, 902.7337709700948),
(5.0, 1874.4067119887775, 1811.3451494550557),
(5.0, 2163.080461618503, 1840.8093648015893),
(5.0, 2074.5243486073673, 3782.4163522012577),
(5.0, 2056.7912423625253, 470.181466395112),
(5.0, 2105.2317497103127, 524.8532251834686),
(5.0, 2375.7653644855686, 1097.8645923046913),
(5.0, 2274.869907197827, 725.5888411045722),
(5.0, 2286.78021978022, 823.1176669484362),
(5.0, 2477.5736712443654, 3273.0428766118043),
(5.0, 2461.705685618729, 3413.5393416651996),
(5.0, 2585.4316079444975, 2374.4842538430144),
(5.0, 2722.678243517861, 781.2931102024827),
(5.0, 2630.109522052039, 902.0422587193209),
(5.0, 2721.1595322390303, 938.8852054500591),
(5.0, 2739.7317179655097, 1009.6524776249727),
(5.0, 2799.6063686385432, 2328.704373190728),
(5.0, 2783.330575692964, 904.1339019189766),
(5.0, 2858.7568411552347, 622.506119133574),
(5.0, 2866.938534507792, 3064.189139483109),
(5.0, 2910.775520077407, 1317.6782776971456)]

因此返回值可以是：[（coordinate0，coordinate1，coordinate2，coordinate3，coordinate4，coordinate5），（coordinate0，coordinate1….]

最小示例，其中坐标在切片中不变：

^{pr2}$

返回

coordinates=[[(0,1,1),(1,1,1),(2,1,1),(3,1,1),(4,1,1),[(0,2,2),(1,2,2),(2,2,2),(3,2,2),(4,2,2)]

也有可能在切片中坐标的数目不一样

Answer 1

下面是一些代码，从一个切片到下一个切片查找最近的点：

import numpy as np
from scipy.spatial import KDTree
import matplotlib.pylab as plt

def get_points_on_slice(i):
    return slices[ slices[:, 0] == i ][:, (1, 2)]

# Look for the nearest point slice by slice:
n_last_slice = int( np.max(slices[:, 0]) )
start_points = get_points_on_slice(0)
path_through = np.arange(start_points.shape[0]).reshape(1, -1)

for i in range(1, n_last_slice+1):

    get_nearest = KDTree(get_points_on_slice(i))

    previous_points = get_points_on_slice(i-1)[path_through[-1, :]]
    distance, idx_nearest = get_nearest.query(previous_points)

    path_through = np.vstack((path_through, idx_nearest))

# `path_through` is a (nbre slices x nbr points on the first slice) array
# with the index of the nearest point on the corresponding slice

# Graph
plt.figure(figsize=(6, 6))
for path_idx in path_through.T:
    path_coords = [get_points_on_slice(i)[idx] for i, idx in enumerate(path_idx)]

    plt.plot(*zip(*path_coords), 'x-', alpha=.8);

plt.axis('equal');

结果是：