Kollision Rechteck/Kreis?
-
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!
-
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.
-
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.
-
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.
-
Mit "jeweiligen Seite des Rechtecks" meine ich natürlich die Seite die an den jeweiligen Teil der Ebene angrenzt, genauso bei den Eckpunkten.
-
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?
-
du stellst dich aber wirklich dämlich an...
-
*LOL* Wenn du meinst... Du hast meine Frage aber leider noch nicht beantwortet. Oder gibst du dich geschlagen?
-
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?
-
OK, mit Ebene meinst wohl den ganzen . 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.
-
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?
-
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.