[SOLVED] Schnittpunkt von zwei Kreisen

Thracian

Hallo,
für ein Programm muss ich den Schnittpunkt von zwei Kreisen berechnen. Gegeben sind jeweils die Koordinaten vom Mittelpunkt sowie der Radius.
Gibt es eine Möglichkeit, den Schnittpunkt zu berechnen.
Meine Gedanken bisher:
Ich kann auf jeden Fall den Abstand zwischen den Punkten berechnen (Wurzel aus (X2 - X1)² + (Y2-Y1)²). Außerdem weiss ich, dass beide Schnittpunkte auf einer Senkrechten dieser Strecke liegen. Ich habe mir überlegt, dass man jetzt eventuell mit Vektoren und dem Skalarprodukt arbeiten könnten.
Ein anderer Weg wäre, den Schnittpunkt der Senkrechten mit der Strecke P1P2 zu suchen und dann per Satz von Vieta die Kreisschnittpunkte herauszufinden.
Wie dem auch sei, irgendwo da hänge ich jetzt fest und ich bin mir auch nicht sicher, ob ich mich verrannt habe.
Kann mir da jemand helfen?
Beste Grüße,
Thracian

Mario Sandler

Gibt bei google en Haufen Treffer:
http://www.uni-protokolle.de/foren/viewt/25549,0.html
<-- Täusch ich mich oder versucht da jemand XSA auf der Seite?

Thracian

Danke für die Antwort, ich hatte bei Google irgendwie nichts gefunden. Ich hab aber irgendwie den Eindruck, dass der dortige Lösungsvorschlag nicht ganz richtig ist (kann mich aber auch verrechnet haben).

Uniprotokolle.de schrieb:

s = √((xn-xm)²+(yn-ym)²)
p = (s²+R1²-R2²)/(2*s)
h = ±√(R1²-p²)
Wenn (R1²-p²) < 0 dann kein Schnittpunkt.
Wenn (R1²-p²) = 0 dann berühren sich die kreise nur.
Wenn (R1²-p²) > 0 dann berühren gibt es zwei Schnittpunkte

o = (xn-xm)/s a = (yn-ym)/s

x1 = xm + o*p + a*h
y1 = ym + a*p - o*h

Für x2,y3 h = -h benutzen.

Wenn ich als Punkte P1(2|2) und P2(3|3) wähle und als Radien jeweils 1 nehme kommen als Schnittpunkt S1(3|3) und S2(2|3) heraus. Das kann doch gar nicht stimmen.

Hallo, vielleicht hilft dir das:

//-----------------------------------------------------------------------------/
// Berechnen der Schnittpunkte zweier Kreise (2 dimensional, die z-Koordinate  /
// wird nicht berücksichtigt)                                                  /
//-----------------------------------------------------------------------------/

int SchnittKreisKreis (CVector mp1, double r1, CVector mp2, double r2,
                       CVector* sp1, CVector* sp2)
    {
    double d, a, h

    d = AbstandPunktPunkt (mp1, mp2);

    if (d > r1 + r2)    // Keine Schnittpunkte
       {
       // wscript.echo "Keine Schnittpunkte, Abstand zu groß"
       return (-1);
       }
    else if (fabs(d) < 0.0001)
       {
       // wscript.echo "Kreise haben gleichen Mittelpunkt"
       return (-2);
       }

    dx = mp2.x - mp1.x;
    dy = mp2.y - mp1.y;

    a = (r1 * r1 - r2 * r2 + d * d) / (2 * d);

    h = sqrt (r1 * r1 - a * a);

    sp1.x = mp1.x + (a/d) * dx - (h/d) * dy;   // Schnittpunkt 1
    sp1.y = mp1.y + (a/d) * dy + (h/d) * dx; 
    sp1.z = mp1.z;                             // Z-koordinate übernehmen

    sp2.x = mp1.x + (a/d) * dx + (h/d) * dy;   // Schnittpinkt 2
    sp2.y = mp1.y + (a/d) * dy - (h/d) * dx; 
    sp2.z = mp1.z;

    return(0);
    }

