python - 如何对 xy 坐标进行排序以获得连续多边形
问题描述
我有两个(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()
解决方案
因此,从一个轮廓跳跃的标准是基于闭合距离......
这就是旅行商问题。这是一个经过充分研究的 NP 完全问题,没有已知的解决方案既有效又能给出准确的答案。但是,对于您的情况,应该使用“足够好”的答案,因此您可以考虑启发式算法。您可以通过 Wikipedia 或其他来源找到许多著名的启发式方法。
我认为您的用例的一个好的解决方案是从最小生成树(MST) 开始,它应该看起来像您的解决方案,除了只有一个边缘桥接单独的部分而不是两个。从那里,您应该能够为每座桥添加第二条边,并连接由于树木未完成循环而导致的多边形部分中的任何小间隙。
对于您的示例,下图中的红线显示 MST,黄线是您需要添加以使其成为循环的边缘。希望很明显,找到 MST 会使这个问题变得简单得多。
推荐阅读
- r - 在 Shiny renderDataTable() 中使用 formattable()
- python-3.x - 我可以在 python 中扫描没有“限制”的 DynamoDB 表吗?
- java - 如何在方法中传递和模拟对象的 var args
- angular - 在 macOS High Sierra 上安装 Angular 失败
- javascript - JS计算错误命中来确定百分比
- c++ - 在命令提示符下使用 GCC 构建 WxWidgets 失败
- php - 使用 HttpClient 发送多个文件
- unix - 在卸载的挂载点下创建的文件
- r - 在 R 中使用 dplyr 和lazyeval 函数
- html - 法罗小话。html文件模板中的copyReplaceAll到静态页面文件