Files |  Tutorials |  Articles |  Links |  Home |  Team |  Forum |  Wiki |  Impressum

Aktuelle Zeit: Do Mär 28, 2024 16:04

Foren-Übersicht » Programmierung » Mathematik-Forum
Unbeantwortete Themen | Aktive Themen



Ein neues Thema erstellen Auf das Thema antworten  [ 10 Beiträge ] 
Autor Nachricht
 Betreff des Beitrags: Centroid einer Point Cloud?
BeitragVerfasst: Mo Apr 09, 2012 23:20 
Offline
DGL Member
Benutzeravatar

Registriert: Di Dez 03, 2002 22:12
Beiträge: 2105
Wohnort: Vancouver, Canada
Programmiersprache: C++, Python
Hi,

ich versuche den Centroid einer Point Cloud zu errechnen und verzweifle daran..

Es ist leider nicht damit getan eine BoundingBox drum rum zu packen und dann davon den Mittelpunkt zu nehmen, denn wenn man z.B. ein 2D-Dreieck mit den Werten [-1, -1], [-1, 1] und [1, 1] hat wäre der Mittelpunkt der BoundingBox nicht der Mittelpunkt des Dreiecks.

Alle punkte zusammen addieren und dann durch die Anzahl der Punkte teilen funktioniert auch nicht, denn wenn z.B. bei einem Dreieck bei einem der eck Punkte noch 20 andere Punkt liegen würden diese den Mittelpunkt sehr in ihre Richtung her verschieben bei dieser Rechnung.

Hat irgendjemand eine Idee wie man das berechnen kann?
Es ist wie gesagt eine Punkt Wolke, also keine Geometrische Form.. einfach ein häufen 3D Punkte..

Aya~


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Centroid einer Point Cloud?
BeitragVerfasst: Di Apr 10, 2012 08:45 
Offline
DGL Member
Benutzeravatar

Registriert: Fr Mär 30, 2007 18:35
Beiträge: 331
Aya hat geschrieben:
Alle punkte zusammen addieren und dann durch die Anzahl der Punkte teilen funktioniert auch nicht, denn wenn z.B. bei einem Dreieck bei einem der eck Punkte noch 20 andere Punkt liegen würden diese den Mittelpunkt sehr in ihre Richtung her verschieben bei dieser Rechnung.


Wenn du das nicht willst, dann Frage ich mich wonach du überhaupt suchst. Denn genau das wäre der Centroid deiner Punktewolke. Eventuell könntest du doppelte Punkte verwerfen, aber dann ist es wie gesagt kein Mittelpunkt mehr.

Edit: Ich habe gerade nochmal überlegt. Du könntest die konvexe Hülle der Punkte bilden und davon den Mittelpunkt nehmen. Das würde in dem geschilderten Fall den Mittelpunkt nicht "verschieben".


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Centroid einer Point Cloud?
BeitragVerfasst: Di Apr 10, 2012 09:32 
Offline
DGL Member
Benutzeravatar

Registriert: Di Dez 03, 2002 22:12
Beiträge: 2105
Wohnort: Vancouver, Canada
Programmiersprache: C++, Python
Hi,

eventuell nennt sich das was ich möchte nicht Centroid, das kann natürlich sein.

Das mit dem zusammen addieren funktioniert sehr schnell nicht mehr korrekt, noch ein simples beispiel:
Ein Zylinder der an einem ende viel feiner aufgelöst ist als am anderen, da würde sich der Mittelpunkt bei der Average-Rechenmethode Richtung hoch aufgelöstem Ende verschieben, obwohl rein von der Geometrie der Mittelpunkt dort ist wo er auch bei einem gleichmäßig aufgelösten Zylinder wäre.

Eine Hülle zu berechnen hatte ich auch überlegt, allerdings ist das bei einer Punkt Wolke auch nicht so sonderlich einfach.. daher hatte ich gehofft einen besseren Weg zu finden :/

Aya


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Centroid einer Point Cloud?
BeitragVerfasst: Di Apr 10, 2012 13:40 
Offline
DGL Member

Registriert: Mo Dez 26, 2005 22:27
Beiträge: 117
Programmiersprache: Pascal, C++
Wenn du Kenntnisse über die Geometrie hast kannst du möglicherweise die Punkte am "schlechter aufgelöstem Ende" stärker gewichten um den Verschiebungseffekt zu kompensieren?

_________________
Ein Computer wird das tun, was Du programmierst - nicht das, was Du willst.


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Centroid einer Point Cloud?
BeitragVerfasst: Di Apr 10, 2012 13:48 
Offline
DGL Member
Benutzeravatar

Registriert: Di Dez 03, 2002 22:12
Beiträge: 2105
Wohnort: Vancouver, Canada
Programmiersprache: C++, Python
Es ist wie gesagt eine Punkt Wolke, also keine Geometrie... ich nehme die Geometrie beispiele nur immer her weil sie anschaulicher sind.

Anderes Beispiel:
Ich habe 100 Points die sich bei [0, 0, -1] tummeln und nur 5 Stück die bei [0, 0, 1] liegen. Der Mittelpunkt sollte [0, 0, 0] sein, würde aber beim Averagen irgendwo in Richtung [0, 0, -0.6] oder so liegen.

Aya


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Centroid einer Point Cloud?
BeitragVerfasst: Di Apr 10, 2012 15:09 
Offline
Ernährungsberater
Benutzeravatar

