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..
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".
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 :/
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.
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.
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.
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 network • my 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
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 ).
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²).
Mitglieder in diesem Forum: 0 Mitglieder und 1 Gast
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.