Ebene in Punktewolke mathematisch einpassen

[Picojetflyer]

Moin!

Ich tüftel momentan daran, mit einen Excel-Sheet den Abstand eines beliebigen Punktes(X,Y,Z) zu einer Fläche auszurechnen.
Die Fläche, und den Vektor aus 3 Punkten zu berechnen und den Abstand dazu ist kein Problem. Mein Ziel ist es aber, das ganze so zu gestalten das ich das auf beliebig viele Punkte für die Fläche ausbauen kann. Ich bin noch zu keinen richtigen Ergebnis gekommen. B.z.w. die Abweichung zur Referenz war zu groß.
Ich glaube es könnte mit einer Best-Fit-Ebene Funktionieren. Nur wie passe ich Mathematisch eine Ebene bestmöglich in eine Punktewolke aus (n) Punkten ein.

Gruß

Matthias

[rossir]

Eine erste Idee (zum Einstieg) in die Berechnung einer Ebene E die am besten zur Punktwolke p(i) passt.
Grundidee: E wird durch ca. die Hesseform bestimmt. Die Hesseform benötigt einen Punkt p0 (hier einfach mal aus E) und einen Normalenvektor v0.
1) Für p0 wird einfach das Zentrum (Mittelwert aller p(i)) Deiner Punktwolke genommen.
2) Auch v0 wird durch eine Mittelwertbildung bestimmt. v0 ist der Mittelwert der Kreuzprodukte v(i)=(a x b) der Vektoren a und b. Mit a=(p(i)-p0) und b=(p(j)-p0). Dabei liegt p(j) möglichst "links" von p(i).

[oberallgeier]

Hi Matthias.

... wie passe ich Mathematisch eine Ebene bestmöglich in eine Punktewolke aus (n) Punkten ein ...

Zum schicken Vorschlag von rossir einen Denkanstoß: ne Geradenanpassung optimiere ich nach der Kleinste-Quadrate-Methode, da denke ich, dass ich die Ebene mit ner Kleinste-Kuben-Methode anpasse. Hab ich selbst noch nie gehört, liegt aber auch ziemlich abseits meiner Tätigkeiten.

[Picojetflyer]

Eine erste Idee (zum Einstieg) in die Berechnung einer Ebene E die am besten zur Punktwolke p(i) passt.
Grundidee: E wird durch ca. die Hesseform bestimmt. Die Hesseform benötigt einen Punkt p0 (hier einfach mal aus E) und einen Normalenvektor v0.
1) Für p0 wird einfach das Zentrum (Mittelwert aller p(i)) Deiner Punktwolke genommen.
2) Auch v0 wird durch eine Mittelwertbildung bestimmt. v0 ist der Mittelwert der Kreuzprodukte v(i)=(a x b) der Vektoren a und b. Mit a=(p(i)-p0) und b=(p(j)-p0). Dabei liegt p(j) möglichst "links" von p(i).

Ja ich ermittele die Ebene mit der Hesseform. Mit einer Mittelwerten hab ich bereits experimentiert. Mein Ergebnis lag schon nahe an der Referenz, nur für eine ernsthafte Anwendung war das Ergebnis doch noch zu ungenau. Aber das Stichwort mit den "Zentrum" greife ich nochmal auf. Ich glaube da könnte mein Bock liegen.

Hi Matthias.
Zum schicken Vorschlag von rossir einen Denkanstoß: ne Geradenanpassung optimiere ich nach der Kleinste-Quadrate-Methode, da denke ich, dass ich die Ebene mit ner Kleinste-Kuben-Methode anpasse. Hab ich selbst noch nie gehört, liegt aber auch ziemlich abseits meiner Tätigkeiten.

Genau daran bin ich auch schon hängen geblieben. Für eine Gerade ist das genau das was ich suche. Nur wie interpretiere ich das auf eine Ebene. Google oder Wikipedia bietet da ganz wilde Formeln. Nur für mich als Nicht-Studierten habe ich da noch keine Lösung drin gefunden.

Das ganze soll später, eine Auswertemöglichkeit für eine messtechnische Ebenheit werden. Ein Werker ermittelt mittels einer Messuhr, Messwerte in Z Richtung an einen Werkstück. Diese trägt er in einer Excel-Tabelle ein, die Ihn dann, direkt die messtechnisch korrekte Ebenheit ausrechnet. Die Koordinaten in X und Y sind in der Tabelle hinterlegt.

[rossir]

Hier mal Pseudocode (JAVA ähnlich) dafür:

