New try für convex hull

gistfile1.py

import numpy
from pprint import pprint

"""
class Point:

    def  __init__ (self,x,y):
        self.x = x
        self.y = y

    def __lt__(self,other):
        (self.x,self.y) < (other.x,other.y)

    def asList(self):
        return [self.x, self.y]
"""
class Line:

    def __init__ (self,p1,p2):
        self.p1 = p1
        self.p2 = p2

    def hasOnTheLeft(self,otherPoint):

        """
        this test is performed by computing det of
        p1.x            p1.y            1
        p2.x            p2.y            1
        otherPoint.x    otherPoint.y    1
        """

        lists = [ p + (1,) for p in [self.p1,self.p2,otherPoint]]

        matrix = numpy.matrix(lists)
        return numpy.linalg.det(matrix)

def createConvexHul(points):
    points.sort()

    if points[1][1] < points[2][1]:
        ch = [ points[1], points[0], points[2] ]
    else:
        ch = [ points[2], points[0], points[1] ]

    for point in points[3:]:

        i = len(ch)-2;
        others = []
        while i >= 0:
            myLine = Line(point,ch[i])
            poi = ch[i+1]
            if myLine.hasOnTheLeft(poi) > 0 :
                ch.remove(poi)
                others.append(poi)
            else:
                ch.append(point)
                break
            i = i - 1

        others.reverse()
        ch = others + ch

        i = 1
        while i < len(ch):
            myLine = Line(point,ch[i])
            poi = ch[i-1]
            if myLine.hasOnTheLeft(poi) < 0 :
                ch.remove(poi)
            else:
                break
            i = i + 1
        visualize(points,ch)

    return ch

def visualize(points, hull=None):
    GRAY = '#000080'
    from matplotlib import pyplot
    from shapely.geometry import LineString, MultiPoint
    figure = pyplot.figure(1, dpi=90)
    ax = figure.add_subplot(121)
    for x,y in points:
        ax.plot(x, y, 'o', color=GRAY, zorder=1)
    ax.set_title('convex hull')
    line = LineString(hull+[hull[0]])
    x, y = line.xy
    ax.plot(x, y, color='#ffcc33', linewidth=2, solid_capstyle='round', zorder=0)
    ax.set_aspect(1)
    pyplot.show()