Schnittpunkt dreier Kugeln berechnen

[dj_cyborg]

Hallo,

ich versuche mich seit geraumer Zeit an der Berechnung des Schnittpunktes dreier Kreise. Ich habe eine sehr gute Dokumentation gefunden. Nur leider ist mir der Rechenweg zu komplex. Hier werden die Ausgangsgleichungen mit der funktion SOLVE gelöst. Diese funktion gibt es meineswissens aber in Bascom nicht.

Gegeben sind die Positionen der Punkte S1, S2, S3 und deren Abstände (Radien) zum Punkt P1. (alle Winkel innerhalb der Dreiecks-Pyramide kann ich auch berechnen)
Gesucht sind die Koordinaten zum Punkt P1.



Ich versuche zu einer Formel zu kommen bei der ich meine Eingangsdaten verwenden kann.
Ich hatte gehofft über dreiecksberechnung innerhalb der unregelmäßigen Dreieckspyramide ans Ziel zu kommen.

Evtl. hat jemand für mich eine Formle/Lösungsweg/Tipp der sich auch in Bascom umsetzen lässt.

vielen Dank

mfG
Mario

[damfino]

Die Funktion Solve ist ganz nett, aber von Mathlab. Es braucht schon einige Einarbeitungszeit um mit Mathlab umgehen zu können, abgesehen vom Preis.
Wenn du mehr mit Mathematik machen willst, kann man Scilab empfehlen. Leicht ist es aber auch nicht.

Zum Problem Schnittpunkt 2er Kreise: man erhält 0-2 Lösungen (berührend, oder 2 Schnittpunkte, oder gar kein Schnittpunkt), daher muss man vorher überprüfen welche Lösung die richtige ist. Dabei insbesondere auf Divison durch Null aufpassen.
Kosinussatz bietet sich dafür an.

Schnittpunkt 3er Kreise: wie oben, nur 3x so viele Lösungsmöglichkeiten.

Da du dich anscheinend auf GPS beziehst (Doku): mit den ganzen Abweichungen ergibt sich ein Bereich in dem die Position liegt.

Einfacherer Ansatz: richtigen Schnittpunkte von Kreis 1 und 2, 2 und 3, 3 und 1 berechnen, und daraus den Mittelwert. Damit umgeht man die Mehrdeutigkeiten.

Am Besten vorher alles in Ruhe durchrechnen, Formeln ausrechnen und vereinfachen wenn geht, und erst dann das Programm schreiben. Die Atmegas sind mathematisch nicht so gut drauf.

LG!

[HaWe]

je nachdem, wie genau die Messergebnisse sind und wie genau die Lösung sein muss, gibt es mehrere Ansätze:
1.) trigonometrisch (schwierig, weil die Messungenauigkeit "im echten Leben" keine eindeutigen Schnittpunkte zulässt wie in der Trigonometrie oder analytischen Geometrie, und (auch) zeitaufwändig wegen der - ohne fpu - langsamen atan-s etc)
2.) brute-force, iterativ: den gesamten Raum in n*m Quadrate zerlegen und iterativ die gesamte Fläche in einer doppelten Schleife abgrasen und dann den Wert nehmen, der am besten passt
3.) stochastische Monte-Carlo-Methode: ca. 100-1000 sehr gute Zufallszahlen erzeugen (z.B. mit Mersenne Twister, notfalls auch mit K+R Linear Congruence Generator) und dann den am besten passendsten Wert nehmen. Die Zufallszahlen in einer Schleife immer wieder zyklisch neu erzeugen und die ältesten Werte und ggf. die schlechtesten langsam "sterben" lassen. Etwa 3-4 Generationen würde ich sie dabei max. leben lassen. Man kann die Zufallszahlen mit ihrem Fehler auch z.B. in einem FIFO stack oder einem Ring speichern und so nach und nach wieder rausdrängen etc.

zum "am besten passend": da würde ich die Summe der Quadrate der Abweichungen vom Radius der Einzel-Kreise nehmen.

Vorteile bei 2+3:
Man kann leichter durch Einschränkung des Ausgangspunktebereichs Ergebnisse ausschließen, die mathematisch korrekt sind aber unplausibel wären (etwa wie "Schnittpunkte jenseits der Wand").

HTH!

[TiGePa]

