pythonalgorithmgeometrymayaconvex-hull
Why is my convex hull algorithm returning the wrong points?
I'm writing some Python for Autodesk Maya that should return the 2D convex hull for a given 3D polygon. More specifically, I want to flatten a 3D polygon by throwing out the height coordinates, and create a convex hull for the "flattened" 2D representation of said polygon.
For example, if it is given a list of vertices, the expected result should only be the vertices in the outermost edge loop. There are a total of 400 vertices in a basic torus(just an example polygon), and the outer edge loop is made up of 20 of those vertices, but I end up getting 216 vertices back when calculating the convex hull; those vertices include ones that are in the innermost edge loops, which shouldn't happen.
The algorithm is based on code here: https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain#Python
Note that I am using X and Z coordinates, not X and Y. I don't think that this should be a problem as long as Z is used in the same way as Y, but correct me if I'm wrong. You may also be wondering why I don't just look for vertices that have a height of 0; that would indeed work for the torus, but not for other polygons that are moving(animated) and do not have an "equator" that also happens to be the convex hull.
Here are some screenshots of the torus polygon. The vertices highlighted in yellow are what I would expect the convex hull to be, given that we flattened the polygon by ignoring Y.
Here is a representation of my computed hull points.
As you can see, most of the vertices are selected.
Here is the code, though I re-wrote it so that it just takes arrays of vertex coordinates rather than depend on the Maya API. Some things, like the Vertex class, may seem pointless here but that's because code was removed from the original version that doesn't have to do with the convex hull calculation. Tested with Python 2.7.
class PolyFence(list):
def __init__(self, vertices):
self.compute_convex_hull(vertices)
def intersects(self, polygon):
for coordinate in self:
if coordinate.within(polygon):
return True
return False
def compute_convex_hull(self, vertices):
def cross(o, a, b):
return (a.x - o.x) * (b.z - o.z) - (a.z - o.z) * (b.x - o.x)
def build_hull(sorted_points):
hull = []
for p in sorted_points:
while len(hull) >= 2 and cross(hull[-2], hull[-1], p) <= 0:
hull.pop()
hull.append(p)
return hull
sorted_points = sorted(set(vertices))
# Build lower hull
lower = build_hull(sorted_points)
# Build upper hull
upper = build_hull(reversed(sorted_points))
c_hull_points = lower[:-1] + upper[:-1]
ordered_hull_points = sorted(c_hull_points, key=lambda k: (-k.x, -k.z))
ordered_hull_points[-2], ordered_hull_points[-1] = ordered_hull_points[-1], ordered_hull_points[-2]
self += ordered_hull_points
class Vertex:
def __init__(self, pair):
self.x = pair[0]
self.z = pair[1]
def __getitem__(self, idx):
if idx == 0:
return self.x
if idx == 1:
# this is so we don't sort by values we aren't using
return self.z
return None
torus_coords = [(0.4755285680294037, -0.1545085906982422), (0.4045087695121765, -0.2938928008079529), (0.2938928008079529, -0.4045087397098541), (0.154508575797081, -0.4755285084247589), (0.0, -0.5000002384185791), (-0.154508575797081, -0.4755284786224365), (-0.2938927412033081, -0.40450865030288696), (-0.4045086205005646, -0.2938927114009857), (-0.47552838921546936, -0.1545085310935974), (-0.5000001192092896, 0.0), (-0.47552838921546936, 0.1545085310935974), (-0.4045085906982422, 0.29389268159866333), (-0.29389268159866333, 0.4045085608959198), (-0.1545085310935974, 0.4755283296108246), (-1.4901161193847656e-08, 0.5000000596046448), (0.15450848639011383, 0.4755282998085022), (0.29389262199401855, 0.4045085310935974), (0.404508501291275, 0.29389265179634094), (0.4755282700061798, 0.15450850129127502), (0.5, 0.0), (0.4988026022911072, -0.16207078099250793), (0.42430683970451355, -0.3082769513130188), (0.3082769513130188, -0.42430680990219116), (0.16207076609134674, -0.4988025426864624), (0.0, -0.5244719982147217), (-0.16207076609134674, -0.49880251288414), (-0.308276891708374, -0.424306720495224), (-0.4243066906929016, -0.30827686190605164), (-0.49880242347717285, -0.16207072138786316), (-0.5244718790054321, 0.0), (-0.49880242347717285, 0.16207072138786316), (-0.4243066608905792, 0.30827683210372925), (-0.30827683210372925, 0.42430663108825684), (-0.16207072138786316, 0.4988023638725281), (-1.5630476468686538e-08, 0.5244718194007874), (0.16207067668437958, 0.4988023340702057), (0.3082767724990845, 0.42430660128593445), (0.42430657148361206, 0.30827680230140686), (0.4988023042678833, 0.16207069158554077), (0.5244717597961426, 0.0), (0.5663464665412903, -0.1840171068906784), (0.48176309466362, -0.3500213325023651), (0.3500213325023651, -0.4817630648612976), (0.1840170919895172, -0.5663464069366455), (0.0, -0.5954918265342712), (-0.1840170919895172, -0.5663463473320007), (-0.35002127289772034, -0.48176294565200806), (-0.48176291584968567, -0.35002124309539795), (-0.5663462281227112, -0.18401704728603363), (-0.5954916477203369, 0.0), (-0.5663462281227112, 0.18401704728603363), (-0.4817628860473633, 0.35002121329307556), (-0.35002121329307556, 0.4817628562450409), (-0.18401704728603363, 0.5663461685180664), (-1.7747030511827688e-08, 0.5954915881156921), (0.18401698768138885, 0.5663461685180664), (0.3500211238861084, 0.4817627966403961), (0.48176276683807373, 0.3500211834907532), (0.5663461089134216, 0.18401700258255005), (0.5954915285110474, 0.0), (0.6715484857559204, -0.21819931268692017), (0.57125324010849, -0.4150397479534149), (0.4150397479534149, -0.57125324010849), (0.21819929778575897, -0.6715483665466309), (0.0, -0.7061077356338501), (-0.21819929778575897, -0.6715483069419861), (-0.41503965854644775, -0.5712530612945557), (-0.5712530612945557, -0.41503962874412537), (-0.6715481877326965, -0.218199223279953), (-0.7061075568199158, 0.0), (-0.6715481877326965, 0.218199223279953), (-0.5712530016899109, 0.4150395691394806), (-0.4150395691394806, 0.5712529420852661), (-0.218199223279953, 0.6715481281280518), (-2.1043639719664498e-08, 0.7061074376106262), (0.21819916367530823, 0.671548068523407), (0.4150395095348358, 0.5712529420852661), (0.5712528824806213, 0.4150395393371582), (0.671548068523407, 0.21819917857646942), (0.7061073780059814, 0.0), (0.8041107654571533, -0.2612714171409607), (0.6840174794197083, -0.49696773290634155), (0.49696773290634155, -0.6840174198150635), (0.2612713873386383, -0.8041106462478638), (0.0, -0.8454919457435608), (-0.2612713873386383, -0.804110586643219), (-0.4969676434993744, -0.6840173006057739), (-0.6840172410011292, -0.4969675838947296), (-0.8041104674339294, -0.26127129793167114), (-0.8454917073249817, 0.0), (-0.8041104674339294, 0.26127129793167114), (-0.6840171813964844, 0.4969675540924072), (-0.4969675540924072, 0.6840171217918396), (-0.26127129793167114, 0.8041103482246399), (-2.5197611108751516e-08, 0.8454916477203369), (0.26127123832702637, 0.8041102886199951), (0.4969674348831177, 0.6840170621871948), (0.68401700258255, 0.49696749448776245), (0.8041102290153503, 0.26127126812934875), (0.8454915285110474, 0.0), (0.9510571360588074, -0.3090171813964844), (0.809017539024353, -0.5877856016159058), (0.5877856016159058, -0.8090174794197083), (0.309017151594162, -0.9510570168495178), (0.0, -1.0000004768371582), (-0.309017151594162, -0.951056957244873), (-0.5877854824066162, -0.8090173006057739), (-0.8090172410011292, -0.5877854228019714), (-0.9510567784309387, -0.3090170621871948), (-1.000000238418579, 0.0), (-0.9510567784309387, 0.3090170621871948), (-0.8090171813964844, 0.5877853631973267), (-0.5877853631973267, 0.8090171217918396), (-0.3090170621871948, 0.9510566592216492), (-2.9802322387695312e-08, 1.0000001192092896), (0.30901697278022766, 0.9510565996170044), (0.5877852439880371, 0.8090170621871948), (0.80901700258255, 0.5877853035926819), (0.9510565400123596, 0.30901700258255005), (1.0, 0.0), (1.098003625869751, -0.35676300525665283), (0.9340177178382874, -0.6786035299301147), (0.6786035299301147, -0.9340176582336426), (0.35676294565200806, -1.0980035066604614), (0.0, -1.15450918674469), (-0.35676294565200806, -1.0980033874511719), (-0.6786034107208252, -0.9340174198150635), (-0.9340173602104187, -0.6786032915115356), (-1.0980032682418823, -0.3567628562450409), (-1.1545088291168213, 0.0), (-1.0980032682418823, 0.3567628562450409), (-0.9340173006057739, 0.6786032319068909), (-0.6786032319068909, 0.9340172410011292), (-0.3567628562450409, 1.0980030298233032), (-3.440703721935279e-08, 1.1545087099075317), (0.35676273703575134, 1.0980030298233032), (0.6786031126976013, 0.9340171217918396), (0.9340170621871948, 0.6786031723022461), (1.0980029106140137, 0.3567627966403961), (1.1545085906982422, 0.0), (1.2305657863616943, -0.3998350501060486), (1.0467817783355713, -0.7605314254760742), (0.7605314254760742, -1.0467817783355713), (0.3998350203037262, -1.2305656671524048), (0.0, -1.2938932180404663), (-0.3998350203037262, -1.2305655479431152), (-0.7605313062667847, -1.0467815399169922), (-1.0467814207077026, -0.7605312466621399), (-1.2305653095245361, -0.39983490109443665), (-1.2938929796218872, 0.0), (-1.2305653095245361, 0.39983490109443665), (-1.0467814207077026, 0.7605311274528503), (-0.7605311274528503, 1.046781301498413), (-0.39983490109443665, 1.2305651903152466), (-3.856100505572613e-08, 1.293892741203308), (0.3998347818851471, 1.230565071105957), (0.7605310082435608, 1.0467811822891235), (1.0467811822891235, 0.7605310678482056), (1.230565071105957, 0.3998348116874695), (1.2938926219940186, 0.0), (1.3357678651809692, -0.4340173006057739), (1.1362720727920532, -0.8255499005317688), (0.8255499005317688, -1.1362719535827637), (0.43401724100112915, -1.3357677459716797), (0.0, -1.4045093059539795), (-0.43401724100112915, -1.3357676267623901), (-0.8255497813224792, -1.1362717151641846), (-1.1362717151641846, -0.8255496621131897), (-1.335767388343811, -0.4340171217918396), (-1.4045089483261108, 0.0), (-1.335767388343811, 0.4340171217918396), (-1.136271595954895, 0.8255496025085449), (-0.8255496025085449, 1.1362714767456055), (-0.4340171217918396, 1.3357672691345215), (-4.1857617816276615e-08, 1.4045087099075317), (0.43401700258255005, 1.335767149925232), (0.8255494236946106, 1.136271357536316), (1.136271357536316, 0.8255494832992554), (1.3357670307159424, 0.43401703238487244), (1.4045085906982422, 0.0), (1.4033117294311523, -0.4559636116027832), (1.1937283277511597, -0.8672943115234375), (0.8672943115234375, -1.1937282085418701), (0.4559635818004608, -1.4033116102218628), (0.0, -1.4755290746688843), (-0.4559635818004608, -1.4033114910125732), (-0.8672941327095032, -1.193727970123291), (-1.1937278509140015, -0.8672940731048584), (-1.4033112525939941, -0.4559634327888489), (-1.4755287170410156, 0.0), (-1.4033112525939941, 0.4559634327888489), (-1.1937278509140015, 0.8672939538955688), (-0.8672939538955688, 1.193727731704712), (-0.4559634327888489, 1.403311014175415), (-4.3974171859417766e-08, 1.4755284786224365), (0.4559633135795593, 1.403311014175415), (0.8672937750816345, 1.1937276124954224), (1.1937274932861328, 0.8672938942909241), (1.4033108949661255, 0.4559633433818817), (1.475528359413147, 0.0), (1.4265857934951782, -0.46352580189704895), (1.2135263681411743, -0.8816784620285034), (0.8816784620285034, -1.2135263681411743), (0.46352577209472656, -1.4265856742858887), (0.0, -1.5000008344650269), (-0.46352577209472656, -1.4265855550765991), (-0.8816782832145691, -1.2135260105133057), (-1.2135260105133057, -0.8816782236099243), (-1.42658531665802, -0.4635256230831146), (-1.5000004768371582, 0.0), (-1.42658531665802, 0.4635256230831146), (-1.2135258913040161, 0.8816781044006348), (-0.8816781044006348, 1.2135257720947266), (-0.4635256230831146, 1.426585078239441), (-4.470348713425665e-08, 1.5000003576278687), (0.4635255038738251, 1.4265849590301514), (0.8816779255867004, 1.213525652885437), (1.213525652885437, 0.88167804479599), (1.4265849590301514, 0.46352553367614746), (1.5000001192092896, 0.0), (1.4033117294311523, -0.4559636116027832), (1.1937283277511597, -0.8672943115234375), (0.8672943115234375, -1.1937282085418701), (0.4559635818004608, -1.4033116102218628), (0.0, -1.4755290746688843), (-0.4559635818004608, -1.4033114910125732), (-0.8672941327095032, -1.193727970123291), (-1.1937278509140015, -0.8672940731048584), (-1.4033112525939941, -0.4559634327888489), (-1.4755287170410156, 0.0), (-1.4033112525939941, 0.4559634327888489), (-1.1937278509140015, 0.8672939538955688), (-0.8672939538955688, 1.193727731704712), (-0.4559634327888489, 1.403311014175415), (-4.3974171859417766e-08, 1.4755284786224365), (0.4559633135795593, 1.403311014175415), (0.8672937750816345, 1.1937276124954224), (1.1937274932861328, 0.8672938942909241), (1.4033108949661255, 0.4559633433818817), (1.475528359413147, 0.0), (1.3357678651809692, -0.4340173006057739), (1.1362720727920532, -0.8255499005317688), (0.8255499005317688, -1.1362719535827637), (0.43401724100112915, -1.3357677459716797), (0.0, -1.4045093059539795), (-0.43401724100112915, -1.3357676267623901), (-0.8255497813224792, -1.1362717151641846), (-1.1362717151641846, -0.8255496621131897), (-1.335767388343811, -0.4340171217918396), (-1.4045089483261108, 0.0), (-1.335767388343811, 0.4340171217918396), (-1.136271595954895, 0.8255496025085449), (-0.8255496025085449, 1.1362714767456055), (-0.4340171217918396, 1.3357672691345215), (-4.1857617816276615e-08, 1.4045087099075317), (0.43401700258255005, 1.335767149925232), (0.8255494236946106, 1.136271357536316), (1.136271357536316, 0.8255494832992554), (1.3357670307159424, 0.43401703238487244), (1.4045085906982422, 0.0), (1.2305659055709839, -0.39983507990837097), (1.0467818975448608, -0.7605315446853638), (0.7605315446853638, -1.0467818975448608), (0.3998350501060486, -1.2305657863616943), (0.0, -1.2938933372497559), (-0.3998350501060486, -1.2305656671524048), (-0.7605313658714294, -1.0467816591262817), (-1.0467815399169922, -0.7605313062667847), (-1.2305654287338257, -0.39983493089675903), (-1.2938930988311768, 0.0), (-1.2305654287338257, 0.39983493089675903), (-1.0467814207077026, 0.7605311870574951), (-0.7605311870574951, 1.0467814207077026), (-0.39983493089675903, 1.2305653095245361), (-3.8561008608439806e-08, 1.2938928604125977), (0.3998348116874695, 1.2305651903152466), (0.7605310678482056, 1.046781301498413), (1.0467811822891235, 0.7605311274528503), (1.2305651903152466, 0.39983487129211426), (1.293892741203308, 0.0), (1.098003625869751, -0.35676300525665283), (0.9340177178382874, -0.6786035299301147), (0.6786035299301147, -0.9340176582336426), (0.35676294565200806, -1.0980035066604614), (0.0, -1.15450918674469), (-0.35676294565200806, -1.0980033874511719), (-0.6786034107208252, -0.9340174198150635), (-0.9340173602104187, -0.6786032915115356), (-1.0980032682418823, -0.3567628562450409), (-1.1545088291168213, 0.0), (-1.0980032682418823, 0.3567628562450409), (-0.9340173006057739, 0.6786032319068909), (-0.6786032319068909, 0.9340172410011292), (-0.3567628562450409, 1.0980030298233032), (-3.440703721935279e-08, 1.1545087099075317), (0.35676273703575134, 1.0980030298233032), (0.6786031126976013, 0.9340171217918396), (0.9340170621871948, 0.6786031723022461), (1.0980029106140137, 0.3567627966403961), (1.1545085906982422, 0.0), (0.9510571360588074, -0.3090171813964844), (0.809017539024353, -0.5877856016159058), (0.5877856016159058, -0.8090174794197083), (0.309017151594162, -0.9510570168495178), (0.0, -1.0000004768371582), (-0.309017151594162, -0.951056957244873), (-0.5877854824066162, -0.8090173006057739), (-0.8090172410011292, -0.5877854228019714), (-0.9510567784309387, -0.3090170621871948), (-1.000000238418579, 0.0), (-0.9510567784309387, 0.3090170621871948), (-0.8090171813964844, 0.5877853631973267), (-0.5877853631973267, 0.8090171217918396), (-0.3090170621871948, 0.9510566592216492), (-2.9802322387695312e-08, 1.0000001192092896), (0.30901697278022766, 0.9510565996170044), (0.5877852439880371, 0.8090170621871948), (0.80901700258255, 0.5877853035926819), (0.9510565400123596, 0.30901700258255005), (1.0, 0.0), (0.8041106462478638, -0.2612713575363159), (0.6840173602104187, -0.4969676733016968), (0.4969676733016968, -0.6840173006057739), (0.2612713575363159, -0.8041105270385742), (0.0, -0.8454918265342712), (-0.2612713575363159, -0.8041104674339294), (-0.4969675838947296, -0.6840171813964844), (-0.6840171217918396, -0.49696752429008484), (-0.8041103482246399, -0.26127126812934875), (-0.8454915881156921, 0.0), (-0.8041103482246399, 0.26127126812934875), (-0.6840170621871948, 0.49696746468544006), (-0.49696746468544006, 0.68401700258255), (-0.26127126812934875, 0.8041102290153503), (-2.5197607556037838e-08, 0.8454915285110474), (0.261271208524704, 0.8041101694107056), (0.4969673752784729, 0.68401700258255), (0.6840169429779053, 0.4969674348831177), (0.8041101098060608, 0.261271208524704), (0.8454914093017578, 0.0), (0.6715483069419861, -0.2181992530822754), (0.5712531208992004, -0.41503965854644775), (0.41503965854644775, -0.5712530612945557), (0.2181992381811142, -0.6715481877326965), (0.0, -0.7061075568199158), (-0.2181992381811142, -0.6715481877326965), (-0.4150395691394806, -0.5712529420852661), (-0.5712528824806213, -0.4150395095348358), (-0.6715480089187622, -0.21819917857646942), (-0.7061073780059814, 0.0), (-0.6715480089187622, 0.21819917857646942), (-0.5712528824806213, 0.4150394797325134), (-0.4150394797325134, 0.5712528228759766), (-0.21819917857646942, 0.6715479493141174), (-2.104363439059398e-08, 0.7061072587966919), (0.21819910407066345, 0.6715478897094727), (0.41503939032554626, 0.5712527632713318), (0.571252703666687, 0.41503942012786865), (0.6715478897094727, 0.21819913387298584), (0.7061071991920471, 0.0), (0.5663461685180664, -0.18401701748371124), (0.4817628562450409, -0.3500211834907532), (0.3500211834907532, -0.4817628264427185), (0.18401700258255005, -0.5663461089134216), (0.0, -0.5954915285110474), (-0.18401700258255005, -0.5663460493087769), (-0.350021094083786, -0.48176270723342896), (-0.48176267743110657, -0.3500210642814636), (-0.5663459897041321, -0.18401695787906647), (-0.595491349697113, 0.0), (-0.5663459897041321, 0.18401695787906647), (-0.4817626476287842, 0.35002103447914124), (-0.35002103447914124, 0.4817625880241394), (-0.18401695787906647, 0.5663458704948425), (-1.774702163004349e-08, 0.5954912900924683), (0.1840168982744217, 0.5663458704948425), (0.3500209450721741, 0.481762558221817), (0.48176252841949463, 0.35002100467681885), (0.5663458108901978, 0.18401691317558289), (0.5954912304878235, 0.0), (0.4988022744655609, -0.16207067668437958), (0.42430657148361206, -0.3082767426967621), (0.3082767426967621, -0.4243065416812897), (0.16207066178321838, -0.49880221486091614), (0.0, -0.524471640586853), (-0.16207066178321838, -0.49880218505859375), (-0.3082766830921173, -0.4243064522743225), (-0.42430639266967773, -0.3082766532897949), (-0.4988020956516266, -0.1620706170797348), (-0.5244715213775635, 0.0), (-0.4988020956516266, 0.1620706170797348), (-0.42430636286735535, 0.30827662348747253), (-0.30827662348747253, 0.42430633306503296), (-0.1620706170797348, 0.4988020062446594), (-1.5630465810545502e-08, 0.5244714617729187), (0.16207057237625122, 0.49880197644233704), (0.30827656388282776, 0.42430630326271057), (0.4243062734603882, 0.30827659368515015), (0.49880194664001465, 0.16207058727741241), (0.5244714021682739, 0.0)]
torus = [Vertex(coord) for coord in torus_coords]
fence = PolyFence(torus)
expectation_coords = [(1.4265857934951782, -0.46352580189704895), (1.2135263681411743, -0.8816784620285034), (0.8816784620285034, -1.2135263681411743), (0.46352577209472656, -1.4265856742858887), (0.0, -1.5000008344650269), (-0.46352577209472656, -1.4265855550765991), (-0.8816782832145691, -1.2135260105133057), (-1.2135260105133057, -0.8816782236099243), (-1.42658531665802, -0.4635256230831146), (-1.5000004768371582, 0.0), (-1.42658531665802, 0.4635256230831146), (-1.2135258913040161, 0.8816781044006348), (-0.8816781044006348, 1.2135257720947266), (-0.4635256230831146, 1.426585078239441), (-4.470348713425665e-08, 1.5000003576278687), (0.4635255038738251, 1.4265849590301514), (0.8816779255867004, 1.213525652885437), (1.213525652885437, 0.88167804479599), (1.4265849590301514, 0.46352553367614746), (1.5000001192092896, 0.0)] #
expectation = [Vertex(coord) for coord in expectation_coords]
assert(sorted(fence) == sorted(expectation))
Solution
@Sneftel was right; my code wasn't actually sorting the points lexographically because my vertices are not lists or tuples, which are ordered per-property by Python.
This is how I changed the call to sorted to get the correct result:
sorted_points = sorted(set(self.vertices()), key=lambda v: (v.x(), v.z()))
Basically, I'm translating my object to a tuple for it to have something to sort by.
And here's the result. :)
