rotation und verschiebung von koordinaten ermitteln

[Schandmaul]

hi...

ich habe ein programm, mit dem ich vektoren aus einer datei anzeige...
meine "quelle" sieht in etwa so aus:
vek1: p1 = x10 y10 -> p2 = x12 y12
vek2: p1 = x20 y20 -> p2 = x18 y21
usw...

mein drehpunkt liegt zB bei x150 y200...

ich drehe um den mittelpunkt, wodurch die "p1" unverändert bleiben und die "p2" ihre positionen eben um den winkel und dann die verschiebung ändern...
das klappt auch schon ganz gut

jetzt möchte ich aber für jeden vektor die drehung und x/y verschiebung berechnen um diese dann zu minimieren...

da sich meine mathekenntnisse in der vektorrechnung doch sehr in grenzen halten komm ich bei der winkelberechnung irgendwie nich weiter...

nach meiner suche im netz gehe ich mal davon aus, dass ich dazu das skalarprodukt und/oder "irgendwas anderes" brauche...?

meine 1. frage wäre nun: was/wie muß ich rechnen damit ich die drehung berechnen kann um den besten drehwinkel zu finden?

und die 2.: wie muß das dann im c++ code aussehen, damit es funktioniert?

ich hoffe mal das war einigermaßen verständlich...
und ich fände es gut, wenn hier jemand nicht nur die "lösung" schreibt, sondern das auch so erklären kann dass ich auch verstehe was und warum ich "dies und das" mache...

MfG
Schandmaul

[Entenwickler]

Hast du keine Shift-Taste?
Klemmt deine Punkt-Taste?

[Maxi]

also... wenn ich das richtig sehe, so sind deine Vektoren in der Datei alle um 150/200 gedreht und alle um den selben Vektor v verschoben?
Und du willst jetzt alpha (den dreh-winkel) und den Verschiebungsvektor berechnen?

Dann zB so. Is jetzt nur schnell hingeschrieben, musst dann mal nachrechnen.

geg:
V1, V1' V2, V2'
ges: a (alpha), Vt (verschiebungsvektor)

zu allererst:
Verschiebe alle deine Eingangsvektoren um -(150/200), damit der Ursprung bei 0/0 liegt.

x1 ist x-Komponenete von V1 usw.

x1 * cos a - y1 * sin a + xt = x1' // Drehung und Verschiebung von x von V1
x1 * sin a + y1 * cos a + yt = y1' // Drehung und Verschiebung von y von V1

x2 * cos a - y2 * sin a + xt = x2' // Drehung und Verschiebung von x von V2
x2 * sin a + y2 * cos a + yt = y2' // Drehung und Verschiebung von y von V2

Du hast jetzt 4 Gleichungen und 3 Variablen, das müsste doch zu lösen sein. Eigentlich reichen 3 Gleichungen.

Bei dieser Lösung gehe ich davon aus, dass die Punkte genau berechnet wurden und keine Fehler durch Rauschen / Runden usw. enthalten sind.

[Schandmaul]

ich glaube ich hab mich doch etwas unverständlich ausgedrückt

an sich ist das schon richtig, aber
mein problem ist nicht wie ich die dreheung einrechne, sondern wie ich aus den vorhandenen koordinaten die schon vorhandene drehung ausrechnen kann..

wenn zb die p2 um 5° gedreht sind, wie bekomme ich raus, dass sie um 5° gedreht sind?

[proggingmania]

p1 ist vor der Drehung und p2 nach der Drehung ?

Dann rechne erst den Winkel für p1 aus, dann den Winkel für p2.
Die Differenz ist dann der Drehwinkel.

Gruß,
p.

[Werner Salomon]

Schandmaul schrieb:

meine "quelle" sieht in etwa so aus:
vek1: p1 = x10 y10 -> p2 = x12 y12
vek2: p1 = x20 y20 -> p2 = x18 y21
usw...

Das erscheint mir mehrdeutig.
1.) Ist vekt1 ein Vektor, der in einem System den Wert (10,10) und im zweiten den Wert (12, 12) hat.
2.) Ist vekt1 ein Vektor der von (10,10) nach (12,12) zeigt.

Wie meinst Du das?

Schandmaul schrieb:

mein drehpunkt liegt zB bei x150 y200...

