29.01.2020

<< | Home | >>

[ Lukas ]

Im Gespräch mit einem MINTgrün Tutor ist der Begriff „Delaunay - Triangulation“ aufgetaucht. Anscheinend handelt es sich um eine spezielle Art der Verknüpfung einer Punktmenge, die sehr ähnlich zu dem „Dreiecksmuster“ ist, welches wir als Basis für unsere Version verwendet haben. Nach dem Lesen mehrerer verschiedener Paper zu diesem Thema präsentieren wir hier ein komplett neu geschriebenes Programm, welches fehlerlos ein Voronoidiagramm über eine komplett zufällige Punktmenge generiert. Im Gegensatz zu unserem alten Programm müssen wir hier keine Ungenauigkeiten von numpy-Arrays in Kauf nehmen, sondern generieren das komplette Diagramm mathematisch korrekt mithilfe eines Kreiskriteriums (und mit einer neuen Farbgebung auch noch stylisch). Somit werden wir uns im morgigen Termin mithilfe von Blender der Generation im R^3 - Raum widmen.

Kreiskriterium Drei Punkte im R^2 reichen aus (mathematisch bewiesen!), um einen Kreis eindeutig zu beschreiben. Somit ist es notwendig, über die zufällig generierte Punktmenge zu iterieren und alle möglichen Kombinationen aus drei verschiedenen Kernen zu überprüfen. Für jede Kombination wird eine Kreisgleichung berechnet und geprüft, ob innerhalb des Kreises ein weiterer Punkt liegt. Trifft dies nicht zu, handelt es sich bei den drei Punkten um die Eckpunkte eines Dreieckes der echten Delaunay-Triangulation.

Aktueller Code:

# -*- coding: utf-8 -*-
"""
Created on Wed Jan 29 09:45:25 2020
 
@author: Lukas
"""
 
 
import numpy as np
import math
import turtle
import random as rn
#import copy
 
turtle.speed(0)
turtle.ht()
turtle.pensize(1)
 
 
 
#   VARIABLEN
 
anzahlKerne = 40
max_x = 450
max_y = 250
 
ger_index = 0
 
 
#   KLASSEN
 
class Gerade(object):
    ov = (0,0)      #Ortsvektor
    rv = (0,0)      #Richtungsvektor
 
    index = 0
 
    kerne = (0,0)   #   gibt an, welche Kerne durch die Linie verbunden werden
 
    def __init__(self,kerne):
        self.kerne = kerne
 
        self.ov = kerne[0]
        self.rv = np.subtract(kerne[1],kerne[0])
 
    def punktAn(self,k):
        a = self.ov + self.rv*k
        return a
 
    def toString():
        print("OV : "+Gerade.ov+" RV : "+Gerade.rv+" Kerne "+Gerade.kerne)
 
class Kreis(object):
    mp = (0,0)      #   mittelpunkt
    radius = 0      #   radius
 
    epsilon = 0.001
 
    def __init__(self, mp, radius):
        self.mp = mp
        self.radius = radius
 
    def imKreis(self,p):
        if (abstand(self.mp,p) < self.radius - self.epsilon):
            return True
        else: return False
 
    def zeichne(self):
        turtle.penup()
        turtle.goto((self.mp[0],self.mp[1]-self.radius))
        turtle.pendown()
        turtle.circle(self.radius)
 
class Dreieck(object):
    p = []          #   Punkte, die das Dreieck bilden
    g = []          #   Geraden, die das Dreieck bilden
    mp = (0,0)      #   Mittelpunkt, der aus diesem Dreieck hervorgeht
    #uk = Kreis((0,0),0)           #   umkreis des Dreiecks
 
    def __init__(self,p):
        self.p = p
        self.mp = self.mittelpunkt()
        self.g = self.genGeraden()
 
        #self.g = [Gerade((self.p[0],self.p[1])), Gerade((self.p[1],self.p[2])), Gerade((self.p[0],self.p[1]))]
 
        #self.uk = self.umkreis
 
    def zeichne(self):
        zeichneLinie(self.p[0],self.p[1])
        zeichneLinie(self.p[1],self.p[2])
        zeichneLinie(self.p[2],self.p[0])
 
    def genGeraden(self):
        g1 = Gerade((self.p[0],self.p[1]))
        g2 = Gerade((self.p[1],self.p[2]))
        g3 = Gerade((self.p[2],self.p[0]))
 
        ger = [g1,g2,g3]
        return ger        
 
    def mittelpunkt(self):
        #   soll zuerst die Geraden des Dreiecks ermittlen
        g1 = Gerade((self.p[0], self.p[1]))
        g2 = Gerade((self.p[1], self.p[2]))
 
        g1.ov = g1.ov + .5*g1.rv
        g2.ov = g2.ov + .5*g2.rv
 
        g1.rv = rechtW(g1.rv)
        g2.rv = rechtW(g2.rv)
 
        mitte = schnittPunkt(g1,g2)  
 
        return mitte
 
        #   ermittelt Abstand Mittelpunkt - Eckpunkt -> Radius
 
    def umkreis(self):
        a = abstand(self.mp,self.p[0])
        u = Kreis(self.mp,a)
 
        return u
 
