如何对xy坐标进行排序得到连续多边形

Question

我有两个(x, y)坐标的数组：

xx = np.array([513, 512, 508, 507, 506, 505, 504, 503, 502, 501, 500, 498, 497,
       492, 492, 488, 487, 482, 482, 480, 480, 479, 479, 478, 478, 477,
       477, 476, 476, 475, 475, 474, 474, 473, 473, 472, 472, 471, 471,
       470, 470, 469, 469, 468, 468, 467, 467, 466, 466, 465, 465, 464,
       464, 462, 462, 461, 461, 460, 460, 459, 459, 458, 458, 457, 457,
       455, 455, 454, 454, 453, 453, 452, 452, 451, 451, 450, 450, 449,
       449, 448, 448, 447, 447, 446, 446, 445, 445, 444, 444, 443, 443,
       442, 442, 441, 441, 440, 440, 439, 439, 438, 438, 437, 437, 436,
       436, 437, 437, 436, 436, 437, 437, 436, 436, 437, 437, 438, 438,
       439, 439, 440, 440, 441, 441, 443, 443, 448, 449, 451, 452, 453,
       454, 455, 456, 457, 458, 459, 463, 464, 474, 475, 479, 480, 483,
       484, 488, 489, 490, 491, 498, 499, 503, 504, 515, 516, 521, 522,
       532, 533, 538, 539, 549, 550, 561, 562, 565, 566, 567, 568, 569,
       570, 571, 572, 573, 574, 578, 579, 583, 584, 585, 586, 587, 588,
       589, 590, 594, 595, 605, 606, 607, 611, 612, 619, 620, 621, 622,
       623, 624, 628, 629, 632, 633, 634, 635, 636, 637, 638, 639, 643,
       644, 654, 655, 659, 660, 661, 662, 663, 664, 665, 666, 667, 669,
       670, 671, 682, 683, 687, 688, 689, 700, 701, 702, 703, 704, 705,
       706, 707, 708, 709, 713, 714, 724, 725, 729, 730, 731, 732, 733,
       734, 735, 736, 737, 739, 740, 745, 745, 747, 747, 748, 749, 751,
       752, 757, 757, 759, 759, 760, 760, 761, 761, 762, 762, 763, 763,
       764, 764, 763, 763, 762, 762, 761, 761, 760, 760, 759, 759, 758,
       758, 757, 757, 756, 756, 755, 755, 753, 753, 748, 747, 744, 744,
       739, 738, 736, 735, 734, 733, 732, 731, 725, 724, 722, 721, 718,
       718, 713, 712, 710, 709, 708, 707, 706, 705, 704, 704, 699, 698,
       696, 695, 694, 693, 692, 691, 689, 689, 684, 683, 681, 680, 679,
       678, 677, 676, 675, 674, 673, 672, 667, 666, 664, 663, 662, 661,
       660, 659, 658, 657, 656, 652, 651, 650, 649, 648, 647, 646, 645,
       644, 641, 640, 638, 637, 636, 635, 634, 633, 629, 628, 626, 625,
       624, 623, 622, 621, 614, 613, 611, 610, 609, 608, 607, 606, 600,
       599, 597, 596, 595, 594, 593, 592, 591, 590, 589, 587, 585, 584,
       582, 581, 580, 579, 578, 577, 576, 575, 574, 571, 570, 569, 567,
       566, 565, 564, 563, 562, 561, 560, 559, 556, 553, 552, 550, 549,
       548, 547, 546, 545, 544, 544, 539, 538, 536, 535, 534, 533, 532,
       531, 530, 529, 528, 524, 523, 658, 659, 669, 670, 674, 675, 676,
       677, 678, 679, 680, 681, 682, 684, 685, 691, 691, 693, 693, 694,
       694, 695, 695, 696, 696, 697, 697, 698, 698, 697, 697, 696, 696,
       695, 695, 694, 694, 693, 693, 691, 691, 685, 684, 682, 681, 680,
       679, 678, 677, 676, 675, 674, 670, 669, 659, 658, 654, 653, 652,
       651, 650, 649, 648, 647, 646, 644, 643, 637, 637, 635, 635, 634,
       634, 633, 633, 632, 632, 631, 631, 630, 630, 631, 631, 632, 632,
       633, 633, 634, 634, 635, 635, 637, 637, 643, 644, 646, 647, 648,
       649, 650, 651, 652, 653, 654, 518, 519, 529, 530, 534, 535, 536,
       537, 538, 539, 540, 541, 542, 544, 545, 551, 551, 553, 553, 554,
       554, 555, 555, 556, 556, 557, 557, 558, 562, 563, 564, 565, 566,
       567, 568, 569, 570, 572, 573, 575, 576, 577, 578, 579, 580, 581,
       582, 583, 584, 586, 587, 592, 593, 595, 596, 602, 602, 604, 604,
       605, 605, 606, 606, 607, 607, 608, 608, 609, 609, 610, 610, 611,
       611, 610, 610, 609, 609, 608, 608, 607, 607, 606, 606, 604, 604,
       598, 597, 595, 594, 593, 592, 591, 590, 589, 588, 587, 583, 582,
       572, 571, 570, 566, 565, 559, 558, 554, 553, 546, 545, 544, 543,
       542, 541, 537, 536, 526, 525, 521, 520, 519, 518, 517, 516, 515,
       514, 513, 511, 510, 504, 504, 497, 497, 495, 495, 494, 494, 493,
       493, 492, 492, 491, 491, 490, 490, 491, 491, 492, 492, 493, 493,
       494, 494, 495, 495, 496, 496, 495, 495, 494, 494, 493, 493, 492,
       492, 491, 491, 490, 490, 491, 491, 492, 492, 493, 493, 494, 494,
       495, 495, 497, 497, 503, 504, 506, 507, 508, 509, 510, 511, 512,
       513, 514])

