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-Codeimport 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()