Convex hull (凸包)を計算する Python コード

与えられた点をピンだと思って、最も左のピンから糸を上に引っ張って、次々と時計回りに巻いていく感じです。最初の点まで帰ってきたら終了です。この方式は、Gift wrapping algorithmと呼ばれているそうです。

リスト処理関数(map, reduce, filter)を使って意外と簡潔に書けたつもりですが、改行が入っちゃうとそんなに短く見えないですね。あと math.atan2 便利。

入力となる点集合は list of (x, y) の形ですが、v[0] で x, v[1] で y にアクセスできればよいので list of Blender.Mathutils.Vector でもよいです。

def convex_hull(vs):
    def limit(max_rad, v): return max_rad < v and v - 2 * math.pi or v
    def rad(v): return math.atan2(v[1], v[0])
    def sub(a, b): return (a[0]-b[0], a[1]-b[1])

    node = (reduce(lambda a, b: a[0] < b[0] and a or b, vs), math.pi / 2)
    ch = [node[0]]
    for i in range(len(vs)):
        node = reduce(lambda a, b: a[1] > b[1] and a or b, map(lambda x: (x, limit(node[1], rad(sub(x, node[0])))), filter(lambda x: node[0] != x, vs)))
        if ch[0] == node[0]: break
        ch.append(node[0])
    return ch

# Test code
def convex_hull_test():
    vs = [ (0, 0), (0, 1), (1, 1), (1, 0) ]
    for i in range(10): vs.append((random.uniform(0.3,0.6), random.uniform(0.3,0.6)))
    print "convex hull:", convex_hull(vs)

2010/01/02
テーマ: 開発 / アルゴリズム / 2010 / すべて