时间戳

首页 > 解决方案 > 顺时针对多边形顶点进行排序

python - 顺时针对多边形顶点进行排序

问题描述

我正在从事一个涉及将多边形转换为梯形的项目。我正在使用此处所介绍的 seidel.py 版本。该软件本质上获取多边形的坐标，并使用一种算法对其进行梯形分解，该算法找到从构建原始多边形的顶点发出的垂直线的交点。

你可以在这里找到我的版本：Poly2Trap for Python 3.6.7。

我想要实现的是：

发生了什么：

我需要您的帮助是： 如果您知道任何其他对复杂多边形的顶点进行排序的方法，因为我认为这是我所缺乏的。

这是我的结果：

附加信息：

我想在未来使用具有几百个顶点范围的复杂多边形，这就是我避免使用凸包的原因。

这里，一个点是一个具有 x 和 y 坐标的元组。并且多边形的所有顶点都存储在元组列表中。

poly_coords = [(x,y),]

最小、完整和可验证的示例：poly2trap.py

import numpy as np
import matplotlib.pyplot as plt

original_poly_coords = [(235.04275999999999, 739.07534999999996),
(218.13066000000001, 719.73902999999996),
(218.15215000000001, 709.96821),
(218.17362, 700.19740000000002),
(243.15215000000001, 685.27858000000003),
(268.13065, 670.35974999999996),
(268.13065, 660.81429000000003),
(268.13065, 651.26882999999998),
(314.55921999999998, 651.26882999999998),
(360.98779000000002, 651.26882999999998),
(360.98683999999997, 666.44740000000002),
(360.98046561000007, 669.27438118000009),
(360.96234088000011,672.68539864000013),
(360.93345946999995, 676.58895225999993),
(360.89481504000003, 680.89354191999996),
(360.84740125000002, 685.50766749999991),
(360.79221175999999, 690.33982888000003),
(360.73024022999999, 695.29852593999999),
(360.66248032000004, 700.29225856000005),
(360.58992569000003, 705.22952662000012),
(360.51357000000002, 710.01882999999998),
(360.04131999999998, 738.41168000000005),
(310.51454999999999, 738.41168000000005),
(260.98779999999999, 738.41168000000005),
(260.98779999999999, 748.41168000000005),
(260.98779999999999, 758.41168000000005),
(256.47133000000002, 758.41168000000005),
(251.95484999999999, 758.41168000000005),
(235.04275999999999, 739.07534999999996)
]

#After performing triangulation
coords_after_triangulation = [(257.22974168, 758.41168), (361.63905883, 651.2688300000154), 
(360.98046561000007, 669.2743811800001), (361.22358883000004, 651.26883), (361.29515521662, 651.26883),
(243.15215, 685.27858), (243.83742858, 685.27858), (361.36277257856005, 651.26883), 
(361.42553875594,651.26883), (361.48255158887997, 651.26883), (361.53290891750004, 651.26883),
(261.72621168, 738.41168), (251.95485, 758.41168), (261.72621168, 738.4116799999902),
(361.53290891750004, 685.5076675000018), (361.42553875594, 695.2985259399975),
(361.42553875594, 695.2985259400011), (315.21048883, 651.26883), (360.98684, 666.4474),
(360.84740125, 685.5076674999999), (361.57570858192, 680.8935419200061),
(360.9623408800001, 672.6853986400001), (361.57570858192, 680.8935419199988), 
(361.48255158887997, 690.3398288800017), (361.64973999118007, 662.6631410694681), 
(311.25296168, 738.41168), (268.80100975, 738.41168), (315.21048883, 738.41168), 
(218.13066, 719.73903), (218.86211821, 719.7524137325041), (218.8738174, 719.7657746356965),
(268.13065, 660.81429), (268.79146429, 660.8142900000094), (218.85039903, 719.73903), 
(218.85039903, 719.739029999997), (360.98779, 651.26883), (360.77973168, 651.26883), 
(218.17362, 700.1974), (218.8738174, 700.1974000000046), (218.8738174, 700.1974), 
(314.55922, 651.26883), (243.83742858, 739.07535), (361.63905883, 671.7505493924255), 
(360.93345946999995, 676.5889522599999), (360.04132, 738.41168), 
(360.73024023, 695.29852594), (360.77973168, 738.4116800000011), 
(360.77973168, 738.41168), (360.51357, 710.01883), (261.72621168, 674.5878176386889), 
(361.65328739999995, 666.4474000000046), (361.36277257856005, 700.292258559999), 
(218.15215, 709.96821), (218.86211821, 709.9682099999918), (218.86211821, 709.9682100000209), 
(268.13065, 670.35975), (268.80100975, 670.3597500000615), (268.80100975, 670.35975), 
(361.22358883000004, 710.0188300000009), (361.29515521662, 705.2295266200017), 
(361.57570858192, 651.26883), (361.6100484222599, 651.26883), 
(361.6350262786401, 651.26883), (360.89481504, 680.89354192), 
(260.9878, 748.41168), (361.63905883, 651.26883), (311.25296168, 651.26883), 
(252.71326168, 679.9741709800953), (361.6350262786401, 672.6853986399947), 
(310.51455, 738.41168), (235.04276, 739.07535), (235.78183535, 739.07535), 
(243.83742858, 748.2751425044893), (235.78183535, 690.0927851454428), (257.22974168, 677.2750150833695), 
(360.79221176, 690.33982888), (260.9878, 758.41168), (360.58992569000003, 705.2295266200001), 
(261.73621168, 748.4116799999902), (252.71326168, 758.41168), (268.13065, 651.26883), 
(360.66248032000004, 700.29225856), (261.74621168, 758.4116799999902), (261.74621168, 758.41168), 
(268.79146429, 651.26883), (268.80100975, 651.26883), (268.78191883, 651.2688300000154), 
(268.78191883, 651.26883), (361.6100484222599, 676.5889522599973), (261.73621168, 758.41168), 
(261.72621168, 758.41168), (256.47133, 758.41168), (361.64973999118007, 669.2743811799883), 
(361.64973999118007, 669.2743811800028), (260.9878, 738.41168),(257.22974168, 758.41168)]


def ccw_sort(p):
    """Sort given polygon points in CCW order"""
    p = np.array(p)
    mean = np.mean(p,axis=0)
    d = p-mean
    s = np.arctan2(d[:,0], d[:,1])
    return p[np.argsort(s),:]

#sort poly after triangulation
sorted_poly_coords = ccw_sort(coords_after_triangulation)

#plot
#How it should look like:
fig,ax = plt.subplots()    
xa = [i[0] for i in original_poly_coords[:]]
ya = [i[1] for i in original_poly_coords[:]]
ax.plot(xa,ya, color = 'b')

#How it looks like:
fig,bx = plt.subplots()
xb = [i[0] for i in sorted_poly_coords[:]]
yb = [i[1] for i in sorted_poly_coords[:]]
bx.plot(xb,yb, color='r')

plt.show()

任何帮助表示赞赏。

标签： pythonpolygoncomputational-geometry

解决方案

推荐阅读