Die Punkte "p1" (10,10) und (20,20) lassen sich nicht durch Drehung und Verschiebung nach "p2" (12,12) und (18,21) verschieben, da der Abstand der "p1" ein anderer ist, als der zwischen den "p2" untereinander.
Mir ist nicht klar, wie Du das mit der Drehung meinst.

Schandmaul schrieb:

ich drehe um den mittelpunkt, wodurch die "p1" unverändert bleiben und die "p2" ihre positionen eben um den winkel und dann die verschiebung ändern...
das klappt auch schon ganz gut

Gib uns doch mal ein nachvollziehbares Zahlenbeispiel, dann versteht man vielleicht die Frage

Schandmaul schrieb:

jetzt möchte ich aber für jeden vektor die drehung und x/y verschiebung berechnen um diese dann zu minimieren...

Was genau willst Du minimieren? Wenn Du eine Menge "p1" von 2 oder mehr Punkten in der Ebene hast und diese durch Drehung und Verschiebung in eine zweite Menge "p2" von Punkten überführst, so gibt es für diese Drehung und Verschiebung im allgemeinen nur genau eine Lösung.

Schandmaul schrieb:

ich hoffe mal das war einigermaßen verständlich...

leider gar nicht

Schandmaul schrieb:

und ich fände es gut, wenn hier jemand nicht nur die "lösung" schreibt, sondern das auch so erklären kann dass ich auch verstehe was und warum ich "dies und das" mache...

Helfen kann ich oder jemand anderes Dir sicher, sobald wir die Frage verstanden haben. Versuch' bitte mal auf meine Fragen (s.o.) bzw. Bemerkungen zu antworten.

Gruß
Werner

[Schandmaul]

danke schonmal für eure mühe,
aber irgendwie hab ich sowas fast befürchtet..
erklären war noch nie meine stärke..
ich versuches nochmal...

Werner Salomon schrieb:

Das erscheint mir mehrdeutig.
1.) Ist vekt1 ein Vektor, der in einem System den Wert (10,10) und im zweiten den Wert (12, 12) hat.
2.) Ist vekt1 ein Vektor der von (10,10) nach (12,12) zeigt.

mein vektor zeigt von (10,10) nach (12,12)

Werner Salomon schrieb:

Die Punkte "p1" (10,10) und (20,20) lassen sich nicht durch Drehung und Verschiebung nach "p2" (12,12) und (18,21) verschieben, da der Abstand der "p1" ein anderer ist, als der zwischen den "p2" untereinander.
Mir ist nicht klar, wie Du das mit der Drehung meinst.

ich habe im prinzip 2 ebenen, eine mit den p1, eine mit den p2 und rotiere die ebene mit den p2...

ich berechne die drehung so wie bereits von Maxi geschrieben, nur dass ich nicht beide ebenen drehe, sondern nur die mit den p2.

wenn ich mit dieser formel mit alpha um meinen mittelpunkt drehe, dann ändern sich die p2, also mein vektor zeigt danach von p1(10,10) zu p2'(13,15)

Werner Salomon schrieb:

Was genau willst Du minimieren? Wenn Du eine Menge "p1" von 2 oder mehr Punkten in der Ebene hast und diese durch Drehung und Verschiebung in eine zweite Menge "p2" von Punkten überführst, so gibt es für diese Drehung und Verschiebung im allgemeinen nur genau eine Lösung.

ich möchte die länge der vektoren so klein wie möglich haben...
nach der drehung / verschiebung sollen meine p2' im idealfall gleich wie die p1 sein...

zb vorher:
v1.p1 (10,10) v1.p2 (12,13) 
v2.p1 (300,300) v2.p2 (302,303) 
drehung =0; verschiebung x=-2 y=-3

x2 * cos 0 - y2 * sin 0 + -2 = x2' // Drehung und Verschiebung von x
x2 * sin 0 + y2 * cos 0 + -3 = y2' // Drehung und Verschiebung von y

danach:
v1.p1 (10,10) v1.p2' (10,10)
v2.p1 (300,300) v2.p2' (300,300)

habe ich jetzt aber etwas wie :

v1.p1(10,10) v1.p2(12,12)
v2.p1(300,300) v2.p2(298,298)

