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:

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.

ssohin
  • 37
  • 9
  • How do you want to sort them? Here are a few options for clockwise sorting https://math.stackexchange.com/questions/1018164/sorting-a-list-of-points-in-2-d-clockwise, 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 06 '19 at 22:34
  • Too many links, not enough information in the question itself; see https://stackoverflow.com/help/mcve. – chepner Mar 06 '19 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](https://stackoverflow.com/questions/44025403/how-to-use-matplotlib-path-to-draw-polygon) 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 06 '19 at 22:50
  • Edit a Minimal Complete Verifiable Example of your code into your question. See htps://www.stackoverflow.com/help/mcve – DisappointedByUnaccountableMod Mar 06 '19 at 22:54
  • @chepner , barny Thanks for your suggestion, I have added a mcve. – ssohin Mar 06 '19 at 23:14
  • 1
    This *really* isn't minimal. – chepner Mar 06 '19 at 23:18
  • @chepner Can you please elaborate? The poly2trap code depends heavily on the triangulation functions as defined in seidel.py. The test polygon has as many vertices to portray the complexity of the problem I am trying to solve. – ssohin Mar 06 '19 at 23:23
  • 1
    Pinpoint *where* you think the problem is; don't just throw hundreds of lines of code in the question and ask us to figure out the problem. If the question in the title is accurate, all you need is a function that takes a list of points, a routine that sorts them, and the expected and actual output. You probably need to include the definition of `Point`, but you could probably exclude the methods unrelated to sorting. – chepner Mar 06 '19 at 23:29
  • @chepner Thanks for your input. I have realized that triangulation works well and is irrelevant to the question. I have removed that part from the mcve and updated the mcve. – ssohin Mar 06 '19 at 23:56
  • Your question is very unclear. You mention decomposition into trapezoids (which seems to work), then triangulation, then angular sorting. These three processes are unrelated. –  Mar 07 '19 at 13:42
  • @YvesDaoust From what I understand, triangulation is a part of the decomposition process. The end goal is to decompose into trapezoids and form another polygon from that. I've updated the question to try and explain it more clearly. I am looking for a better sort method because of the complexities that the decomposition adds to the resultant geometry. – ssohin Mar 07 '19 at 15:16
  • If you decompose a polygon into trapezoids and re-form a polygon from them ... wouldn't you get the original polygon? – meowgoesthedog Mar 07 '19 at 16:29
  • I am not sure to understand what you are trying to do, but angular sorting is a wrong idea. The polygon vertices are neither clockwise nor counterclockwise. –  Mar 07 '19 at 16:49
  • @meowgoesthedog That's how I expect it to work too, but here the order is lost during decomposition. I also found a similar question for R : (https://stackoverflow.com/questions/53707655/sorting-coordinates-to-create-a-polygon-gives-messy-results). But the answer tackles it with a different approach (extracting coordinates from map). At the moment it seems like I should add a feature to the decomposition part where it maintains the order. – ssohin Mar 07 '19 at 20:19

0 Answers0