Python :: Aufgabe #156

2 Lösungen Lösungen öffentlich

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.

Lösungen:

vote_ok
von 0 (0 Punkte) - 28.10.2017 um 23:19 Uhr
Quellcode ausblenden 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!
vote_ok
von satn1241 (3090 Punkte) - 17.04.2020 um 12:50 Uhr
Quellcode ausblenden 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()
1800448

Du scheinst einen AdBlocker zu nutzen. Ich würde mich freuen, wenn du ihn auf dieser Seite deaktivierst und dich davon überzeugst, dass die Werbung hier nicht störend ist.