凸包走査アルゴリズムをPython+PyOpenGLで

オライリーから出版されている『アルゴリズムクイックリファレンス』で凸包走査アルゴリズムを学習したので、PythonとPyOpenGLで適当に点を打った点集合から凸包を計算して表示するプログラムを作成しました。

点（-1,-1）と、点（+1,+1）からなる矩形に一様乱数でランダムな点を作成してプロットしています。

アルゴリズムクイックリファレンス

点の数：20

点の数：50

点の数：1000

ソース

#! /usr/bin/python2.6
# coding: utf-8

# random points convex hull

from OpenGL.GL import *
from OpenGL.GLU import *
from OpenGL.GLUT import *
import sys
import random

def clockWiseLastThree(u, p):
    vec = lambda i,j: (p[u[j]][0] - p[u[i]][0], p[u[j]][1] - p[u[i]][1])
    v = vec(-3, -2)
    w = vec(-2, -1)
    op = v[0]*w[1] - v[1]*w[0]
    return op > 1e-6

def convexHullScan(p):
    assert len(ps) >= 3
    # sort
    p.sort()
    # upper convex hull
    upper = [0, 1]
    for i in xrange(2, len(p)):
        upper.append(i)
        while len(upper) >= 3 and not clockWiseLastThree(upper, p):
            upper.pop(-2)
    # lower convex hull
    lower = [len(p)-1, len(p)-2]
    for i in xrange(len(p)-3, -1, -1):
        lower.append(i)
        while len(lower) >= 3 and not clockWiseLastThree(lower, p):
            lower.pop(-2)
    seq = upper + lower
    return seq

ps = None
indices = None

def display():
    glClearColor(1, 1, 1, 1)
    glClear(GL_COLOR_BUFFER_BIT)
    # plot points
    glColor3f(0, 0, 1)
    glPointSize(3)
    glBegin(GL_POINTS)
    for p in ps:
        glVertex2dv(p)
    glEnd()
    # plot convex hull
    glColor3f(1, 0, 0)
    glBegin(GL_LINE_LOOP)
    for i in indices:
        glVertex2dv(ps[i])
    glEnd()
    # 
    glutSwapBuffers()

def main():
    global npoints, ps, indices
    glutInit(sys.argv)
    glutCreateWindow("Convex Hull Scan Algorithm");
    
    # app init
    if len(sys.argv) < 2:
        print 'usage: %s npoints' % __file__
        return
    npoints = int(sys.argv[1])
    f = lambda: 2.*(random.random()-.5)
    rp = lambda: (f(), f())
    ps = [rp() for _ in xrange(npoints)]
    indices = convexHullScan(ps)
    
    # mainloop
    glutDisplayFunc(display)
    glutMainLoop()

if __name__ == '__main__':
    main()