// p0 berechnen
Point3 p0 = new Point3(0,0,0);
for (int i = 0; i < point.length; i++) {
 p0.x+=point[i].x;
 p0.y+=point[i].y;
 p0.z+=point[i].z;
}
p0.x/=point.length;
p0.y/=point.length;
p0.z/=point.length;

// Alle Vektoren auf p0 basieren
for (int i = 0; i < point.length; i++) {
 point[i].x-=p0.x;
 point[i].y-=p0.y;
 point[i].z-=p0.z;
}

// Gemitteltes Kreuzprodukt berechnen
Point3 pV = new Point3(0,0,0);
for (int i = 0; i < point.length; i++) {
 pV.x+=point[i].y*point[(i+1)%point.length].z - point[i].z*point[(i+1)%point.length].y;
 pV.y+=point[i].z*point[(i+1)%point.length].x - point[i].x*point[(i+1)%point.length].z;
 pV.z+=point[i].x*point[(i+1)%point.length].y - point[i].y*point[(i+1)%point.length].x;
}
pV.x/=point.length;
pV.y/=point.length;
pV.z/=point.length;

// Alle Vektoren zurück heben
for (int i = 0; i < point.length; i++) {
 point[i].x+=p0.x;
 point[i].y+=p0.y;
 point[i].z+=p0.z;
}
// auch das Kreuzprodukt
pV.x+=p0.x;
pV.y+=p0.y;
pV.z+=p0.z;

//Ausgabe
println("Hesse Punkt   p0="+p0);
println("(Hesse Punkt) pV="+pV);
println("Hesse Vektor   V=("+p0+", "+pV+")"); 

Dies liefert für die Punkte:

( 10,    0,  0),      
(  0,   10,  1),      
(-10,    0,  0),      
(  0,  -10,  1),

das erwartete Ergebnis:

Hesse Punkt   p0=(0.0, 0.0, 0.5)
(Hesse Punkt) pV=(0.0, 0.0, 100.5)
Hesse Vektor   V=((0.0, 0.0, 0.5), (0.0, 0.0, 100.5))

[Picojetflyer]

Hi Rossir!

Vielen vielen Dank für deine ausführliche Darstellung! Ich probiere das mal in Excel VB umzusetzen.

Gruß

Matthias

[mare_crisium]

Matthias,

der Lösungsvorschlag von Rossir ist ein schöner intuitiver Ansatz. Dabei bleibt aber unbeantwortet, in welchem Sinne die Ebene "optimal" eingepasst ist. Auf alle Fälle richtig ist es, den Mittelpunkt der Punktwolke (also den Mittelwert aller Punkt-Vektoren) als Bezugspunkt der Ebene (rossir nennt ihn den Hesse-Punkt) zu verwenden.

Die naheliegende Antwort auf die Frage, was "mathematisch optimal" bedeuten soll, ist: Die Ebene soll so liegen, dass möglichst viele Punkte davon einen möglichst geringen Abstand haben. Als Abstand betrachtet man dabei die Länge der Senkrechten von der Ebene zu dem betreffenden Punkt. Wie man die ausrechnet, wenn man den Normalenvektor (rossir nennt es den Hesse-Vektor) und den Bezugspunkt kennt, weisst Du ja sicher.

Nur liefert die Berechnung einen positiven Abstand, wenn der Punkt über und einen negativen, wenn er darunter liegt. Wenn man diese Formel in einen Algorithmus steckt, der die Ebene liefert, von der alle Punkte den minimalen Abstand haben, dann wird der versuchen, möglichst viele Abstände möglichst negativ zu machen. Denn "möglichst klein" bedeutet in der Mathematik nun einmal "möglichst negativ".

Das wird erst besser, wenn man das Quadrat des Abstandes nimmt; das ist nämlich immer positiv. Wenn man nun die Summe über die Abstandsquadrate aller Punkte bildet, dann bekommt man eine Funktion, die immer positiv ist. Und die Ebene, von der die Punkte den kleinsten möglichen Abstand haben, zeichnet sich durch ein Minimum dieser Funktion aus. Diese Funktion ist zudem stetig und deshalb differenzierbar. Das hat der gute Herr C.F.Gauss schon 1795 herausgefunden.

Um das Minimum zu finden, muss man die Summe der Abstandsquadrate nach dem Bezugspunkt und dem Normalenektor differenzieren und die Ableitungen gleich Null setzen. Dadurch bekommt man einen Satz von lösbaren Gleichungen. Die Formeln, die bei der Lösung herauskommen sind nicht simpel, aber auch nicht schwer zu programmieren.

Ciao,
mare_crisium