Я работаю над проектом, который включает в себя преобразование многоугольника в трапеции. Я использую версию seidel.py, как указано здесь . Это программное обеспечение по существу берет координаты многоугольника и выполняет трапецеидальное разложение на нем, используя алгоритм, который находит пересечения вертикальных линий, исходящих из вершин, образующих исходный многоугольник.
Вы можете найти мою версию этого здесь: Poly2Trap
для Python 3.6.7.
Я пытаюсь достичь:
- Полигон ввода
- разложить многоугольник, используя seidel.py
- извлечение вновь добавленных вершин разложенного многоугольника
- Создать новый список вершин, добавив новые вершины, созданные во время триангуляции, в исходный список вершин
- Нарисуйте многоугольник с новым списком вершин
Что происходит:
- Метод разложения работает и выводит список трапеций. Каждая из этих трапеций имеет три или четыре вершины, некоторые из которых уже определены в исходном многоугольнике.
- После получения списка всех трапеций я объединяю все в список вершин (все трапеции и исходный многоугольник) и удаляю дубликаты.
- На данный момент у меня остался набор различных вершин, которые я хочу снова изобразить как многоугольник.
- Для этого я использую метод угловой сортировки , который берет центроид многоугольника и сортирует вершины, вычисляя углы от вершины до центроида.
- Когда я строю и сравниваю, результирующий многоугольник не такой, как ожидалось.
Мне нужна ваша помощь:
Если вам известен какой-либо другой метод сортировки вершин сложного многоугольника, потому что я думаю, что этого мне не хватает.
Вот мои результаты:
Дополнительная информация:
В будущем я хочу работать со сложными полигонами с вершинами в диапазоне от нескольких сотен, и поэтому я избегаю использования выпуклой оболочки.
Здесь точка - это кортеж с координатами 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()
Любая помощь приветствуется.