09.01.2020
Frohes Neues Jahr!
Wir beginnen wie letztes Jahr bereits beschrieben damit, zwei fehlerhafte Kernsätze zu untersuchen. Mit etwas Glück finden wir somit die Fehlerquelle und können diese mit noch mehr Glück ausmerzen. Im folgenden eine Visualisierung der beiden Kernsätze.
1. Linie fehlt : [(287, 92), (-218, -98), (-269, -216), (-72, 160), (-222, 60)]
2. Kreuz enthalten : [(-47, 256), (30, 171), (-34, -66), (-52, -9), (-137, 95)]
Ersteinmal die gute Nachricht: Die Fehler tauchen auf nach mehrmaliger Durchführung mit denselben Kernlisten auf, somit muss es irgendwo „echte“ Fehler im Code geben (es liegt also an uns und nicht an irgendeinem merkwürdigen Bug).
Gefundene Logikfehler im Code:
Hier die Lösungswege für die entsprechenden Fehler
1. Wir haben ein Epsilon mit dem Wert 0.001*AnzahlKerne gewählt, sodass Schnittpunkte, die extrem nah an einem Kern sind, nicht beachtet werden. Diese sind mit einer sehr hohen Wahrscheinlichkeit (Wir waren zu faul die auch noch auszurechnen…) nicht tatsächliche Schnittpunkte sondern eigentlich Knotenpunkte, sodass wir diese Ungenauigkeit in Kauf nehmen. Der eigentliche Fehler liegt darin, dass Python in numpy-Arrays irgendwann die einzelnen Komponenten runden muss. Da aber der Schnittpunktabgleich Schnittpunkte in den Knotenpunkten findet, kommt es zu den Fehlern.
2. Wir haben die for-Schleife, die für den Vergleich der Linien verantwortlich ist, gegen eine while-Schleife ersetzt und dann die Indizies manuell angepasst, sobald eine Linie rausgelöscht wird.
Somit haben wir die Probleme unseres Vormodells einigermaßen in den Griff bekommen und können uns nächste Woche mit dem nächsten Schritt befassen, indem wir die Rechtwinkellinien einsetzten und hoffentlich bald ein richtiges Voronoi generieren können.
# -*- 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 = 30 # KLASSEN class Gerade(object): ov = (0,0,0) #Ortsvektor rv = (0,0,0) #Richtungsvektor l = 0; #Laenge # METHODEN def generiereKernListe(n,maxx,maxy,abstand): # 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 # MAIN # genriert die Liste der Kerne ker = generiereKernListe(anzahlKerne,300,300,0.1) #ker = [(287, 92), (-218, -98), (-269, -216), (-72, 160), (-222, 60)] #ker = [(-47, 256), (30, 171), (-34, -66), (-52, -9), (-137, 95)] #anzahlKerne = 5 print("Kerne : ",ker) # ** Fehlerhafte Kernliste zum Testen!! ** #ker = [(-151, 245), (170, 0), (-78, 171), (-48, 122), (-6, -199), (-13, -162)] #ker = [(-260, 261), (271, 107), (-127, -218), (239, -245), (181, 256), (115, -293)] 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) listeGeraden.append(eineGerade) # zeichnet alle Linien zwischen allen Punkten #turtle.color("red") #for i in range(0, len(listeGeraden)): # zeichneLinie(listeGeraden[i].ov,listeGeraden[i].ov+listeGeraden[i].rv) turtle.color("black") turtle.pensize(2) schnitt = 0 l = len(listeGeraden) #testet, welche geraden gelöscht werden sollen i = 0 k = 0 epsilon = 0.001*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): print("Schnitte : ", schnitt) for i in range(0, len(listeGeraden)): zeichneLinie(listeGeraden[i].ov,listeGeraden[i].ov+listeGeraden[i].rv) turtle.Screen().exitonclick() #turtle.done() # Schöne Fehler: # Linie Fehlt einfach : [(287, 92), (-218, -98), (-269, -216), (-72, 160), (-222, 60)] # Kreuz enthalten : [(-47, 256), (30, 171), (-34, -66), (-52, -9), (-137, 95)]
Der finale Generationsstand enthält nun recht selten Fehler, aber damit müssen wir es nun belassen. Zum Abschluss des Projektes können wir nochmal nach einer Methode suchen, wie die Rundung von numpy-Arrays unterbunden werden kann, nächste Woche setzten wir uns dann aber zunächst mit dem nächsten Schritt des Voronoi-Diagramms auseinander.