dann müßte ich ebene 2 um alpha rotieren, wie/mit welcher formel erhalte ich alpha?

MfG

[Werner Salomon]

Schandmaul schrieb:

habe ich jetzt aber etwas wie :

v1.p1(10,10) v1.p2(12,12)
v2.p1(300,300) v2.p2(298,298)

dann müßte ich ebene 2 um alpha rotieren, wie/mit welcher formel erhalte ich alpha?

Na ja - ich hab's oben schon geschrieben. In diesem Fall bekommst Du p2 nicht auf p1 abgebildet, da die Entfernung der beiden Punkte (12,12) zu (298,298) kleiner ist als die Entfernung von (10,10) und (300,300).

Schandmaul schrieb:

ich möchte die länge der vektoren so klein wie möglich haben...
nach der drehung / verschiebung sollen meine p2' im idealfall gleich wie die p1 sein...

Es sind natürlich mehrere Vektoren - also auch mehrere Längen. Im Normalfall strebt man in diesen Fällen ein Minimum der Summe aller Quadrate der Längen an.

Das ganze ist also eine Extremwertaufgabe. Dein obiges Beispiel ist aber bereits ein Optimum in diesem Sinne.

Du schreibst einmal Drehung und einmal Drehung und Verschiebung, ich gehe mal davon aus, Du meinst immer letzteres. Das heißt es soll nicht nur der Winkel, sondern auch die Verschiebung bestimmt werden - oder?

Wichtige Frage: wie viele Punkte hast Du. Sind es immer nur zwei - wie in Deinem Beispiel?

Gruß
Werner

[Schandmaul]

Werner Salomon schrieb:

Na ja - ich hab's oben schon geschrieben. In diesem Fall bekommst Du p2 nicht auf p1 abgebildet, da die Entfernung der beiden Punkte (12,12) zu (298,298) kleiner ist als die Entfernung von (10,10) und (300,300).

"brauche" ich die entfernung der punkte (12,12) zu (298,298) überhaupt?
ich drehe die gesamte ebene mit allen p2,
die entfernung der punkte (p2) untereinander ändert sich nicht, sondern nur die von den p1 zu p2...
also meine vektoren werden dann länger oder kürzer...

Werner Salomon schrieb:

Es sind natürlich mehrere Vektoren - also auch mehrere Längen. Im Normalfall strebt man in diesen Fällen ein Minimum der Summe aller Quadrate der Längen an.

Das ganze ist also eine Extremwertaufgabe. Dein obiges Beispiel ist aber bereits ein Optimum in diesem Sinne.

da bin ich mir nicht ganz sicher, aber ich würde jetzt mal sagen ja das könnte stimmen...
und genau da verstehe ich das ganze nicht mehr...

ja das bsp wäre das optimale, wenn ich nur eine verschiebng hätte,
aber es kann eine verschiebung, eine rotation oder beides sein...

Werner Salomon schrieb:

Du schreibst einmal Drehung und einmal Drehung und Verschiebung, ich gehe mal davon aus, Du meinst immer letzteres. Das heißt es soll nicht nur der Winkel, sondern auch die Verschiebung bestimmt werden - oder?

Wichtige Frage: wie viele Punkte hast Du. Sind es immer nur zwei - wie in Deinem Beispiel?

Gruß
Werner

ja ich meine immer beides, nur meine frage bezieht sich auf den winkel, wenn die rotation "weg" ist die verschiebung rauszubekommen ist ja einfach

die anzahl der punkte variiert zw 2 und 599, wollte eigentlich mit den 2 punkten das nur verständlicher machen...

ich versuchs nochmal anders...

angenommen ich hätte 2 bilder mit verschidenen punkten...
bild 1 ist das "soll" bild und bild 2 das "ist" bild...
bild (ebene) 2 ist nun im verhältnis zu bild 1 um den mittelpunkt gedreht und/oder auch verschoben...

jetzt möchte ich bild 2 durch rotation und/oder verschiebung bestmöglich an bild 1 "annähern", im idealfall dann die punkte bild 2 = bild 1 (alle vektoren hätten dann länge 0)...

wenn also bild 2 zu bild 1 um 5° gedreht und ohne verschiebung ist...
dann muß man bild 2 um -5° drehen um die beiden bilder "übereinander" zu legen...

