Kollision Rechteck/Kreis?

Hi,

ich habe eine struktur für meine Objekte:

class CBase
{
	int x, y, w, h, r; // x,y,width,height,radius
}

doch wie kann ich ein Rechteck (x,y,w,h) mit einem Kreis kollidieren lassen? (x,y,r)

Ich finde in meinem Mathebuch nichts über sowas...

WebFritzi

Hö? Wen (x,y) beim Rechteck der Punkt oben links und beim Kreis der Mittelpunkt ist, dann sind sie doch schon kollidiert. Ich weiß nicht genau, was du nun eigentlich willst.

ups sorry, bei Kreis kommt auf X und Y noch der Radius abgezogen, sogesehen ist dann der Kreis in einem Quader.

Abbadon

iSAK schrieb:

ups sorry, bei Kreis kommt auf X und Y noch der Radius abgezogen, sogesehen ist dann der Kreis in einem Quader.

versteh ich nicht, aber es ist ja auch schon recht spät...

Abbadon

Willst du wissen ob sich Kreis und Rechteck überlappen? Das kann man ganz einfach ausrechnen.

WebFritzi

OK, ich gehe mal davon aus: Du hast ein Rechteck R = (x_ul, y_ul, x_lr, y_lr) und einen Kreis K = (a, b, R). Dabei ist (x_ul,y_ul) der Eckpunkt links oben vom Rechteck und (x_lr,y_lr) der Eckpunkt rechts unten; (a,b) ist der Mittelpunkt des Kreises und R sein Radius. Und jetzt willst du wissen, ob R und K kollidieren. Ist das so richtig?
Wenn ja, dann kannst du das so machen: Du bildest das Schnittrechteck R' von R und dem Quadrat, welches den Kreis umschließt. Gibt es keins, so gibt es auch keine Kollision. Gibt es eins, so machen wir eine Fallunterscheidung:

1. R' hat keine oder 2 Ecken mit R gemeinsam
2. R' hat alle Ecken mit R gemeinsam (R' == R)
3. R' hat genau eine Ecke mit R gemeinsam

Wenn du dir das ganze mal aufmalst, wirst du folgendes erkennen:

1.Fall: Es liegt eine Kollision vor.
2.Fall: Liegt nur eine der 4 Ecken im Kreis, so liegt eine Kollision vor.
3.Fall: Liegt diese Ecke im Kreis, so liegt eine Kollision vor.

@Abbadon: Ich finde das nicht so einfach. Ich habe jedenfalls lange gegrübelt...

WebFritzi

Hier mal meine programmatischen Überlegungen:

Erstmal Definitionen:

struct RECTANGLE
{
   unsigned int x_ul;  // upper left
   unsigned int y_ul;
   unsigned int x_lr;  // lower right
   unsigned int y_lr;
};

struct CIRCLE
{
   unsigned int x_m;
   unsigned int y_m;
   unsigned int R;
};

Es sei mal rc das Rechteck und rc_i das Schnittrechteck (i für Intersection). Ich habe mir überlegt, wieviele korrespondierende Werte der beiden Rechtecke gleich sind, wenn n Ecken der Rechtecke gleich sind. Korrespondierende Werte sind z.B. rc.x_lr und rc_i.x_lr. Also die entsprechenden x- und y-Werte der Rechtecke. Dabei kommt heraus:

Keine Ecke gleich: genau ein x-Wert gleich,
                   genau ein y-Wert gleich,
                   genau 2 x-Werte gleich,
                   genau 2 y-Werte gleich,
                   alle Werte verschieden
Genau eine Ecke gleich: genau ein x-Wert und ein y-Wert gleich
Genau zwei Ecken gleich: 3 Werte gleich
Genau drei Ecken gleich: Gibt's nicht!
Genau vier Ecken gleich: Alle Werte gleich.

Wir müssen also nur die Fälle "genau ein x-Wert und ein y-Wert gleich" und "Alle Werte gleich" näher untersuchen. Im ersten Fall ist's klar: da testen wir einfach, ob die entsprechende Ecke im Kreis ist. Im zweiten könnten wir natürlich alle vier Ecken testen, aber es geht auch einfacher. Dazu mehr im Code und danach.
Wir lassen also bei der Definition des Schnittrechtecks 2 Counter mitlaufen. Dazu definieren wir noch:

