16.01.2020

Wir haben uns heute darum gekümmert, dass die verschiedene Fehler noch etwas seltener auftauchen als zuvor (anpassung des Epsilonbereiches). Dann haben wir uns mit den Möglichkeiten auseinandergesetzt, dass tatsächliche Voronoi zu generieren.

Abb. Generationsstand 17:02 Uhr

Außerdem haben wir eine Methode geschrieben, die den Winkel zwischen zwei verschiedenen Vektoren ausgibt. So können wir herausfinden, welche beiden Linien links und rechts von einer Verbindungslinie sind (wichtig für die Auswahl der Voronoi-Linien, bei denen die Schnittpunkte gefunden werden sollen).

# -*- coding: utf-8 -*-
"""
Created on Thu Dec 19 15:31:18 2019
 
@author: Lukas
"""
 
import numpy as np
import math
import turtle
import random as rn
 
turtle.speed(0)
turtle.ht()
 
#   VARIABLEN
 
anzahlKerne = 15
max_x = 300
max_y = 300
 
 
 
#   KLASSEN
 
class Gerade(object):
    ov = (0,0)    #Ortsvektor
    rv = (0,0)    #Richtungsvektor
    l  = 0;          #Laenge
 
    kerne = (0,0)
 
    def toString():
        print("OV : "+Gerade.ov+" RV : "+Gerade.rv+" Kerne "+Gerade.kerne)
 
#   METHODEN    
 
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 zeichneLinie(start,ende):
    #   zeichnet eine Linie zwischen start und ende mithilfe einer turtle
    turtle.penup()
    turtle.goto(start)
    turtle.pendown()
    turtle.goto(ende)
 
def richtungLinie(start,ende):
    #   gibt den Richtungsvektor von start nach ende aus
    richtung  = np.subtract(ende,start)
    return richtung
 
def schnittTest(g1,g2):
    #   testetm 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 vektorLänge(v2):
    #   errechnet die Laenge eines Vektors
    v1 = np.array([0,0])
    return math.sqrt((abs(v1[0]-v2[0])**2)+(abs(v1[1]-v2[1])**2))
 
def vektorNorm(v):
    #   normiert einen Vektor
    return(1/math.sqrt(v[0]**2+v[1]**2)*v)
 
def punktAufLinie(p,o,r):
    #   liegt punkt p auf der geraden g = o + m*r?    
    if(np.array_equal(p,o)): return False
    elif(np.array_equal(r,[0,0])): return False
    elif(r[1] == 0): 
        a = (p[0]-o[0])/r[0]
        if (o[1]+a*r[1] == p[1]):
            if(a<1 and a>0): return True
            else: return False
        else: return False
    else: 
        a = (p[1]-o[1])/r[1]
        if (o[0]+a*r[0] == p[0]):
            if(a<1 and a >0): return True
            else: return False
        else: return False
 
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 zwischenWinkel(a,b):
    #   gibt den Winkel zwischen zwei Vektoren aus
    w = (a[0]*b[0]+a[1]*b[1])/(math.sqrt(a[0]**2+a[1]**2)*math.sqrt(b[0]**2+b[1]**2))
    w = math.degrees(math.acos(w))
    return w
 
#   MAIN
 
#   genriert die Liste der Kerne
ker = generiereKernListe(anzahlKerne,max_x,max_y)
 
print("Kerne : ",ker)
 
 
listeGeraden = []
 
#   generiert alle Linien zwischen den Kernen
for i in range(0,anzahlKerne):
    for k in range(i,anzahlKerne):
        if (i!=k):
 
            eineGerade     = Gerade()
            eineGerade.ov  = np.array(ker[i])
            eineGerade.rv  = np.subtract(ker[k],ker[i])
            eineGerade.l   = vektorLänge(eineGerade.rv)
 
            # welche Kerne verbindet die Linie?
            eineGerade.kerne = (i,k)
 
            listeGeraden.append(eineGerade)
 
 
#   zeichnet alle Linien zwischen allen Punkten
turtle.color("cyan")
for i in range(0, len(listeGeraden)):
    zeichneLinie(listeGeraden[i].ov,listeGeraden[i].ov+listeGeraden[i].rv)
 
schnitt = 0
l = len(listeGeraden)
 
#testet, welche geraden gelöscht werden sollen
 
i = 0
k = 0
 
epsilon = 0.0001 #*anzahlKerne
 