yy = np.array([168, 169, 169, 170, 170, 171, 171, 172, 172, 173, 173, 175, 175,
       180, 181, 185, 185, 190, 191, 193, 194, 195, 196, 197, 198, 199,
       200, 201, 205, 206, 209, 210, 211, 212, 213, 214, 215, 216, 220,
       221, 223, 224, 225, 226, 227, 228, 229, 230, 231, 232, 235, 236,
       237, 239, 240, 241, 242, 243, 244, 245, 246, 247, 251, 252, 253,
       255, 256, 257, 258, 259, 260, 261, 262, 263, 267, 268, 270, 271,
       272, 273, 274, 275, 276, 277, 278, 279, 283, 284, 295, 296, 300,
       301, 311, 312, 316, 317, 328, 329, 333, 334, 345, 346, 350, 351,
       361, 362, 367, 368, 378, 379, 384, 385, 395, 396, 400, 401, 402,
       403, 404, 405, 406, 407, 408, 410, 411, 416, 416, 418, 418, 419,
       419, 420, 420, 421, 421, 422, 422, 423, 423, 422, 422, 421, 421,
       420, 420, 419, 419, 418, 418, 417, 417, 416, 416, 415, 415, 416,
       416, 415, 415, 416, 416, 415, 415, 414, 414, 413, 413, 412, 412,
       411, 411, 410, 410, 409, 409, 408, 408, 407, 407, 406, 406, 405,
       405, 404, 404, 403, 403, 404, 403, 403, 402, 402, 401, 401, 400,
       400, 399, 399, 398, 398, 397, 397, 396, 396, 395, 395, 394, 394,
       393, 393, 394, 394, 395, 395, 396, 396, 397, 397, 398, 398, 400,
       400, 399, 399, 398, 398, 397, 398, 398, 399, 399, 400, 400, 401,
       401, 402, 402, 403, 403, 404, 404, 403, 403, 402, 402, 401, 401,
       400, 400, 399, 399, 397, 397, 392, 391, 389, 388, 387, 387, 385,
       385, 380, 379, 377, 376, 375, 374, 373, 372, 371, 370, 369, 365,
       364, 354, 353, 349, 348, 347, 346, 345, 344, 337, 336, 332, 331,
       330, 329, 328, 327, 326, 325, 324, 322, 321, 316, 316, 313, 312,
       307, 307, 305, 305, 304, 304, 303, 303, 297, 297, 295, 295, 292,
       291, 286, 286, 284, 284, 283, 283, 282, 282, 281, 280, 275, 275,
       273, 273, 272, 272, 271, 271, 269, 268, 263, 263, 261, 261, 260,
       260, 259, 259, 258, 258, 257, 257, 252, 252, 250, 250, 249, 249,
       248, 248, 247, 247, 246, 246, 245, 245, 244, 244, 243, 243, 242,
       242, 239, 239, 237, 237, 236, 236, 235, 235, 231, 231, 229, 229,
       228, 228, 227, 227, 220, 220, 218, 218, 217, 217, 216, 216, 210,
       210, 208, 208, 207, 207, 206, 206, 205, 205, 204, 204, 202, 202,
       200, 200, 199, 199, 198, 198, 197, 197, 196, 196, 195, 195, 193,
       193, 192, 192, 191, 191, 190, 190, 189, 189, 186, 186, 184, 184,
       183, 183, 182, 182, 181, 180, 175, 175, 173, 173, 172, 172, 171,
       171, 170, 170, 169, 169, 168, 316, 315, 315, 316, 316, 317, 317,
       318, 318, 319, 319, 320, 320, 322, 322, 328, 329, 331, 332, 333,
       334, 335, 336, 337, 338, 339, 343, 344, 354, 355, 359, 360, 361,
       362, 363, 364, 365, 366, 367, 369, 370, 376, 376, 378, 378, 379,
       379, 380, 380, 381, 381, 382, 382, 383, 383, 382, 382, 381, 381,
       380, 380, 379, 379, 378, 378, 376, 376, 370, 369, 367, 366, 365,
       364, 363, 362, 361, 360, 359, 355, 354, 344, 343, 339, 338, 337,
       336, 335, 334, 333, 332, 331, 329, 328, 322, 322, 320, 320, 319,
       319, 318, 318, 317, 317, 316, 217, 216, 216, 217, 217, 218, 218,
       219, 219, 220, 220, 221, 221, 223, 223, 229, 230, 232, 233, 234,
       235, 236, 237, 238, 239, 240, 242, 243, 243, 244, 244, 245, 245,
       246, 246, 247, 247, 249, 249, 251, 251, 252, 252, 253, 253, 254,
       254, 255, 255, 257, 257, 262, 262, 264, 264, 270, 271, 273, 274,
       275, 276, 277, 278, 279, 280, 281, 285, 286, 290, 291, 295, 296,
       306, 307, 311, 312, 313, 314, 315, 316, 317, 318, 319, 321, 322,
       328, 328, 330, 330, 331, 331, 332, 332, 333, 333, 334, 334, 335,
       335, 334, 335, 335, 336, 336, 337, 337, 338, 338, 339, 339, 340,
       340, 341, 341, 342, 342, 341, 341, 340, 340, 339, 339, 338, 338,
       337, 337, 335, 335, 329, 328, 321, 320, 318, 317, 316, 315, 314,
       313, 312, 311, 310, 306, 305, 295, 294, 290, 289, 288, 287, 279,
       278, 274, 273, 272, 271, 269, 268, 267, 266, 265, 264, 263, 262,
       261, 260, 256, 255, 245, 244, 240, 239, 238, 237, 236, 235, 234,
       233, 232, 230, 229, 223, 223, 221, 221, 220, 220, 219, 219, 218,
       218, 217])