wie kann ich aus meinen punkten diese 5° drehung der beiden ebenen zueinander berechnen?

Gruß
Schandmaul

[proggingmania]

Also, das erste mal hab ich dich ja völlig missverstanden und jetzt bin ich mir auch nicht sicher, ob ich richtig liege.
Aaaaber, wenn beide Vektoren den gleichen Winkel zu einer Bezugsachse, z.B. zur X-Achse haben, dann sind beide Vektoren schon einmal parallel, gelle ?
Und durch Verschiebung um entsprechende X- und Y- Einheiten können dann beide Vektoren zumindest den selben Ursprungspunkt erhalten, ne ?

Und dieselbe Länge kann man dann bekommen, wenn man aus den Vektoren Einheisvektoren berechnet, wenn ich mich noch richtig erinnere.

LG,
p.

[Werner Salomon]

Hallo Schandmaul,

Mir ist jetzt klar, was Du für eine Anforderung hast. Die Lösung dafür ist mir bekannt inklusiv der mathematischen Herleitung und fertigen C++-Code, ... aber leider z.Zt noch Firmengeheimnis. Das heißt: ich darf sie nicht ausplaudern

Nur soviel: die Herleitung ist nicht trivial - obwohl sie im Prinzip mit Abitur-Wissen zu machen ist - und ich habe sie auch nirgendwo im Internet gefunden.

Das einzige was mir noch dazu einfällt ist die Empfehlung der Mathematik-newsgroup de.sci.mathematik. Wenn es Dir da jemand erzählen sollte, so habe ich es Dir nicht verraten .

Noch mal 'ne Frage zum Schluss: wozu benötigst Du das?

Gruß
Werner

[Schandmaul]

dass die herleitung nicht trivial ist hab ich auch gemerkt...
obwohl ich nicht gedacht hätte, dass das sooo geheim sein könnte...

auf http://www.mathe-online.at/mathint/vect2/i.html steht was von "Winkel zwischen zwei Vektoren"
bin mir nur nicht sicher ob das das ist was ich brauche, und verstehen tue ich das im mom (noch) gar nicht...
das besagte abitur-wissen zum herleiten fehlt mir nämlich...

naja, ich werds mal bei den Mathematikern versuchen

Gruß
Schandmaul

[Werner Salomon]

Verrätst Du mir bitte noch wozu Du das Verfahren benötigst ..

Gruß
Werner

[Schandmaul]

kann ich machen ^^

ich habe die aufgabe eine messung auszuwerten,
dabei sind meine p1 die vom pc berechneten soll-positionen und die p2 die gemessenen ist-positionen...
die abweichung von "soll" zu "ist" stelle ich über linien (vektoren p1 zu p2) dar...

zur auswertung habe ich nur die koordinaten aus meiner datei,
den drehpunkt berechne ich aus soll-koordinaten...

jetzt soll ich aber anhand dieser koordinaten die "korrekturwerte" (rotation, veschiebung, skalierung) berechnen...

also verschiebung und skalierung ist einfach,
nur bei der rotation komm ich grade nicht weiter...

irgendwann kommt evtl. auch noch scherung mit dazu, aber darüber hab ich mir noch keine gedanken weiter gemacht, da ich mit der rotation erstmal genug probleme hab...

Gruß
Schandi

[proggingmania]

Huhu,
also wie jetzt ?
Du hast einen Vektor V in der Ebene mit seinen Koordinaten p1, p2.
Der Vektor V wird jetzt gedreht und eventuell noch verschoben.
Nach Drehung und Verschiebung hat er die Koordinaten p1', p2'.
Richtig ?

Jetzt möchtest Du den Drehwinkel rausbekommen, oder ?
Rechne doch erst beide Winkel separat aus und bilde dann die Differenz,
dann hast du den Drehwinkel.

Wenn du Lust hast, kannst du auch konkrete Beispiele, also Vektoren mit Koordinaten vorher und nachher aufschreiben, dann können wir das in Quellcode umsetzen.

LG,
p.

[Schandmaul]

proggingmania schrieb:

Huhu,
also wie jetzt ?
Du hast einen Vektor V in der Ebene mit seinen Koordinaten p1, p2.
Der Vektor V wird jetzt gedreht und eventuell noch verschoben.
Nach Drehung und Verschiebung hat er die Koordinaten p1', p2'.
Richtig ?

