c++.de :: Normale an einem Punkt

daishi Mitglied 10:48:11 11.12.2003 Titel:

Hi,
ich will in einer Punktewolke im R³ die Normalenvektoren an den Punkten bestimmen.

Die Punktewolke hat folgende Eigenschaften:
- Die Punkte sind Äquidistant auf dem X-Y-Raster verteilt.
- Es können Löcher (nicht definierte Punkte) auftreten, aber jeder Punkt besitzt mindestens einen Nachbarn.
- Es besteht eine eindeutige Abbildung (x,y)->z

Meine Ansätze sind bisher:
1: Durch die 5er-Umgebung des Punktes wird eine Ausgleichsebene gelegt, der Normalenverktor dieser Ebene ist die Normale in diesem Punkt.

2: Hier berechne ich 2 Ausgleichsgeraden XZ-Ebene und YZ-Ebene. Aus den beiden Richtungsvektoren berechne ich dann den Normalenvektor.

Mein Problem ist nun, daß beide Verfahren recht rechenaufwendig sind und numerische Instabilitäten aufweisen. Daher wollte ich mal fragen, ob jemand noch eine Lösung kennt, die mir weiterhelfen könnte.

Danke

Winn Mitglied 11:35:28 11.12.2003 Titel:

Hey Daishi,

Öhm... dürfte paßen, ich würde folgendes mal ausprobieren... probiere jeweils z.B. 4 Funktionswerte derart auf die xy Ebene zu projezieren, daß sie "alle" den gleichen Abstand zu Ihr haben (quasi eine Art Brennpunkt, der Vorteil, es reichen auch schon zwei Punkte um den Brennpunkt zu entwickeln), approximiere den Mittelpunkt der 4 (oder 3, 2) durch eine Taylorentwicklung mit zwei Veränderlichen. Der approximierte Punkt der Taylorentwicklung und der Brennpunkt ergeben zusammen den gesuchten Normalenvektor... ich hoffe Du konntest es Dir vorstellen... bei zwei Funktionswerten hast Du ein Dreieck als Brennmethode, bei drei eine 4 seitige Pyramide (die Grundfläche ist die Ebene durch die vier Punkte) und bei 4 schließlich eine fünfseitige Pyramide... die Berechnung der Längen und des Richtungsvektors auf den Brennpunkt würde zu einem Gleichsystem führen, daß den Pythagoras Satz benutzt... das Gleichungssystem hättest Du dann pro Komponente...

Gute Jagd Winn

daishi Mitglied 12:12:47 11.12.2003 Titel:

Hi,
danke für die Antwort.
Ist zwar ne nette Idee, hat aber das Problem, daß ich eine falsch Normale errechne, wenn ich die Punkte nicht gleichmäßig um den zuberechnenden Punkt lege.

Ich werde die ganze Sache mal auf Ganzzahlberechnugn umstellen müssen, dann kann ich zumindest die Rundungsfehler vergessen, was mir schon sehr hilft.

Trotzdem Danke für die Antwort.

Winn Mitglied 14:17:05 11.12.2003 Titel:

Kleinen Fehler hab ich schon gemacht, der entwickelte Punkt aus der Taylorentwicklung, brauchst Du nicht mal, er würde tatsächlich für eine falsche Normale sorgen, wenn er nicht auch entsprechend zum Brennpunkt gekippt wird... wenn Du aber den Gewichtspunkt der entstehenden Ebene mit dem Brennpunkt verbindest, erhälst Du Deinen Normalenvektor... sicherlich hast Du dann nicht eine Normalen "am Punkt" aber mindestens in der Mitte zweier Punkte... von der Geschwindigkeit her würde es außerordentlich flott sein, denn die Gewichtungpunkt zweier Punkte, kann als Mittelung verstanden werden... der Brennpunkt wäre auch schnell ermittelt, denn der höchste y-Wert gäbe die maximale Länge an... die Gerade vom kleineren Y-Wert müßte nur noch mittels Pythagoras "angepaßt" werden... Schnittpunkt berechnen, Differenz von Schnittpunkt zum "gemittelten" Punkt berechnen, vielleicht noch normieren, fertig... das Verfahren würde ähnlich auch noch mit drei Punkten gehen, aber mit vieren wie ich angab, geht's tatsächlich nicht...

Übrigens verwette ich nen Euro, wenn die Ganzzahlberechnung nicht auch zu Instabilitäten führt...

Öhm, fällt mir gerade noch ein, selbst die Normale am Punkt wäre dann kein Problem mehr, denn wenn Du z.B. die Normalen aus der X-Richtung komponentenweise aufsplittest und die darausentstehenden Winkel extrahierst, jene noch aus der Y-Richtung aufaddierst und anschließend auf einen Normalenvektor zur XY-Ebene anwendest, hast Du den Normalenvektor "im" Punkt

Gute Jagd Winn

daishi Mitglied 14:49:00 11.12.2003 Titel:

Hmmmmm, so könnte es wirklich was werden.

Ich melde mich wenn ich's probiert habe.

DANKE

Winn schrieb:

..., wenn die Ganzzahlberechnung nicht auch zu Instabilitäten führt...

Klar, mit der Ganzzahlberechnung bekomme ich die Instabilitäten nicht weg, aber einige andere nette Effekte der Gleitkommazahlen treten nicht mehr auf.

Hier mal ein Kleines Beispiel:
in C++ mit double bekommt man fogende Ergebnisse
161.2-161.0=0.19999999999999
36.8-36.2=0.59999999999999

Bei der Ganzzahlberechnung kann ich zumindest diese Probleme Ausschließen.

Winn Mitglied 11:55:50 12.12.2003 Titel:

Moin daishi,

vielleicht bekommste das mit "ceil" und "floor" aus der math.h hin, die choppen float, double und long double derart, daß stets der größte oder kleinste Wert über bleibt... denn bedenke, die Rechner sind in der Regel schwache Integerarithmetiker, da biste mit Float schneller... bin gespannt ob's im Gesamten funktioniert, halt mich auf dem Laufenden

Gruß Winn