Ich versuch hier mal nen Ansatz wiederzugeben:
x1,y1,z1 Koordinaten von S1, x2,y2,z2,x3,y3,z3 analog, x,y,z Koordinaten von P1 (die Unbekannten), r1,r2,r3 Abstände von S1,S2,S3 zu P1
Aus den drei Punkten S1-S3 und den Abständen zu P1 ergeben sich drei Kugelgleichungen:
(x-x1)^2 + (y-y1)^2 + (z-z1)^2 = r1^2 (I)
(x-x2)^2 + (y-y2)^2 + (z-z2)^2 = r2^2 (II)
(x-x3)^2 + (y-y3)^2 + (z-z3)^2 = r3^2 (III)
Diese nun ausmultiplizieren und Konstanten auf die rechte Seite bringen liefert:
x^2-2xx1 + y^2-2yy1 + z^2-2zz1 = r1^2 - x1^2 - y1^2 - z1^2 (I)
x^2-2xx2 + y^2-2yy2 + z^2-2zz2 = r2^2 - x2^2 - y2^2 - z2^2 (II)
x^2-2xx3 + y^2-2yy3 + z^2-2zz3 = r3^2 - x3^2 - y3^2 - z3^2 (III)
Subtrahieren der ersten Gleichung von den anderen beiden liefert:
x^2-2xx1 + y^2-2yy1 + z^2-2zz1 = r1^2 - x1^2 - y1^2 - z1^2 (I)
2x(x1-x2) + 2y(y1-y2) + 2z(z1-z2) = r2^2-r1^2 + x1^2 - x2^2 + y1^2 - y2^2 + z1^2 - z2^2 (IV)
2x(x1-x3) + 2y(y1-y3) + 2z(z1-z3) = r3^2-r1^2 + x1^2 - x3^2 + y1^2 - y3^2 + z1^2 - z3^2 (V)
Da mir das jetzt ein wenig zuviel Schreibarbeit wird und ich dir nicht alles abnehmen möchte , so sollte es weiter gehen:
das (x1-x3)-fache von (IV) von dem (x1-x2)-fachem von (V) abziehen -> Ergebnis (VI) hat nun nur noch zwei unbekannte.
Auflösen von (VI) nach y liefert was in der Form y = a*z (VII)
Einsetzen in (IV) und auflösen nach x liefert was von der Form x = b*z (VIII)
(VII) und (VIII) in (I) einsetzen liefert eine quadratische Gleichung mit Unbekannter z. Diese liefert theoretisch zwei Lösungen von der vermutlich schon eine als unmöglich ausgeschlossen werden kann.
Habs nicht nachgerechnet. Könnte aber klappen
Das ganze ist natürlich ne rein analytische Lösung. Wie stabil das ganze später numrisch läuft ist ne andere Geschichte. Die Ausdrücke werden extrem lang wenn man das von Hand alles ausrechnet. Wenn sich P1 nur in einer Ebene bewegt (z bleibt konstant), wird das ganze einfacher, da man dann mit ner Projektion der Punkte S1-S3 auf die Ebene arbeiten könnte und man nur noch zwei Unbekannte hat.

[dj_cyborg]

Hallo,

vielen Dank für eure Antworten.

Brute-force und Zufallszahl könnten im 3D Raum etwas zu lange dauern .

Ich werde mich zu erst an TiGePa´s Ansatz versuchen.

Mal sehen wie weit ich komme.

Vielen Dank erst mal.

mfG
Mario

Zusatzfrage:

Ist die Berechnung nicht Ähnlich der von Deltabots?

[WL]

Hallo,

ich habe so etwas (Schnittpunkt zweier Kreise) mal hier https://www.roboternetz.de/community...sitionsscanner gebraucht:

Sub Schnitt_kreis(xm1 As Single , Ym1 As Single , R1 As Single , Xm2 As Single , Ym2 As Single , R2 As Single , Xs1 As Single , Ys1 As Single , Xs2 As Single , Ys2 As Single , M As Integer)
Dx = Xm2 - Xm1
Dy = Ym2 - Ym1
A2 = Dx * Dx : Temp = Dy * Dy : A2 = A2 + Temp
R12 = R1 * R1
R22 = R2 * R2
H = -4 * A2
If H = 0 Then
   M = 1
   Exit Sub
End If
Hi = R12 - R22 : Hi = Hi - A2
B2 = Hi * Hi : B2 = B2 / H : B2 = B2 + R22
If B2 < 0 Then
   M = 1
   Exit Sub
End If
B = Sqr(b2)
Temp = R12 - B2
Y = Sqr(temp)
A = Sqr(a2)
Xk = Dx / A
Yk = Dy / A
Xh = Xk * Y : Xh = Xh + Xm1
Yh = Yk * Y : Yh = Yh + Ym1
If B2 = 0 Then
   M = 0
   Xs1 = Xh : Ys1 = Yh
   Exit Sub
End If
Xl = Xk * B
Yl = Yk * B
Xs1 = Xh - Yl
Ys1 = Yh + Xl
Xs2 = Xh + Yl
Ys2 = Yh - Xl
M = -1
End Sub

Der Algorithmus ist von hier http://www.antonis.de/faq/progs/_inhalt.htm