#   FUNKTIONEN
 
def generiereKernListe(n,maxx,maxy):
    #   generiert eine Liste von Punkten im R^2
    liste=[]
 
    for c in range(n):
        x = rn.randint(-maxx,maxx)#rn.uniform(0,maxx)
        y = rn.randint(-maxy,maxy)#rn.uniform(0,maxy)
 
        liste.append((x,y))
 
    return liste
 
def abstand(p1,p2):
    return math.sqrt((p2[0]-p1[0])**2+(p2[1]-p1[1])**2)
 
def rechtW(v):
    #   findet einen Vektoren im rechten Winkel zu dem gegebenen Vektor
    v_neu = np.array((-v[1],v[0]))
    return v_neu
 
def zeichneLinie(start,ende):
    #   zeichnet eine Linie zwischen start und ende mithilfe einer turtle
    turtle.penup()
    turtle.goto(start)
    turtle.pendown()
    turtle.goto(ende)  
 
def zeichnePunkt(pos):
    turtle.penup()
    turtle.goto(pos[0]-5,pos[1]-5)
    turtle.pendown()
    turtle.goto(pos[0]+5,pos[1]-5)
    turtle.goto(pos[0]+5,pos[1]+5)
    turtle.goto(pos[0]-5,pos[1]+5)
    turtle.goto(pos[0]-5,pos[1]-5)
    turtle.penup()
 
def schnittTest(g1,g2):
    #   testet, ob g1 und g2 sich schneiden
    return np.linalg.solve([[g2.rv[0],-g1.rv[0]],[g2.rv[1],-g1.rv[1]]],[[g1.ov[0]-g2.ov[0]],[g1.ov[1]-g2.ov[1]]])
 
def schnittPunkt(g1,g2):
    z = schnittTest(g1,g2)
    k = g2.punktAn(z[0][0])
    #zeichnePunkt(k)
    return k
 
#c = circle((0,1),5)
 
 
 
 
#   PROGRAMM
 
ker = generiereKernListe(anzahlKerne,max_x,max_y)
drei = []
 
for i in ker:
    zeichnePunkt(i)
 
for i in range(0,len(ker)):
    for j in range(i+1,len(ker)):
        for k in range(j+1,len(ker)):
            d = Dreieck([ker[i],ker[j],ker[k]])
            #d.g = [Gerade((ker[0],ker[1])), Gerade((ker[1],ker[2])), Gerade((ker[0],ker[1]))]
 
            frei = True
 
            for l in ker:
                if(d.umkreis().imKreis(l) == True):
                    frei = False
 
            if (frei == True):
                drei.append(d)
 
for d in drei:
    turtle.pensize(1)
    turtle.color("gainsboro")
    d.umkreis().zeichne()
    turtle.color("mediumspringgreen")
    turtle.pensize(2)
    d.zeichne()
 
 
 
turtle.color("dimgrey")
turtle.pensize(3)
 
#for m in drei:
#    print(m.g[0].ov,"\n")
#    print(m.mp,"\n")
 
for m in drei:
    for n in drei:
        if (m != n):
            #print(m.g[0]," and ", n.g)
 
            if (m.g[0].kerne in n.g[0].kerne):print("yes")
            nachbarn = False
 
            for o in m.g:
                for p in n.g:
                    if ((o.kerne[0] in p.kerne) and (o.kerne[1] in p.kerne)):
                        nachbarn = True
 
            if (nachbarn == True):
                zeichneLinie(m.mp, n.mp)
 
            #if (((m.g[0].kerne[0] and m.g[0].kerne[1]) in n.g[0].kerne) or (m.g[1] in n.g) or (m.g[2] in n.g)):                
            #    zeichneLinie(m.mp, n.mp)
 
 
#d = Dreieck([ker[0],ker[1],ker[2]])
#d.zeichne()
#zeichnePunkt(d.mp)
 
#zeichnePunkt(mitteAusDreieck(d))
 
 
 
#for i in range(1,len(ker)):
#    zeichneLinie(ker[i-1],ker[i])
#zeichneLinie(ker[0],ker[len(ker)-1])
 
 
 
 
turtle.Screen().exitonclick()