实际上，它看起来是这样的：

我的问题是：我需要一个同时考虑两个内孔的多边形（坐标）。使用3个多边形（外轮廓和内轮廓）在我的情况下不起作用。我的想法是使用最接近的欧几里德距离对（x，y）坐标进行排序。但是，这种方法无法从一个轮廓跳到下一个轮廓。此处用红色勾勒出的是所需的输出（为了直观起见，将间隙画得更大）：

理想情况下，面积（绿色标记）应最大化。因此，从一个轮廓跳下的标准是基于闭合距离，以避免面积损失（见下文）

---

更新： 感谢kaya3与MST的建议：

from __future__ import print_function
import numpy as np
import matplotlib.pylab as plt
import mistree as mist


mst = mist.GetMST(x=xx, y=yy)
d, l, b, s, l_index, b_index = mst.get_stats(include_index=True)

plt.figure(figsize=(15, 15))

# plotting nodes:
plt.scatter(xx, yy, s=10, color='r')

# plotting MST edges:
plt.plot([xx[l_index[0]], xx[l_index[1]]],
         [yy[l_index[0]], yy[l_index[1]]],
         color='k')

plt.xlim(0, 700)
plt.ylim(0., 700)
plt.xlabel(r'$X$', size=16)
plt.ylabel(r'$Y$', size=16)
plt.tight_layout()
plt.show()

输出不正确（应用MST后并非所有轮廓都连接）：

Answer 1

Thus, the criteria to jump from one contour is based on the closed distance ...

这是Travelling Salesman Problem。这是一个研究得很好的NP完全问题，目前还没有一个既有效又能给出精确答案的已知解。但是，对于您的情况，应该有一个“足够好”的答案，因此您可以考虑heuristic algorithms。有许多众所周知的启发法，你可以通过维基百科或其他来源找到有关的信息。你知道吗

我认为对于您的用例来说，一个好的解决方案应该是从一个minimum spanning tree（MST）开始，它应该看起来像您的解决方案，除了只有一条边桥接独立的部分，而不是两个。从那里，你应该能够添加第二条边到每一个桥去相反的方向，并连接在多边形部分的树没有完成的周期造成的任何小差距。你知道吗

例如，下图中的红线表示MST，而黄线则是需要添加的边，以使其成为一个循环。希望很明显，找到MST可以让这个问题简单得多。你知道吗

Answer 2

这是一个难题。我认为首先将三个等高线连接成三个独立的闭合多边形是有意义的，一个是外部的P，两个是内部的A（大，左）和B（小，右）。然后才考虑连接内部多边形的最短“桥” 或者相互连接（如您绘制的连接到A的B），或者连接到外部的P。请注意，如果使用连接B到A或P的最短线段，它将连接到P（因为B曲线非常接近P）。而且，你展示的A和P之间的桥不是最短的桥： 相反，西北桥要短一些。你知道吗