Gruß,

Andreas

Thracian

Hallo,
vielen Dank für deine Antwort.
Ich hab jetzt mal beide Lösungen "kombiniert", aber im Prinzip nutzen ja beide den selben Lösungsweg.
Hier unten ist der Konstruktor beschrieben, es geht dabei um Bäume, aber hat nichts zu bedeuten.

#include <cmath>
Baum::Baum(float X1, float Y1, float X2, float Y2, float r1, float r2, bool Ausrichtung)
{
float s, p, h;
s = sqrtf((powf((X2-X1),2))+(powf((Y2-Y1),2))); //Abstand der Mittelpunkte

if(s>(r1+r2))
{
    //Kreise schneiden sich nicht
}
if(X1==X2 && Y1==Y2)
{
    //gleicher Kreismittelpunkt
}
else // Tatsächlich existieren Schnittpunkte
{

p = (powf(r1,2)-powf(r2,2)+powf(s,2))/(2*s);
if (Ausrichtung == 0)
{
    h = sqrtf(powf(r1,2)-powf(p,2));
}
else
{
    h = -1 * sqrtf(powf(r1,2)-powf(p,2));
}

Xpos = X1 + ((X2-X1)/s) * p + ((Y2-Y1)/s) * h;
Ypos = Y1 + ((Y2-Y1)/s) * p + ((X2-X1)/s) * h;;
}
}

Kompiliert man jetzt aber das vollständige Programm, so gibt er bei:
X1 = 1
Y1 = 1
X2 = 2
Y2 = 2
r1,r2 = 1
als Schnittpunkte (jeweils mit anderer Ausrichtung) S1(1|2) was stimmt und S2(2|2) was nicht stimmen kann.
Wer es selbst ausprobieren möchte, hier ist das kompilierte Programm bei rapidshare (nur wer sich die Mühe machen möchte :D):
http://rapidshare.com/files/79809033/SChnittpunkt.exe
Beste Grüße und vielen Dank,
Thracian

Hallo,

wahrscheinlich hast du einen Fehler eingebaút

Mein Programm rechnet korrekt:

S1 (1|2)
S2 (2|1)

Gruß,

Andreas

Thracian

Hm, mit welchen Datentypen hast du gearbeitet? Vielleicht hat er bei mir die floats einfach falsch gerundet?

Hallo,

Datentypen sieht man doch, alles double.

Übernimm doch einfach den Code.
Der ist doch in 2 Minuten angepasst.

Außerdem r1 * r1 ist schneller und besser als powf(...)

Gruß,

Andreas

Thracian

Hallo,
erstmal vielen Dank für deine Hilfe. Da ich diesen Programmteil gerne in eine größere Facharbeit integrieren würde (Thema: Kartographierung von Waldgrundstücken) kennzeichne ich diesen Abschnitt natürlich als "nicht mein eigener" und verweise auf diesen Thread. Geht das in Ordnung oder hättest du gerne eine andere Kennzeichnung?

Zum eigentlich Fehler:
Dieser war denkbar einfach. Beide Quelltexte sind richtig und vom Prinzip her auch gleich. Ich hatte lediglich bei der Ausgabe eine Kleinigkeit übersehen (Zweimal den ersten Y-Wert des Schnittpunktes ausgeben). Insofern war es klar, dass man im eigentlich Quelltext keinen Fehler finden konnte.

Naja, vielen Dank für die Hilfe
Gruß,
Thracian

Hallo Thracian,

ich denke, dass du das nicht extra kennzeichnen musst.

Sind nur geometrische Betrachtungen und wenn du in der Schule

Phytagoras gelernt hast, dann gibst du auch keine Quelle an

Benenne einfach deinen Variablen etwas anders.

Wenn du für deine Arbeit noch eine Skizze benötigst, bitte Email angeben
da diese Zeichnung auch nicht von mir ist und ich sie deshalb hier nicht
einstellen möchte.

Gruß,

Andreas

Thracian

Hallo,
vielen Dank, eine Skizze wäre klasse.
Email erhalten, echt klasse //Edit
Besten Dank