Sourcecodes - Kreise schneiden

Sprachenübersicht/C / C++/ C#/Mathematik

Kreise schneiden

Diese Seite wurde 11847 mal aufgerufen.

Dieser Artikel wurde in einem Wikiweb System geschrieben, das heißt, Sie können die Artikel jederzeit editieren, wenn Sie einen Fehler gefunden haben, oder etwas hinzufügen wollen.

Editieren Versionen Linkpartnerschaft Bottom Printversion

Keywords: Kreise schneiden, C++, allgemein Kreise schneiden

Dieser Artikel soll zeigen, wie man zwei Kreis allgemein schneidet.

Am Schluss entwickeln wir einen Algorithmus in C++, der zwei Kreise schneidet.

Wenn wir uns zwei Kreise aufzeichnen, kommen wir per Vektorenrechnung auf die Formeln:

Code:


1: (x-x1)^2 + (y-y1)^2 = r1^2
2: (x-x2)^2 + (y-y2)^2 = r2^2



Wobei x und y Koordinaten des Schnittpunktes, und x1/x2, y1/y2 Koordinaten der Kreismittelpunkte sind. r1/r2 sind die Radien.

Wir müssen die beiden Gleichungen nach x und y auflösen. Dazu beginnen wir mit dem Subtraktionsverfahren, wir subtrahieren beide Gleichungen:

x(2*x2- 2*x1) + (x1^2 - x2^2) + y(2*y2 - 2*y1) +(y1^2 -y2^2) = r1^2 - r2^2

x = y (y1-y2)/(x2-x1) + ((r1^2-r2^2) + (x1^2-x2^2) -(y1^2-y2^2))/(2*x2 - 2*x1)

a = (y1-y2)/(x2-x1)
b = ((r1^2-r2^2) + (x1^2-x2^2) -(y1^2-y2^2))/(2*x2 - 2*x1)

Jetzt formen wir die Gleichung 1 nach x um:

x = +- sqrt(r1^2 - (y-y1)^2) +x1

Wir setzen beide Gleichungen gleich:

y*a + (b-x1) = +- sqrt(r1^2 - (y-y1)^2)

Wir quadrieren die Gleichung:

y^2 *a^2 + y(2*a(b-x1)) +(b-x1)^2 = r1^2 - y^2 + 2*y*y1 - y1^2

y^2 (a^2 + 1) + y (2*a(b-x1) - 2*y1) + ((b-x1)^2 - r1^2 + y1^2) = 0

e = (a^2 + 1)
f = (2*a(b-x1) - 2*y1)
g = ((b-x1)^2 - r1^2 + y1^2)

So, wir lösen die quadratische Gleichung

y1,2 = (-f +- sqrt(f^2 - 4*e*g) )/(2*e)

Jetzt müssen wir nur noch in die Gleichung x = y * a + b zwei mal einsetzen, und schon haben wir unsere beiden Punkte.

Jetzt implementieren wir das ganze in C++:

Code:


#include <iostream>
#include <math.h>

struct Point
{
     double x;
     double y;
};

struct Result
{
     struct Point P1;
     struct Point P2;
};

void GetCollisionPoint(struct Point P1, struct Point P2, double r1, double r2, struct Result *res)
{
     double a = (P1.y - P2.y)/(P2.x - P1.x);
     double b = ( (r1*r1 - r2*r2)- (P1.x*P1.x - P2.x*P2.x) - (P1.y*P1.y - P2.y*P2.y)  )/(2*P2.x - P1.x);

     double e = a*a+1;
     double f = (2*a*(b-P1.x))-(2*P1.y);
     double g = (b-P1.x)*(b-P1.x) -r1*r1 + P1.y*P1.y;

     res->P1.y = (-f + sqrt(f*f - 4*e*g) )/2*e;
     res->P2.y = (-f - sqrt(f*f - 4*e*g) )/2*e;

     res->P1.x = res->P1.y * a + b;
     res->P2.x = res->P2.y * a + b;
}

int main(int args, char* argv[])
{

     struct Point A;
     A.x = -11;
     A.y = 1;

     struct Point B;
     B.x = -1;
     B.y = 1;

     struct Result test;

     GetCollisionPoint(A,B, 1, 1, &test);

     std::cout << "Position (x,y,z): P(" << test.P1.x << "/" << test.P2.x << "," << test.P1.y << "/" << test.P2.y << ")" << std::endl;

     return 0;
}



Code:


debian:/devices/server/projects/SAY# make && ./test
g++ -O2 -Wall main.c -o ./test -L /usr/local/lib 
Position (x,y,z): P(-0/-0,1/1)

Gibt es noch irgendwelche Fragen, oder wollen Sie über den Artikel diskutieren?

Editieren Versionen Linkpartnerschaft Top Printversion

Haben Sie einen Fehler gefunden? Dann klicken Sie doch auf Editieren, und beheben den Fehler, keine Angst, Sie können nichts zerstören, der Artikel kann wiederhergestellt werden.

Sprachenübersicht/C / C++/ C#/Mathematik/Kreise schneiden