Sorting a polygon vertices clockwise2019 Community Moderator Electionhow to use matplotlib PATH to draw polygonSorting coordinates to create a polygon gives messy resultsHow do I sort a list of dictionaries by a value of the dictionary?How do I sort a dictionary by value?How to determine if a list of polygon points are in clockwise order?Split weakly-simple-polygon to true simple polygon or polygonsHow to compute the center of a polygon in 2D and 3D spaceLocating the centroid (center of mass) of spherical polygonsMonotone polygon triangulation with collinear, vertical edge segmentsHow to draw spokes from the center of a polygon to it's boundary using RDraw moving polygons with matplotlibfurthest point inside polygon with orthogonal edges (convex or concave or having holes)
Is there a way to make cleveref distinguish two environments with the same counter?
Has a sovereign Communist government ever run, and conceded loss, on a fair election?
How to write a chaotic neutral protagonist and prevent my readers from thinking they are evil?
Smooth vector fields on a surface modulo diffeomorphisms
Was it really inappropriate to write a pull request for the company I interviewed with?
The (Easy) Road to Code
Create chunks from an array
How to install round brake pads
"If + would" conditional in present perfect tense
PTIJ: Who was the sixth set of priestly clothes for?
Does an unused member variable take up memory?
Can I negotiate a patent idea for a raise, under French law?
Is it a Cyclops number? "Nobody" knows!
Can the Witch Sight warlock invocation see through the Mirror Image spell?
How to copy the rest of lines of a file to another file
Under what conditions can the right to be silence be revoked in the USA?
Why does Central Limit Theorem break down in my simulation?
How can I portion out frozen cookie dough?
Too soon for a plot twist?
Trocar background-image com delay via jQuery
What would be the most expensive material to an intergalactic society?
What does *dead* mean in *What do you mean, dead?*?
Did Amazon pay $0 in taxes last year?
Rationale to prefer local variables over instance variables?
Sorting a polygon vertices clockwise
2019 Community Moderator Electionhow to use matplotlib PATH to draw polygonSorting coordinates to create a polygon gives messy resultsHow do I sort a list of dictionaries by a value of the dictionary?How do I sort a dictionary by value?How to determine if a list of polygon points are in clockwise order?Split weakly-simple-polygon to true simple polygon or polygonsHow to compute the center of a polygon in 2D and 3D spaceLocating the centroid (center of mass) of spherical polygonsMonotone polygon triangulation with collinear, vertical edge segmentsHow to draw spokes from the center of a polygon to it's boundary using RDraw moving polygons with matplotlibfurthest point inside polygon with orthogonal edges (convex or concave or having holes)
0
I am working on a project that involves conversion of polygon into trapezoids. I am using a version of seidel.py as featured here. This software essentially takes in coordinates of a polygon, and performs trapezoidal decomposition on it using an algorithm that finds the intersections of vertical lines eminating from the vertices building up the original polygon.
You can find my version of this here: Poly2Trap
for Python 3.6.7.
What I'm trying to achieve is:
- Input polygon
- decompose polygon using seidel.py
- extract decomposed polygon's newly added vertices
- Create new vertex list by adding new vertices created during triangulation to the original vertex list
- Draw a polygon with the new vertex list
What's happening:
- The decomposition method works and outputs a list of trapezoids. These trapezoids each have three or four vertices, some of which are already defined in the original polygon.
- After I get the list of all trapezoids, I combine all into a list of vertices (all trapezoids and original polygon) and remove duplicates.
- At this point, I am left with a set of distinct vertices which I want to portray as a polygon again.
- To achieve this, I am using angular sort method which takes the centroid of the polygon and sorts the vertices by calculating angles from the vertex to the centroid.
- When I plot and compare, the resultant polygon isn't as expected.
What I need your help with is:
If you know of any other method to sort vertices of a complex polygon because I think that's where I am lacking.
Here are my results:
- Output: Decomposed polygon into trapezoids of the seidel.py
- The results after sort and plot show that the sort fails
Additional info:
I want to work with complex polygons with vertices in the range of a few hundred in the future and that is why I am avoiding the use of convex hull.
Here, a point is a tuple with x and y coordinates. and all the vertices of the polygon are stored in a list of tuples.
poly_coords = [(x,y),]
Minimal, Complete, and Verifiable example:
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()
Any help is appreciated.
python polygon computational-geometry
asked Mar 6 at 22:23
ssohinssohin
11
New contributor
ssohin is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
|
show 9 more comments
0
I am working on a project that involves conversion of polygon into trapezoids. I am using a version of seidel.py as featured here. This software essentially takes in coordinates of a polygon, and performs trapezoidal decomposition on it using an algorithm that finds the intersections of vertical lines eminating from the vertices building up the original polygon.
You can find my version of this here: Poly2Trap
for Python 3.6.7.
What I'm trying to achieve is:
- Input polygon
- decompose polygon using seidel.py
- extract decomposed polygon's newly added vertices
- Create new vertex list by adding new vertices created during triangulation to the original vertex list
- Draw a polygon with the new vertex list
What's happening:
- The decomposition method works and outputs a list of trapezoids. These trapezoids each have three or four vertices, some of which are already defined in the original polygon.
- After I get the list of all trapezoids, I combine all into a list of vertices (all trapezoids and original polygon) and remove duplicates.
- At this point, I am left with a set of distinct vertices which I want to portray as a polygon again.
- To achieve this, I am using angular sort method which takes the centroid of the polygon and sorts the vertices by calculating angles from the vertex to the centroid.
- When I plot and compare, the resultant polygon isn't as expected.
What I need your help with is:
If you know of any other method to sort vertices of a complex polygon because I think that's where I am lacking.
Here are my results:
- Output: Decomposed polygon into trapezoids of the seidel.py
- The results after sort and plot show that the sort fails
Additional info:
I want to work with complex polygons with vertices in the range of a few hundred in the future and that is why I am avoiding the use of convex hull.
Here, a point is a tuple with x and y coordinates. and all the vertices of the polygon are stored in a list of tuples.
poly_coords = [(x,y),]
Minimal, Complete, and Verifiable example:
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()
Any help is appreciated.
python polygon computational-geometry
asked Mar 6 at 22:23
ssohinssohin
11
New contributor
ssohin is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
How do you want to sort them? Here are a few options for clockwise sorting math.stackexchange.com/questions/1018164/…, alternatively you could try something like triangulating your polygon first and then inheriting the order from triangulation. When talking about non-convex polygons, you have a non-unique notion of "clockwise", so solution will be context dependent.
– Juan Carlos Ramirez
Mar 6 at 22:34
Too many links, not enough information in the question itself; see stackoverflow.com/help/mcve.
– chepner
Mar 6 at 22:34
@JuanCarlosRamirez Thanks for your comment, I did come across that link when searching. Approach 1 mentioned here is what I had assumed would work the best for me which is similar to what was posted link I want to have the vertices ordered in a direction that would allow me to convert into a valid shapely polygon again. I did not consider inheriting the order from the triangulation though, thanks for the suggestion.
– ssohin
Mar 6 at 22:50
Edit a Minimal Complete Verifiable Example of your code into your question. See htps://www.stackoverflow.com/help/mcve
– barny
Mar 6 at 22:54
1
This really isn't minimal.
– chepner
Mar 6 at 23:18
|
show 9 more comments
0
0
0
1
I am working on a project that involves conversion of polygon into trapezoids. I am using a version of seidel.py as featured here. This software essentially takes in coordinates of a polygon, and performs trapezoidal decomposition on it using an algorithm that finds the intersections of vertical lines eminating from the vertices building up the original polygon.
You can find my version of this here: Poly2Trap
for Python 3.6.7.
What I'm trying to achieve is:
- Input polygon
- decompose polygon using seidel.py
- extract decomposed polygon's newly added vertices
- Create new vertex list by adding new vertices created during triangulation to the original vertex list
- Draw a polygon with the new vertex list
What's happening:
- The decomposition method works and outputs a list of trapezoids. These trapezoids each have three or four vertices, some of which are already defined in the original polygon.
- After I get the list of all trapezoids, I combine all into a list of vertices (all trapezoids and original polygon) and remove duplicates.
- At this point, I am left with a set of distinct vertices which I want to portray as a polygon again.
- To achieve this, I am using angular sort method which takes the centroid of the polygon and sorts the vertices by calculating angles from the vertex to the centroid.
- When I plot and compare, the resultant polygon isn't as expected.
What I need your help with is:
If you know of any other method to sort vertices of a complex polygon because I think that's where I am lacking.
Here are my results:
- Output: Decomposed polygon into trapezoids of the seidel.py
- The results after sort and plot show that the sort fails
Additional info:
I want to work with complex polygons with vertices in the range of a few hundred in the future and that is why I am avoiding the use of convex hull.
Here, a point is a tuple with x and y coordinates. and all the vertices of the polygon are stored in a list of tuples.
poly_coords = [(x,y),]
Minimal, Complete, and Verifiable example:
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()
Any help is appreciated.
python polygon computational-geometry
asked Mar 6 at 22:23
ssohinssohin
11
New contributor
ssohin is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
I am working on a project that involves conversion of polygon into trapezoids. I am using a version of seidel.py as featured here. This software essentially takes in coordinates of a polygon, and performs trapezoidal decomposition on it using an algorithm that finds the intersections of vertical lines eminating from the vertices building up the original polygon.
You can find my version of this here: Poly2Trap
for Python 3.6.7.
What I'm trying to achieve is:
- Input polygon
- decompose polygon using seidel.py
- extract decomposed polygon's newly added vertices
- Create new vertex list by adding new vertices created during triangulation to the original vertex list
- Draw a polygon with the new vertex list
What's happening:
- The decomposition method works and outputs a list of trapezoids. These trapezoids each have three or four vertices, some of which are already defined in the original polygon.
- After I get the list of all trapezoids, I combine all into a list of vertices (all trapezoids and original polygon) and remove duplicates.
- At this point, I am left with a set of distinct vertices which I want to portray as a polygon again.
- To achieve this, I am using angular sort method which takes the centroid of the polygon and sorts the vertices by calculating angles from the vertex to the centroid.
- When I plot and compare, the resultant polygon isn't as expected.
What I need your help with is:
If you know of any other method to sort vertices of a complex polygon because I think that's where I am lacking.
Here are my results:
- Output: Decomposed polygon into trapezoids of the seidel.py
- The results after sort and plot show that the sort fails
Additional info:
I want to work with complex polygons with vertices in the range of a few hundred in the future and that is why I am avoiding the use of convex hull.
Here, a point is a tuple with x and y coordinates. and all the vertices of the polygon are stored in a list of tuples.
poly_coords = [(x,y),]
Minimal, Complete, and Verifiable example:
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()
Any help is appreciated.
python polygon computational-geometry
python polygon computational-geometry
asked Mar 6 at 22:23
ssohinssohin
11
New contributor
ssohin is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked Mar 6 at 22:23
ssohinssohin
11
New contributor
ssohin is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 2 days ago
ssohin
asked Mar 6 at 22:23
ssohinssohin
11
New contributor
ssohin is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked Mar 6 at 22:23
ssohinssohin
11
asked Mar 6 at 22:23
ssohinssohin
11
11
New contributor
ssohin is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
ssohin is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
ssohin is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
How do you want to sort them? Here are a few options for clockwise sorting math.stackexchange.com/questions/1018164/…, alternatively you could try something like triangulating your polygon first and then inheriting the order from triangulation. When talking about non-convex polygons, you have a non-unique notion of "clockwise", so solution will be context dependent.
– Juan Carlos Ramirez
Mar 6 at 22:34
Too many links, not enough information in the question itself; see stackoverflow.com/help/mcve.
– chepner
Mar 6 at 22:34
@JuanCarlosRamirez Thanks for your comment, I did come across that link when searching. Approach 1 mentioned here is what I had assumed would work the best for me which is similar to what was posted link I want to have the vertices ordered in a direction that would allow me to convert into a valid shapely polygon again. I did not consider inheriting the order from the triangulation though, thanks for the suggestion.
– ssohin
Mar 6 at 22:50
Edit a Minimal Complete Verifiable Example of your code into your question. See htps://www.stackoverflow.com/help/mcve
– barny
Mar 6 at 22:54
1
This really isn't minimal.
– chepner
Mar 6 at 23:18
|
show 9 more comments
How do you want to sort them? Here are a few options for clockwise sorting math.stackexchange.com/questions/1018164/…, alternatively you could try something like triangulating your polygon first and then inheriting the order from triangulation. When talking about non-convex polygons, you have a non-unique notion of "clockwise", so solution will be context dependent.
– Juan Carlos Ramirez
Mar 6 at 22:34
Too many links, not enough information in the question itself; see stackoverflow.com/help/mcve.
– chepner
Mar 6 at 22:34
@JuanCarlosRamirez Thanks for your comment, I did come across that link when searching. Approach 1 mentioned here is what I had assumed would work the best for me which is similar to what was posted link I want to have the vertices ordered in a direction that would allow me to convert into a valid shapely polygon again. I did not consider inheriting the order from the triangulation though, thanks for the suggestion.
– ssohin
Mar 6 at 22:50
Edit a Minimal Complete Verifiable Example of your code into your question. See htps://www.stackoverflow.com/help/mcve
– barny
Mar 6 at 22:54
1
This really isn't minimal.
– chepner
Mar 6 at 23:18
How do you want to sort them? Here are a few options for clockwise sorting math.stackexchange.com/questions/1018164/…, alternatively you could try something like triangulating your polygon first and then inheriting the order from triangulation. When talking about non-convex polygons, you have a non-unique notion of "clockwise", so solution will be context dependent.
– Juan Carlos Ramirez
Mar 6 at 22:34
How do you want to sort them? Here are a few options for clockwise sorting math.stackexchange.com/questions/1018164/…, alternatively you could try something like triangulating your polygon first and then inheriting the order from triangulation. When talking about non-convex polygons, you have a non-unique notion of "clockwise", so solution will be context dependent.
– Juan Carlos Ramirez
Mar 6 at 22:34
Too many links, not enough information in the question itself; see stackoverflow.com/help/mcve.
– chepner
Mar 6 at 22:34
Too many links, not enough information in the question itself; see stackoverflow.com/help/mcve.
– chepner
Mar 6 at 22:34
@JuanCarlosRamirez Thanks for your comment, I did come across that link when searching. Approach 1 mentioned here is what I had assumed would work the best for me which is similar to what was posted link I want to have the vertices ordered in a direction that would allow me to convert into a valid shapely polygon again. I did not consider inheriting the order from the triangulation though, thanks for the suggestion.
– ssohin
Mar 6 at 22:50
@JuanCarlosRamirez Thanks for your comment, I did come across that link when searching. Approach 1 mentioned here is what I had assumed would work the best for me which is similar to what was posted link I want to have the vertices ordered in a direction that would allow me to convert into a valid shapely polygon again. I did not consider inheriting the order from the triangulation though, thanks for the suggestion.
– ssohin
Mar 6 at 22:50
Edit a Minimal Complete Verifiable Example of your code into your question. See htps://www.stackoverflow.com/help/mcve
– barny
Mar 6 at 22:54
Edit a Minimal Complete Verifiable Example of your code into your question. See htps://www.stackoverflow.com/help/mcve
– barny
Mar 6 at 22:54
1
1
This really isn't minimal.
– chepner
Mar 6 at 23:18
This really isn't minimal.
– chepner
Mar 6 at 23:18
|
show 9 more comments
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "1"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
ssohin is a new contributor. Be nice, and check out our Code of Conduct.
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f55033132%2fsorting-a-polygon-vertices-clockwise%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
ssohin is a new contributor. Be nice, and check out our Code of Conduct.
draft saved
draft discarded
ssohin is a new contributor. Be nice, and check out our Code of Conduct.
ssohin is a new contributor. Be nice, and check out our Code of Conduct.
ssohin is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f55033132%2fsorting-a-polygon-vertices-clockwise%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
How do you want to sort them? Here are a few options for clockwise sorting math.stackexchange.com/questions/1018164/…, alternatively you could try something like triangulating your polygon first and then inheriting the order from triangulation. When talking about non-convex polygons, you have a non-unique notion of "clockwise", so solution will be context dependent.
– Juan Carlos Ramirez
Mar 6 at 22:34
Too many links, not enough information in the question itself; see stackoverflow.com/help/mcve.
– chepner
Mar 6 at 22:34
@JuanCarlosRamirez Thanks for your comment, I did come across that link when searching. Approach 1 mentioned here is what I had assumed would work the best for me which is similar to what was posted link I want to have the vertices ordered in a direction that would allow me to convert into a valid shapely polygon again. I did not consider inheriting the order from the triangulation though, thanks for the suggestion.
– ssohin
Mar 6 at 22:50
Edit a Minimal Complete Verifiable Example of your code into your question. See htps://www.stackoverflow.com/help/mcve
– barny
Mar 6 at 22:54
1
This really isn't minimal.
– chepner
Mar 6 at 23:18