unsigned char MAX_RCC(unsigned int* rectValue, unsigned int circleValue, unsigned int* xy_saved)
{
   if(*rectValue < circleValue)
   {
      *rectValue = circleValue;
      return 0;
   }
   else
   {
      *xy_saved = *rectValue;
      return 1;
   }
}

unsigned char MIN_RCC(unsigned int* rectValue, unsigned int circleValue, unsigned int* xy_saved)
{
   if(*rectValue > circleValue)
   {
      *rectValue = circleValue;
      return 0;
   }
   else
   {
      *xy_saved = *rectValue;
      return 1;
   }
}

Wenn der Rect-Wert geändert werden muss, geben wir 0 zurück sonst 1 (eine neue gleiche Koordinate). Im letzten Fall speichern wir noch den Rect-Wert. Jetzt die Funktion:

bool Rect_Circle_Collision(RECTANGLE rc, CIRCLE* c)
{
   unsigned char x_counter = 0, y_counter = 0;
   unsigned int x_corner, y_corner;

   // Die Koordinaten des Schnittrechtecks werden in die
   // Koordinaten von rc geschrieben, und währenddessen
   // wird gezählt
   if(rc.x_ul <= c->x_m + c->R)
      x_counter += MAX_RCC(&rc.x_ul, c->x_m - c->R, &x_corner);
   else
      return false;

   if(rc.y_ul <= c->y_m + c->R)
      y_counter += MAX_RCC(&rc.y_ul, c->y_m - c->R, &y_corner);
   else
      return false;

   if(rc.x_lr >= c->x_m - c->R)
      x_counter += MIN_RCC(&rc.x_lr, c->x_m + c->R, &x_corner);
   else
      return false;

   if(rc.y_lr >= c->y_m - c->R)
      y_counter += MIN_RCC(&rc.y_lr, c->y_m + c->R, &y_corner);
   else
      return false;

   // Auswertung der Counter

   // Genau eine Ecke gleich
   if(x_counter == 1  &&  y_counter == 1)
      return IsPointInCircle(x_corner, y_corner, c);

   // Alle vier Ecken gleich
   if(x_counter == 2  &&  y_counter == 2)
      return( MIN(square(rc.x_ul-c->x_m), square(rc.x_lr-c->x_m)) +
              MIN(square(rc.y_ul-c->y_m), square(rc.y_lr-c->y_m))
              <= square(c->R) );

   // Sonst: Kollision
   return true;
}

Hierfür müssen noch die Funktionen MIN(), square() und IsPointInCircle() definiert werden:

int MIN(int x, int y)
{
   return (x < y) ? x : y;
}

int square(int x)
{
   return x * x;
}

bool IsPointInCircle(unsigned int x, unsigned int y, CIRCLE* ptC)
{
   return( square(x - ptC->x_m) + square(y - ptC->y_m) <= square(ptC->R) );
}

So, hoffe mal, es haben sich keine Fehler eingeschlichen.

Edit: Fehler raus!

WebFritzi

UND ES LÄUFT!!! Hiermit kann man unter Windows testen:

HDC hdc = GetDC(hwnd);

   CIRCLE c;
   c.x_m = 100;
   c.y_m = 100;
   c.R   = 50;

   RECTANGLE rc;
   rc.x_ul = 0;
   rc.y_ul = 0;
   rc.x_lr = 60;
   rc.y_lr = 80;

   Ellipse(hdc, c.x_m - c.R, c.y_m - c.R, c.x_m + c.R, c.y_m + c.R);
   Rectangle(hdc, rc.x_ul, rc.y_ul, rc.x_lr, rc.y_lr);

   ReleaseDC(hwnd, hdc);

   if( Rect_Circle_Collision(rc, &c) )
      MessageBoxA(hwnd, "COLLISION", "Notify", MB_OK|MB_ICONINFORMATION);
   else
      MessageBoxA(hwnd, "NO COLLISION", "Notify", MB_OK|MB_ICONINFORMATION);

Man braucht natürlich ein Fenster-Handle hwnd.

Abbadon

WebFritzi schrieb:

@Abbadon: Ich finde das nicht so einfach. Ich habe jedenfalls lange gegrübelt...

Wenn man Lust hat zu grübeln, dann kann man das ja machen. Aber auch ohne zu grübeln kommt man ans Ziel:
1. Teil die Ebene in 9 Teile auf, die Grenzen sind die Geraden die durch die Seiten des Rechtecks gehen.
2. Wenn der Mittelpunkt des Kreises im Rechteck liegt ist alles klar. Ansonsten vergleiche den Abstand vom Mittelpunkt des Kreises zur jeweiligen Seite des Rechtecks bzw. zum jeweiligen Eckpunkt des Rechtecks, jenachdem in welchem Teil der Ebene der Mittelpunkt liegt.

