python - 为什么我的凸包算法返回错误的点？

Question

我正在为 Autodesk Maya 编写一些 Python，它应该返回给定 3D 多边形的 2D 凸包。更具体地说，我想通过抛出高度坐标来展平 3D 多边形，并为所述多边形的“展平”2D 表示创建一个凸包。

例如，如果给它一个顶点列表，预期的结果应该只是最外边循环中的顶点。一个基本环面(只是一个示例多边形)总共有 400 个顶点，外边缘循环由其中 20 个顶点组成，但在计算凸包时我最终得到了 216 个顶点；这些顶点包括位于最内层边循环中的顶点，这是不应该发生的。

该算法基于此处的代码: https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain#Python

请注意，我使用的是 X 和 Z 坐标，而不是 X 和 Y。我不认为这应该是一个问题，只要 Z 的使用方式与 Y 相同，但如果我错了请纠正我.您可能还想知道为什么我不只查找高度为 0 的顶点；这确实适用于环面，但不适用于其他正在移动(动画)并且没有恰好也是凸包的“赤道”的多边形。

以下是环面多边形的一些屏幕截图。假设我们通过忽略 Y 来展平多边形，以黄色突出显示的顶点就是我所期望的凸包。

这是我计算的船体点的表示。

如您所见，大多数顶点都被选中。

这是代码，但我重新编写了它，以便它只采用顶点坐标数组而不依赖于 Maya API。有些东西，比如 Vertex 类，在这里可能看起来毫无意义，但那是因为代码从原始版本中删除，与凸包计算无关。使用 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))

Answer 1

@Sneftel 是对的；我的代码实际上并没有按字典顺序对点进行排序，因为我的顶点不是列表或元组，它们是由 Python 按属性排序的。

这就是我如何更改对 sorted 的调用以获得正确的结果:

sorted_points = sorted(set(self.vertices()), key=lambda v: (v.x(), v.z()))

基本上，我将我的对象转换为一个元组，以便它有一些排序依据。

这是结果。 :)