Registriert: Sa Jan 01, 2005 17:11
Beiträge: 2067
Programmiersprache: C++
@Aya:
Entweder es ist eine Punktewolke, dann ist die Auflösung egal, oder es ist eine gerasterte Geometrie.
Nimm die konvexe Hülle und schau dir da vielleicht QHull an.

_________________
Steppity,steppity,step,step,step! :twisted:
❆ ❄ ❄ ❄ ❅ ❄ ❆ ❄ ❅ ❄ ❅ ❄ ❅ ❄ ❄
❄ ❄ ❄ ❅ ❄ ❄ ❄ ❅ ❄ ❄ ❆ ❄ ❄


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Centroid einer Point Cloud?
BeitragVerfasst: Di Apr 10, 2012 16:24 
Offline
DGL Member
Benutzeravatar

Registriert: Do Sep 02, 2004 19:42
Beiträge: 4158
Programmiersprache: FreePascal, C++
Die Konvexe Hülle hilft dir auch nicht unbedingt. Wenn die Punkte sich so tummeln, dass sie in der Hüllengeometrie eine hochaufgelöste Stelle bilden. Z.B. wenn die Punkte bei [0, 0, -1] eine Kugel mit Radius 0.1 aus 1024 vertices bilden, die bei [0, 0, 1] aber eine Kugel mit Radius 0.1 aus 64 vertices. Dann hast du nen abgerundeten Zylinder, bei dem das eine Ende ca. 512 Vertices hat und das andere ca. 32. Du kommst aus dieser Situation kaum raus, wenn du nicht mehr über die Geometrie weißt. Oder halt Punkte in einem gewissen Radius zusammenfasst und damit geringer gewichtest.

Könntest zum beispiel sagen, alles in einem Radius von 1/10 der kürzesten Bounding-Box-Kante wird erstmal zusammengefasst (gemittelt). Dann mittelst du über die gemittelten Punkte… Eventuell hilft das, muss aber auch nicht. Ist halt alles heuristik.

grüße

_________________
If you find any deadlinks, please send me a notification – Wenn du tote Links findest, sende mir eine Benachrichtigung.
current projects: ManiacLab; aioxmpp
zombofant networkmy photostream
„Writing code is like writing poetry“ - source unknown


„Give a man a fish, and you feed him for a day. Teach a man to fish and you feed him for a lifetime. “ ~ A Chinese Proverb


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Centroid einer Point Cloud?
BeitragVerfasst: Di Apr 10, 2012 20:43 
Offline
DGL Member

Registriert: Fr Okt 03, 2008 13:32
Beiträge: 367
Also so wie ich das verstanden hab, suchst du den Mittelpunkt einer möglichst kleinen Kugel, die alle Punkte umschließt.
Kann man das nicht einfach so machen, das man zu der Punktewolke die Boundingbox bestimmt und diese dann in 8 kleinere Quader teilt? Dann bestimmt man für alle 8 die maximale Distanz vom Mittelpunkt des Quaders zu allen Punkten. Danach wählt man die Box mit dem kleinsten max. Abstand und teilt sie wieder. Das wiederholt man dann einfach bis man ein ausreichend gutes Ergebnis hat.

Keine Ahnung ob das in Echtzeit geht und natürlich liefert es nur eine Näherungslösung außer du lässt das unendlich lange laufen (wenn du soviel Zeit hast :wink: ).


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Centroid einer Point Cloud?
BeitragVerfasst: Di Apr 10, 2012 21:42 
Offline
DGL Member
Benutzeravatar

Registriert: Do Dez 29, 2005 12:28
Beiträge: 2249
Wohnort: Düsseldorf
Programmiersprache: C++, C#, Java
Also wenn du eine ungefähre, dafür aber schnelle Lösung möchtest, nimm den Mittelpunkt der BoundingBox.

Das ganze ist keine einfaches Problem. Für die optimale Lösung suche mal nach "optimal bounding sphere", da findet sich z.B. das hier:
http://www.gamedev.net/page/resources/_ ... elzl-r2484
Der beschriebene Algorithmus soll im Erwartungsfall eine lineare Laufzeit haben, im Worstcase O(n²).

_________________
Yeah! :mrgreen:


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Centroid einer Point Cloud?
BeitragVerfasst: Do Apr 12, 2012 23:27 
Offline
Guitar Hero
Benutzeravatar

Registriert: Do Sep 25, 2003 15:56
Beiträge: 7804
Wohnort: Sachsen - ERZ / C
Programmiersprache: Java (, Pascal)
Wenn die Bounding-Volumes nicht sind wonach du suchst, wäre es vielleicht hilfreich, du umreist kurz wozu du den Mittel/Schwerpunkt brauchst.

_________________
Blog: kevin-fleischer.de und fbaingermany.com


Nach oben
 Profil  
Mit Zitat antworten  
Beiträge der letzten Zeit anzeigen:  Sortiere nach  
Ein neues Thema erstellen Auf das Thema antworten  [ 10 Beiträge ] 
Foren-Übersicht » Programmierung » Mathematik-Forum


Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 9 Gäste


Du darfst keine neuen Themen in diesem Forum erstellen.
Du darfst keine Antworten zu Themen in diesem Forum erstellen.
Du darfst deine Beiträge in diesem Forum nicht ändern.
Du darfst deine Beiträge in diesem Forum nicht löschen.
Du darfst keine Dateianhänge in diesem Forum erstellen.

Suche nach:
Gehe zu:  
cron
  Powered by phpBB® Forum Software © phpBB Group
Deutsche Übersetzung durch phpBB.de
[ Time : 0.085s | 19 Queries | GZIP : On ]