====== Sechster Arbeits-Termin ====== **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. {{:ws1920:rechtewinkelbild.jpg?400|}} 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!!! {{:ws1920:zwischendings.jpg?400|}} ----