Jetzt möchtest Du den Drehwinkel rausbekommen, oder ?
Rechne doch erst beide Winkel separat aus und bilde dann die Differenz,
dann hast du den Drehwinkel.

Wenn du Lust hast, kannst du auch konkrete Beispiele, also Vektoren mit Koordinaten vorher und nachher aufschreiben, dann können wir das in Quellcode umsetzen.

hi,
nee nich ganz ^^
mein vektor geht von p1 zu p2,
der vekror an sich wird nicht gedreht/verschoben,
sondern die "ebene" mit allen p2,
mein vektor geht nach der drehung von p1 (bleibt unverändert) nach p2' (neu )...
der vektor hat danach eine andere länge/richtung...
verstehst du jetzt was ich meine?

mfg

[proggingmania]

Ok, korrigiere mich bitte, wenn ich falsch liege:

Du hast eine Menge ( 2 bis 599 ) von 2D-Vektoren in der Ebene und genau einen Drehpunkt
D(x;y)

Wir betrachten jetzt nur einen Vektor V1 mit Anfangspunkt p1 und Endpunkt p2.

Wir denken uns den Drehpunkt D mit dem Anfangspunkt p1 des Vektors V1 verbunden
und erhalten eine Strecke, bzw einen neuen Vektor V2: Dp1

Wir denken uns den Drehpunkt D mit dem Endpunkt p2 des Vektors V1 verbunden
und erhalten eine Strecke, bzw einen neuen Vektor V3: Dp2.

Der Endpunkt p2 wird nun um D gedreht, je nach Drehrichtung wird V1 größer oder kleiner,
d.h. sein Betrag ändert sich.

Vektor V1 ist genau dann minimal, wenn er mit Dp2 kollinear ist und in die selbe Richtung zeigt,
p2 wird zu p2'.

V1 hat dan den minimalen Betrag |Dp2| - |Dp1|, den kann man auch ohne Rotation direkt ausrechnen.
Der heiß begehrte Rotationswinkel, nennen wir ihn mal Phi, bei dem V1 minimal ist,
ist nun der Winkel zwischen Dp1 und Dp2.
Den Winkel könnte man jetzt z.B. mit Hilfe des Kosinussatzes ausrechnen, dafür
braucht man lediglich die drei Punkte im Raum: D(x;y), p1(x1;y1), p2( x2;y2).

Nach Anwendung des Kosinussatzes und Umformung ergibt sich für den Winkel Phi:

$$

Phi =
\arccos
\left(
\frac
{(x-x1)^2+(y-y1)2+(x-x2)^2+(y-y2)2-(x2-x1)^2-(y2-y1)2}
{2\cdot((x-x1)^2+(y-y1)2)\cdot((x-x2)^2+(y-y2)2)}
)\right

$$

Gruß,
p.

[Schandmaul]

danke für deine hilfe, aber ich glaube ich bin ein hoffnungsloser fall...
auch wenn es vllt ganz einfach ist, ich schaffs nich

hab das jetzt versucht mit dieser formel zu berechnen, aber irgendwo ist da ein fehler den ich nicht finde...

double x = 300;
	double y = 500;
	double x1= 0;
	double y1= 0;
	double x2= 0;
	double y2= 0;
	double Phi = 0;
	double s1 =0;
	double s2 =0;

	for(int i=0; i<iAnzahl; i++)
	{
		x1= v[i].p1.x1;
		y1= v[i].p1.y1;
		x2= v[i].p2.x2;
		y2= v[i].p2.y2;

		s1 = (pow((x-x1),2) + pow((y-y1),2) + pow((x-x2),2) + pow((y-y2),2) - pow((x2-x1),2) - pow((y2-y1),2));
		s2 = (2 * (pow((x-x1),2) + pow((y-y1),2)) * (pow((x-x2),2) + pow((y-y2),2)));
		Phi += acos(s1/s2);

	}
Phi /= iAnzahl;

ich bekomme immer einen "Phi" von 1,57xxxx , selbst wenn ich folgendes mache:

