Das deutsche Python-Forum

Code: Alles auswählen

#!/usr/bin/python
# -*- coding: utf8 -*-

import math


# gewöhnlicher Kreis
class Circle:

    def __init__(self, x, y, r):
        self.x = x # x Koordinate Mittelpunkt
        self.y = y # y Koordinate Mittelpunkt
        self.r = r # Radius

    def __str__(self):
        return '<{0},{1}:{2}>'.format(self.x, self.y, self.r)

    # Eukldischer Abstand zweier Punkte
    def distance(self, x, y):
        return math.sqrt((self.x - x)**2 + (self.y - y)**2)

    # Kollision Kreis-Punkt
    def collide(self, x, y):
        return (self.distance(x, y) <= self.r)

    # Kollision Kreis-Kreis
    def intersect(self, circ):
        if (self.distance(circ.x, circ.y) <= self.r + circ.r):
            # hier sollte dann die polygonbasierte Kollisionsprüfung folgen
            #print 'Abstand: {0}, Radiensumme: {1}'.format(self.distance(circ.x, circ.y), self.r+circ.r)
            return True
        else:
            return False

    # Quadrat (achsenparallel) erzeugen, dessen Inkreis dieser Kreis ist
    def getRect(self):
        return Rect(self.x - self.r, self.y - self.r, 2 * self.r, 2 * self.r)


# Achsenparalleles Rechteck
class Rect:

    def __init__(self, x, y, w, h):
        self.x = x # x Koordinate "oben links"
        self.y = y # y Koordinate "oben links"
        self.w = w # Breite
        self.h = h # Höhe

    # Kollision Rechteck-Punkt
    def collide(self, x, y):
        return ((self.x <= x <= self.x + self.w) and
                 (self.y <= y <= self.y + self.h))

    # Kollision Rechteck-Rechteck
    def intersect(self, rect):
        return ((self.x < rect.x + rect.w) and (rect.x < self.x + self.w) and
                (self.y < rect.y + rect.h) and (rect.y < self.y + self.h))

    def __str__(self):
        return '<{0},{1};{2},{3}>'.format(self.x, self.y, self.w, self.h)

class Quadtree:

    def __init__(self, depth, rect):
        self.rect  = rect
        self.depth = depth
        self.ne = None
        self.se = None
        self.sw = None
        self.nw = None
        self.objs = list()
        if (depth > 1):
            w = self.rect.w / 2
            h = self.rect.h / 2
            x = self.rect.x + w
            y = self.rect.y
            self.ne = Quadtree(depth-1, Rect(x, y, w, h))
            w = self.rect.w / 2
            h = self.rect.h / 2
            x = self.rect.x + w
            y = self.rect.y + h
            self.se = Quadtree(depth-1, Rect(x, y, w, h))
            w = self.rect.w / 2
            h = self.rect.h / 2
            x = self.rect.x
            y = self.rect.y + h
            self.sw = Quadtree(depth-1, Rect(x, y, w, h))
            w = self.rect.w / 2
            h = self.rect.h / 2
            x = self.rect.x
            y = self.rect.y
            self.nw = Quadtree(depth-1, Rect(x, y, w, h))

    def insert(self, obj):
        if (not self.rect.intersect(obj.getRect())):
            return
        if (self.depth == 1):
            self.objs.append(obj)
        else:
            self.ne.insert(obj)
            self.se.insert(obj)
            self.sw.insert(obj)
            self.nw.insert(obj)

    def query(self, obj):
        inRange = list()
        if (not self.rect.intersect(obj.getRect())):
            return inRange
        if (self.depth == 1):
            for o in self.objs:
                if (obj.intersect(o)):
                    inRange.append(o)
        else:
            inRange.extend(self.ne.query(obj))
            inRange.extend(self.se.query(obj))
            inRange.extend(self.sw.query(obj))
            inRange.extend(self.nw.query(obj))
        return inRange


if __name__ == '__main__':
    import time, random

    size = 600
    depth = 5
    qtree = Quadtree(depth, Rect(0, 0, size, size))
    linear = list()
    for i in range(size):
        x = random.randint(0, size * 10) / 10.0
        y = random.randint(0, size * 10) / 10.0
        r = random.randint(0, size * 10) / 20.0
        c = Circle(x, y, r)
        qtree.insert(c)
        linear.append(c)
    print 'Strukturen (Liste und Quadtree der Tiefe {0}) mit {1} Objekten wurden erstellt.\n'.format(depth, size)

    prim = Circle(1.5, 1.5, 0.1)
    print 'Kreis {0} (mit Quadrat {1}) Kollisionen:'.format(prim, prim.getRect())
    s = time.time()
    objs = qtree.query(prim)
    e = time.time()
    #for o in objs:
    #    print o
    print '\t\t--> {0} Objekte gefunden'.format(len(objs))
    print 'Zeit Quadtree:\t\t{0}\n'.format(e-s)

    print 'Kreis {0} (mit Quadrat {1}) Kollisionen:'.format(prim, prim.getRect())
    s = time.time()
    objs = list()
    for o in linear:
        if prim.intersect(o):
            objs.append(o)
    e = time.time()
    #for o in objs:
    #    print o
    print '\t\t--> {0} Objekte gefunden'.format(len(objs))
    print 'Zeit lineare Liste:\t{0}'.format(e-s)

Code: Alles auswählen

Strukturen (Liste und Quadtree der Tiefe 4) mit 5000 Objekten wurden binnen 2.72023701668s erstellt.

Kreis <1.5,1.5:0.1> (mit Quadrat <1.4,1.4;0.2,0.2>) Kollisionen:
		--> 321 Objekte gefunden
Zeit Quadtree:		0.00606107711792

Kreis <1.5,1.5:0.1> (mit Quadrat <1.4,1.4;0.2,0.2>) Kollisionen:
		--> 321 Objekte gefunden
Zeit lineare Liste:	0.0397760868073

Code: Alles auswählen

if pred:
    return True
else:
    return False

Code: Alles auswählen

return pred