while (i < l):
    k = i+1
    while (k < l):
        z = [0,0]
        if(i!=k):
            #for k in range(i+1, l):
            try:
                #   schneiden sich die Linien?
                z = schnittTest(listeGeraden[i],listeGeraden[k])
 
                if (z[0][0]<1-epsilon and z[0][0]>0+epsilon and z[1][0]<1-epsilon and z[1][0]>0+epsilon):
                    #print("\n\n ",i," OV ",listeGeraden[i].ov," ",i," RV ",listeGeraden[i].rv," ",k," OV ",listeGeraden[k].ov," ",k," RV ",listeGeraden[k].rv)
                    #print("vergleiche ",i," und ", k)
                    #print("Schnitt\n",z[0][0],z[1][0])
                    schnitt=schnitt+1
                    #del listeGeraden[i]   #ACHTUNG: EIGENTLICH SOLL DIE LÄNGERE GELÖSCHT WERDEN
 
                    #print("laenge a : ",listeGeraden[i].l," laenge b : ",listeGeraden[k].l,"\n",10*" - ")
                    if (listeGeraden[i].l < listeGeraden[k].l):
                        del listeGeraden[k]
                        i=0
                    else: 
                        del listeGeraden[i]
                        k=0
            except:
                #print("# end of this iteration")
                break
        k=k+1
    i=i+1
 
#for i in range(0, l):
#    for k in range(i+1, l):
 
 
 
listeRGeraden = []
 
for i in range(0, len(listeGeraden)):
    neueGerade = Gerade()
    neueGerade.ov = listeGeraden[i].ov+(.5*listeGeraden[i].rv)
    neueGerade.rv = rechtW(listeGeraden[i].rv)
 
    listeRGeraden.append(neueGerade)
 
 
 
print("Schnitte : ", schnitt)
 
for i in range(0, len(listeGeraden)):
    turtle.color("black")
    turtle.pensize(2)
    zeichneLinie(listeGeraden[i].ov,listeGeraden[i].ov+listeGeraden[i].rv)
    print(listeGeraden[i].kerne)
 
    turtle.color("red")
    turtle.pensize(1)
    zeichneLinie(listeRGeraden[i].ov,listeRGeraden[i].ov+listeRGeraden[i].rv)
 
 
turtle.Screen().exitonclick()
#turtle.done()
 
 
 
# Gute Kernlisten:
 
# beste : [(52, 199), (101, 243), (-227, -48), (5, 213), (26, -294), (197, 174), (57, -275), (-61, -63), (206, 6), (-112, 62), (26, 105), (247, 121), (287, 161), (152, 272), (209, -94)]
# beste : [(-92, 125), (-172, -127), (282, 26), (43, 114), (52, -6), (-155, -212), (-187, 135), (125, -30), (-78, -80), (8, -165), (-292, -8), (140, -7), (-252, -254), (-47, -19), (292, -225)]
 
# 15 : [(-214, -223), (65, 86), (113, -226), (227, -199), (8, -5), (94, 193), (-218, -280), (108, -30), (206, 217), (-21, -292), (215, 112), (-289, -86), (-127, 50), (-257, 298), (-194, 254)]
# 15 : [(-158, 54), (181, -2), (-55, -230), (158, 192), (106, -216), (150, -88), (156, -245), (-22, 261), (67, 2), (-47, -27), (81, -28), (81, -252), (290, -54), (282, 286), (-32, -188)]
# 15 : [(166, 27), (-152, 245), (-152, 79), (-64, 298), (259, -222), (98, 177), (38, 227), (-40, -201), (55, 68), (-291, 272), (60, -232), (143, -282), (-86, 49), (53, 270), (160, -177)]
# 25 : [(-98, 152), (8, 295), (-153, -130), (-272, 86), (-92, 57), (157, 255), (-121, 134), (-42, -17), (-57, -238), (-290, -26), (-233, 8), (-271, 160), (27, 43), (-32, 292), (108, -297), (-41, 207), (67, -111), (-209, -224), (172, -288), (255, -136), (105, -229), (166, 42), (-145, -288), (33, 193), (77, 78)]
#  7 : [(76, -55), (-297, -51), (162, -110), (-50, -9), (125, 18), (-21, 35), (-259, 175), (-194, 23), (-243, -147), (181, -288)]
 
# 30 : [(-168, -165), (94, -217), (-10, 185), (-90, 224), (-140, 246), (189, 28), (297, -126), (-211, 290), (71, -6), (-298, -79), (-78, 51), (277, -97), (135, 56), (47, 107), (182, -138), (258, -241), (-292, 3), (257, -188), (227, -261), (90, -2), (-228, 19), (153, -44), (-169, -146), (225, 33), (78, 166), (142, 238), (0, -105), (217, 83), (211, -195), (-142, -79)]
# 30 : [(253, 63), (-202, 25), (117, -194), (271, 247), (-84, -96), (145, 215), (-81, -145), (157, -297), (-157, 80), (217, 164), (175, -253), (-190, -48), (-122, 193), (253, -268), (-211, -81), (-121, 64), (-249, -25), (244, 298), (-42, 98), (-144, 218), (42, -56), (-141, 118), (125, 63), (-119, -21), (-79, 238), (21, 272), (100, -107), (147, 25), (-170, -54), (260, 267)]

Lukas Aktualisierung :

• Schnittpunkt wird nicht mehr getestet, falls zwei Linien in denselben Kern laufen (funktioniert nun fast immer fehlerfrei, Epsilon - Abweichung erübrigt sich dadurch).
• Methode xAchseWinkel implementiert (gibt Winkel eines Vektors zur X-Achse an)
• Voronoi werden endlich mehr oder weniger gezeichnet!!!