Articlename:  Kreise schneiden
Keywords:     Kreise schneiden, C++, allgemein Kreise schneiden
Date:         25.09.2007, 15:04
Views:        3297
Categoryname: Mathematik
----------------------------------------

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

------- End-Code -------


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.

Dabei haben wir noch ein paar Probleme, es gibt Situationen die mit unserer Gleichung
keine Lösung erzeugen.

Jetzt implementieren wir das ganze in C++:


------- Code -------

#include 
#include 

class Point
{
     public:

     Point()
     {
          x = y = 0;
     }

     Point(double x_, double y_)
     {
          x = x_;
          y = y_;
     }

     double x;
     double y;
};

class Result
{
     public:

     Result()
     {
          Points = 0;
     }

     void SetPoints(int p)
     {
          Points = p;
     }

     int GetPoints()
     {
          return Points;
     }

     Point P1;
     Point P2;

     private:

     int Points;
};

double Abs(double x)
{
     if(x < 0)
          x *= -1;
     return x;
}

void GetCollisionPoint(Point P1, Point P2, double r1, double r2, Result *res)
{
     r1 = Abs(r1);
     r2 = Abs(r2);

     res->SetPoints(0);

     //Kein Schnittpunkt
     double abc = sqrt(Abs(P2.x - P1.x)*Abs(P2.x - P1.x) + Abs(P2.y - P1.y)*Abs(P2.y
- P1.y));

     //Kreise innerhalb
     if(abc  Abs(r1 + r2))
          return;

     //Unendlich Schnittpunkte
     if((P1.x - P2.x == 0) && (P1.y - P2.y == 0))
          return;

/* 25.09.2007 
 * Koordinatentausch war fehlerhaft
 * Jens Ziegler
*/   

     //ggf. Koordinaten tauschen, um Division durch Null vermeiden
     if(P2.x == P1.x)
     {
          res->SetPoints(2);

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

          res->P1.x = (-f + sqrt(f*f - 4*e*g) )/(2*e);
          res->P2.x = (-f - sqrt(f*f - 4*e*g) )/(2*e);
          res->P1.y = res->P1.x * a + b;
          res->P2.y = res->P2.x * a + b;
     }
     else
     {
          res->SetPoints(2);

          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 - 2*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;

     }

     if(res->P1.y == res->P2.y && res->P1.x == res->P2.x)
          res->SetPoints(1);


int main(int args, char* argv[])
{
     std::cout > x;
     std::cout > y;
     std::cout > r1;

     Point A(x,y);

     std::cout  x;
     std::cout > y;
     std::cout > r2;

     Point B(x,y);

     std::cout