Python :: Aufgabe #156
2 Lösungen
Konvexe Hüllkurve um Punktwolke
Fortgeschrittener - Python
von hollst
- 04.05.2017 um 10:36 Uhr
In der X-Y-Ebene seinen N Punkte zufällig verteilt (Bild 1). Man schreibe ein Programm, das die konvexe Hüllkurve um diese Punktwolke zeichnet (Bild 2).
Zum Verständnid, was die konvexe Hüllkurve um eine Punktwolke ist, stelle man sich die Punkte als fixierte Push-Pins oder Nägel auf einem Pinbord (möglichst nicht aus Kork) oder Holzbrett vor. Jetzt nehme man einen Gummiring (z. B. vom Einweckglas) und spanne diesen so um die Pins, dass sich alle im „Inneren“ des Gummiringes befinden (eine „360-Grad-Umwicklung“ eines Pins ist nicht erlaibt). Der so verformte Gummiring ergibt aus physikalischen Gründen einen geschlossenen Linienzug. Dieser Linienzug wird konvexe Hüllkurve um die Punktwolke genannt.
Zum Verständnid, was die konvexe Hüllkurve um eine Punktwolke ist, stelle man sich die Punkte als fixierte Push-Pins oder Nägel auf einem Pinbord (möglichst nicht aus Kork) oder Holzbrett vor. Jetzt nehme man einen Gummiring (z. B. vom Einweckglas) und spanne diesen so um die Pins, dass sich alle im „Inneren“ des Gummiringes befinden (eine „360-Grad-Umwicklung“ eines Pins ist nicht erlaibt). Der so verformte Gummiring ergibt aus physikalischen Gründen einen geschlossenen Linienzug. Dieser Linienzug wird konvexe Hüllkurve um die Punktwolke genannt.
Lösungen:
Python-Code
#konvexe_Menge.py from random import randint from tkinter import * from math import sqrt import numpy as np #N Anzahl der Punkte class Huelle(object): def __init__(self,N): self.n=N self.f1=None self.layout() self.fenster.mainloop() def convex(self): self.t.insert(END,'Hüllenpunkte:\n') #self.t.insert(END,'Nächstgelegenster Punkt:'+str(start)) self.start=self.kleinst() x1,y1=self.start print(self.start) print(self.points) a=np.array([-1,0]) winkel=[] #self.points.remove(self.start) anf_punkt=(0,0) while anf_punkt != self.start: for punkt in self.points: x2,y2=punkt b=np.array([x2-x1,y2-y1]) dot = np.dot(b,a) b_modulus = np.sqrt((b*b).sum()) a_modulus = np.sqrt((a*a).sum()) cos_angle = dot / b_modulus / a_modulus angle = np.arccos(cos_angle)* 360 / 2 / np.pi winkel.append((angle,punkt)) winkel.sort() anf_punkt=winkel[0][1] self.t.insert(END,str(anf_punkt)+'\n') x2,y2=anf_punkt self.points.remove(anf_punkt) self.c.create_line(x1,y1,x2,y2,fill='red') a=np.array([x2-x1,y2-y1]) x1,y1=x2,y2 winkel=[] def punkte(self): self.t.insert(END,'\n') for i in range(self.n): x=randint(30,370) y=randint(30,370) self.points.add((x,y)) #self.t.insert(END,'['+str(x)+';'+str(y)+']\n') self.c.create_rectangle(x-2,y-2,x+2,y+2) self.start=self.kleinst() self.t.insert(END,'Nächstgelegenster hinzugefügter Punkt:'+str(self.start)+'\n') def kleinst(self): abstaende={} for (x,y) in self.points: abstand=sqrt(x**2+y**2) abstaende[abstand]=(x,y) P=min(abstaende.keys()) return abstaende[P] def clear(self): self.points=set() if self.f1: self.f1.destroy() self.f1=Frame(self.fenster) self.c=Canvas(self.f1,width=400,height=400,bg='green') self.t=Text(self.f1) self.f1.pack(side=TOP) self.c.pack(side=LEFT) self.t.pack(side=LEFT) def layout(self): self.fenster=Tk() self.fenster.title("Konvexe Hülle") self.clear() self.f2=Frame(self.fenster) self.f2.pack(side=BOTTOM) Button(self.f2,text="clear canvas",command=self.clear).pack(side=LEFT) Button(self.f2,text="draw new points",command=self.punkte).pack(side=LEFT) Button(self.f2,text="Convex line",command=self.convex).pack(side=LEFT) Huelle(20)
#Vielen Dank an User Hollst! Wirklich tolle Ideen!
Python-Code
import numpy as np import matplotlib.pyplot as plt from scipy.spatial import ConvexHull points = np.random.rand(30, 2) hull = ConvexHull(points) plt.plot(points[:, 0], points[:, 1], 'ro') for simplex in hull.simplices: plt.plot(points[simplex, 0], points[simplex, 1], 'k-') plt.grid(True) plt.show()