Wenn man es eleganter haben will, dann muss man eben grübeln.

WebFritzi

Das Problem an deiner Lösung ist, dass sie keine ist. Du benutzt Ausdrücke wie "jeweiligen Seite des Rechtecks" oder "jeweiligen Eckpunkt des Rechtecks". Was soll das sein? Wie soll das jetzt jemand programmieren? Oder sagen wir's mal so: Programmiere mir das mal! Los. Wenn's so einfach geht... bitte.

Abbadon

Mit "jeweiligen Seite des Rechtecks" meine ich natürlich die Seite die an den jeweiligen Teil der Ebene angrenzt, genauso bei den Eckpunkten.

WebFritzi

Erstens ist deine Formulierung "Ebene" sehr irreführend. Ich würde mal sagen: "Segment" oder so... Naja, und jedes der 9 Segmente ist aber durch 3 Geraden bestimmt. Welche davon nehme ich denn nun?

Abbadon

du stellst dich aber wirklich dämlich an...

WebFritzi

*LOL* Wenn du meinst... Du hast meine Frage aber leider noch nicht beantwortet. Oder gibst du dich geschlagen?

Abbadon

WebFritzi schrieb:

Erstens ist deine Formulierung "Ebene" sehr irreführend. Ich würde mal sagen: "Segment" oder so...

Ich weiss nicht was an Ebene irreführend sein soll, das ist ein gängiger Begriff.

WebFritzi schrieb:

Naja, und jedes der 9 Segmente...

Wo kommen denn aufeinmal 9 Segmente her? Ich dachte du meinst mit Segment die Ebene???

WebFritzi schrieb:

...ist aber durch 3 Geraden bestimmt. Welche davon nehme ich denn nun?

Nehmen?? Wozu?

WebFritzi

OK, mit Ebene meinst wohl den ganzen $\mathbf{R}^2$ . Verlängern wir nun jede Strecke des Rechtecks zu einer Geraden, so entstehen 9 "Teile", die die Ebene teilen. Nennen wir diese Teile "Segmente", OK?

Mit "jeweiligen Seite des Rechtecks" meine ich natürlich die Seite die an den jeweiligen Teil der Ebene angrenzt, genauso bei den Eckpunkten.

Was ist der "jeweilige Teil der Ebene"? Wir betreiben hier Mathematik, mein Junge. Da muss alles ganz genau definiert sein.

Abbadon

WebFritzi schrieb:

Was ist der "jeweilige Teil der Ebene"? Wir betreiben hier Mathematik, mein Junge. Da muss alles ganz genau definiert sein.

In meinem etwas misslungenem Satz steht:

Abbadon schrieb:

...,jenachdem in welchem Teil der Ebene der Mittelpunkt liegt

Damit sollte eigentlich klar sein was mit dem "jeweiligen Teil der Ebene" gemeint ist. Oder etwa nicht?

WebFritzi

OK. Ich glaube, ich habe dich endlich verstanden. Ich zeichne mal auf:

|             |
      A     |     B       |        C
            |             |
-------------------------------------------------
      D     |/////////////|        E
            |/////////////|
-------------------------------------------------
            |             |
      F     |     G       |        H
            |             |

Ich habe die Teile mal mit Buchstaben benannt. Liegt der Mittelpunkt des Kreises nun in A, C, F oder H, dann ist klar, dass die jeweilige Ecke zu überprüfen ist, ob sie im Kreis liegt. Liegt der Mittelpunkt in B, D, G oder E, dann muss man prüfen, ob die jeweilige Seite des Rechtecks durch den Kreis verläuft. Wie macht man das? Einfach die Seite als Gerade auffassen und deren Abstand zum Mittelpunkt berechnen (analytische Geometrie). Ist dieser Abstand kleiner als der Radius, gibt es eine Kollision - sonst nicht.
Ich finde aber trotzdem meine Lösung besser, denn es gibt nur 4 Fallunterschiede (OK, insgesamt 6). Außerdem scheint mir der Rechenaufwand etwas geringer.

@Abbadon: Versuch doch das nächste mal, einfach das, was du meinst, verständlich rüberzubringen.