root/trunk/RBRapier/RBRapier/Tools/Geometry/ConvexPolygonTesselation.py

#!/usr/bin/env python
##~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
##~ License 
##~ 
##- The RuneBlade Foundation library is intended to ease some 
##- aspects of writing intricate Jabber, XML, and User Interface (wxPython, etc.) 
##- applications, while providing the flexibility to modularly change the 
##- architecture. Enjoy.
##~ 
##~ Copyright (C) 2002  TechGame Networks, LLC.
##~ 
##~ This library is free software; you can redistribute it and/or
##~ modify it under the terms of the BSD style License as found in the 
##~ LICENSE file included with this distribution.
##~ 
##~ TechGame Networks, LLC can be reached at:
##~ 3578 E. Hartsel Drive #211
##~ Colorado Springs, Colorado, USA, 80920
##~
##~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#~ Imports 
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#~ Definitions 
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

def TesselateConvexPolygon(Indexes):
    """
    >>> TesselateConvexPolygon(range(7))
    [[0, 1, 6], [2, 6, 1], [6, 2, 5], [3, 5, 2], [5, 3, 4]]
    >>> TesselateConvexPolygon(range(6))
    [[0, 1, 5], [2, 5, 1], [5, 2, 4], [3, 4, 2]]
    """
    count = len(Indexes)
    order = range(1,count)
    order.append(0)
    if count & 1: count = count//2
    else: count = count//2-1
    order0, order1 = order[count:], order[:count]
    order0.reverse()
    order = [x for y in map(None, order0, order1) for x in y if x is not None]

    result = []
    for i in xrange(len(order)-2):
        result.append([Indexes[idx] for idx in order[i:i+3]])
        if i & 1: result[-1].reverse()
    return result

#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#~ Title 
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

try: import psyco
except ImportError: pass
else:
    psyco.bind(TesselateConvexPolygon)

#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#~ Testing 
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

if __name__=='__main__':
    print "Testing..."
    import doctest
    import ConvexPolygonTesselation as _testmod
    doctest.testmod(_testmod)
    print "Test complete."