x=0;
	y=0;
	x1=500;
	y1=800;
	x2=500;
	y2=800;

	s1 = (pow((x-x1),2) + pow((y-y1),2) + pow((x-x2),2) + pow((y-y2),2) - pow((x2-x1),2) - pow((y2-y1),2));
	s2 = (2 * (pow((x-x1),2) + pow((y-y1),2)) * (pow((x-x2),2) + pow((y-y2),2)));
	Phi = acos(s1/s2);

wenn p1 = p2 ist sollte Phi doch 0 sein und nicht 1,5x

was mache ich falsch ?

gruß
Schandi

[Werner Salomon]

proggingmania schrieb:

Nach Anwendung des Kosinussatzes und Umformung ergibt sich für den Winkel Phi:

$$

Phi =
\arccos
\left(
\frac
{(x-x1)^2+(y-y1)2+(x-x2)^2+(y-y2)2-(x2-x1)^2-(y2-y1)2}
{2\cdot((x-x1)^2+(y-y1)2)\cdot((x-x2)^2+(y-y2)2)}
)\right

$$

Du hast die Wurzel vergessen. Korrekt wäre hier

$$

\phi =
\arccos
\left(
\frac
{(x-x1)^2+(y-y1)2+(x-x2)^2+(y-y2)2-(x2-x1)^2-(y2-y1)2}
{2\cdot \sqrt{(x-x1)^2+(y-y1)2} \cdot \sqrt{(x-x2)^2+(y-y2)2} }
\right)

$$

Schandmaul schrieb:

wenn p1 = p2 ist sollte Phi doch 0 sein und nicht 1,5x

was mache ich falsch ?

(s.o.) berücksichtige die Wurzel und Du erhälst

double x=0;
    double y=0;
    double x1=500;
    double y1=800;
    double x2=500;
    double y2=800;

    double s1 = (pow((x-x1),2) + pow((y-y1),2) + pow((x-x2),2) + pow((y-y2),2) - pow((x2-x1),2) - pow((y2-y1),2));
    double s2 = (2 * sqrt(pow((x-x1),2) + pow((y-y1),2)) * sqrt(pow((x-x2),2) + pow((y-y2),2)));
    double Phi = acos(s1/s2);

Phi wird zu 0.

Abgesehen davon bekommt man auf diese Art und Weise für Phi nur positive Werte, da der cos für positive und negative Winkel mit gleiche Betrag gleiche Werte liefert.

Besser ist es, den sin und cos dieses Winkels zu bestimmen und dann die Funktion atan2 zu nutzen. Das Skalarprodukt ist
$\vec{a} \cdot \vec{b}=\left| \vec{a} \right| \cdot \left| \vec{b} \right| \cdot \cos{\phi}$

und das Kreuzprodukt ist
$\vec{a} \times \vec{b}=\left| \vec{a} \right| \cdot \left| \vec{b} \right| \cdot \sin{\phi}$

damit kann man phi bestimmen aus
$\phi = atan2 \left( \vec{Dp1} \times \vec{Dp2} , \vec{Dp1} \cdot \vec{Dp2} \right)$

Am besten man bastelt sich eine Vektor-Klasse oder nimmt diese hier - abgespeckt auf 2 Dimensionen.

Apropos; Frage an Schandi - ist der Drehpunkt überhaupt bekannt?

Gruß
Werner

[proggingmania]

Werner Salomon schrieb:

Du hast die Wurzel vergessen. Korrekt wäre hier

Aaaahhhggrrrfrxt ich Dusselvieh ! So ein Anfängerfehler, Schande über mein Haupt !

Werner Salomon schrieb:

Abgesehen davon bekommt man auf diese Art und Weise für Phi nur positive Werte, da der cos für positive und negative Winkel mit gleiche Betrag gleiche Werte liefert.

Ok, sehen wir mal davon ab und sagen: Jepp ! Man bekommt den Winkel, aber die Drehrichtung geht flöten( verloren ).
Ob p1 == p2 ist, würd ich abfragen bevor ich die beiden Punkte an die Formel lasse.

Werner Salomon schrieb:

damit kann man phi bestimmen aus

Die letzten beiden Formeln können meine Browser nicht darstellen, daher kann ich da keinen Senf zu beitragen.

An Schandschnute hätt ich auch ne Frage und zwar um was für Messpunkte es sich dabei handelt.

Gruuuhuuß,
p.