Konvexe Hülle Problem

[Max]

Hallo,

Kann mir jemand -in für einen Nicht-Informatiker verständlicher Weise-den Algorhitmus zum Bestimmen der äusseren Punkte einer Punktwolke (Konvexe Hülle) im Raum erklären?
Die Netz-Recherche führt mich hierzu auf Uni-Seiten von Informatik Fakultäten oder zu Profi-Programmierern.
Des ist für mich zugegebener massen zu harter Stoff.
Und nebenher ein halbes Informatik Grundstudium rein zupfeifen, des schaff ich nich.

Da kam mir die Idee hier mal anzufragen :wink:

Ich könnte mir gut vorstellen, dass sich hier einige Freaks (Semi-Programmierprofis/Profis/Informatiker...) tummeln, die mir als Nicht Informatiker diesen Algorhitmus erkläeren könnten.
Code wäre nicht zwingend nötig, Prosa tut's auch.

In Hoffnung auf Eure- wie immer geschätzten Antworten- grüsst
Max

 

[Oxygenic]

Also wenn ich selber einen Algorithmus erfinden müsste (da ich sowas auch noch nie gemacht habe), würde ich erst den mittleren Abstand zwischen allen Punkten ermitteln und dann bei jeden Punkt einzeln untersuchen, wie groß sein Abstand vom Mittelpunkt des Objektes ist. Findet sich für diesen dann innerhalb dieses mittleren Punkteabstandes ein Punkt, der weiter von der Mitte entfernt ist, als der aktuell betrachtete, so dürfte der aktuelle nicht zur Hülle gehören.

Das Ergebnis dürften dann alle Punkte sein, die zur Hülle gehören. Ein bissl Feintuning mag allerdings noch nötig sein.

cu

Oxy

http://forum.javacore.de - das Java-Forum!
http://www.3dchat.org - Welcome To The unreal World!

 

[Max]

Also wenn ich selber einen Algorithmus erfinden müsste (da ich sowas auch noch nie gemacht habe), würde ich erst den mittleren Abstand zwischen allen Punkten ermitteln und dann bei jeden Punkt einzeln untersuchen, wie groß sein Abstand vom Mittelpunkt des Objektes ist. Findet sich für diesen dann innerhalb dieses mittleren Punkteabstandes ein Punkt, der weiter von der Mitte entfernt ist, als der aktuell betrachtete, so dürfte der aktuelle nicht zur Hülle gehören.

Das Ergebnis dürften dann alle Punkte sein, die zur Hülle gehören. Ein bissl Feintuning mag allerdings noch nötig sein.

cu

Oxy

http://forum.javacore.de - das Java-Forum!
http://www.3dchat.org - Welcome To The unreal World!

Hi Oxy,
Wenn ich Dich richtig verstanden habe würdest Du das über die Vektor-Beträge, also über den Abstand der Punkte
vom Mittelpunkt lösen.
Die Idee hatte ich auch, dann kann es aber z.B. passieren, dass ein punkt mit kleinerem Abstand als ein Anderer Trotzdem zur Hülle gehört, weil er einfach eine andere Richtung hat.
Vielleicht muss da irgenswie noch die Winkel mit einbauen, mal sehen.
Danke erstmal.
Falls Du oder jemand Anderes noch Ideen hat oder das viellecht schon mal gemacht hat (Code wäre natürlich das Höchste) immer her damit, bitte.

Grüsse
Max

 

[Oxygenic]

Ja, deswegen ja die Geschichte mit dem Abstand! Ist ein Punkt zu weit weg von dem einen, der weiter innen liegt, so zählt er nicht mit, d.h. der innen liegendere würde trotzdem verwendet werden.

cu

Oxy

http://forum.javacore.de - das Java-Forum!
http://www.3dchat.org - Welcome To The unreal World!