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:

1. Laut print-Ausgabe in der Shell werden scheinbar die letzten beiden Linien als schneidend klassifiziert, obwohl der angebliche Schnitt sich bei 1 und 1 befindet (Schnitt werden angegeben zwischen 0 und 1, wobei 0 der Startpunkt der Linie und 1 der Endpunkt ist). Eigentlich sollte dies jedoch durch <1 und >0 eindeutig unterbunden werden.
2. Das Kreuz entsteht durch eine Indize-Verschiebung, wodurch die neue Linie mit dem Index der beriets gelöschten Linie in der Überprüfung „übersehen“ wird.

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.