4. Simple Kreis/Rechteck kollisionsüberprüfung!

Simple Kreis/Rechteck kollisionsüberprüfung!

  • C

    ja, da hab ich wohl geschlampt :p - geht so wohl doch besser:

    inline int sqr(const int x){ return x*x; }
inline bool intersectsCircleLineX(const circle &c, const int x, const int y1,const int y2)
{
	register int r2;
	return (r2=sqr(c.r)-sqr(c.x-x))>=0&&((r2-sqr(c.y-y1))*(r2-sqr(c.y-y2))<=0||((c.y-y1)*(c.y-y2)<=0&&r2-sqr(c.y-y1)<=0));
}
inline bool intersectsCircleLineY(const circle &c, const int x1, const int x2,const int y)
{
	register int r2;
	return (r2=sqr(c.r)-sqr(c.y-y))>=0&&((r2-sqr(c.x-x1))*(r2-sqr(c.x-x2))<=0||((c.x-x1)*(c.x-x2)<=0&&r2-sqr(c.x-x1)<=0));
}
bool intersectsCircleRect(const rect &r, const circle &c)
{
	return intersectsCircleLineX(c,r.x,r.y,r.y+r.height)||
		intersectsCircleLineX(c,r.x+r.width,r.y,r.y+r.height)||
		intersectsCircleLineY(c,r.x,r.x+r.width,r.y)||
		intersectsCircleLineY(c,r.x,r.x+r.width,r.y+r.height);
}
    0
  • ?

    Wieder geschlampt? Mit den selben Koordianten gehts noch immer nicht und obwohl sich kreis und Rect schneiden sagt er "no collision"

    0
  • C

    dann liegt der fehler diesmal nicht bei mir...

    0
  • O

    doch, könnte sogar sein, dass der fehler bei dir liegt, die sache mit dem schneidend er linie mit dem kreis sieht mir sehr abenteuerlich aus

    @threadersteller ich muss das ganze heute abend mal machen, ma schaun ob ichs heute noch poste...

    0
  • C

    also wenn ich diese funktion mit eben diesen beispieldaten füttere liefert sie mir hier true zurück, so wie es sein soll

    die idee des schnitttests ist eigentlich simpel; erst wird geprüft, ob die geraden, die das rechteck definieren, dem kreis überhaupt nah genug kommen; wenn das der fall ist, gibt es zwei möglichkeiten für den schnitt, endweder liegt ein endpunkt im kreis und einer ausserhalb oder beide liegen ausserhalb (ich teste nur einen punkt, denn falls der andere punkt innen liegt, kommen wir gar nicht soweit) aber auf verschiedenen seiten der gerade y=circle_.y bzw. x=circle_.x

    0
  • ?

    hi,

    hier das testprogramm:

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

inline  int abs (int value)
{
    return ((value < 0) ? -value : value); 
}

struct RECTANGLE 
{ 
   unsigned int x;  // upper left 
   unsigned int y; 
   unsigned int width;  // lower right 
   unsigned int height; 
}; 

struct CIRCLE 
{ 
   unsigned int x; 
   unsigned int y; 
   unsigned int r; 
};
inline int sqr(const int x){ return x*x; } 
inline bool intersectsCircleLineX(const CIRCLE &c, const int x, const int y1,const int y2) 
{ 
    register int r2; 
    return (r2=sqr(c.r)-sqr(c.x-x))>=0&&((r2-sqr(c.y-y1))*(r2-sqr(c.y-y2))<=0||((c.y-y1)*(c.y-y2)<=0&&r2-sqr(c.y-y1)<=0)); 
} 
inline bool intersectsCircleLineY(const CIRCLE &c, const int x1, const int x2,const int y) 
{ 
    register int r2; 
    return (r2=sqr(c.r)-sqr(c.y-y))>=0&&((r2-sqr(c.x-x1))*(r2-sqr(c.x-x2))<=0||((c.x-x1)*(c.x-x2)<=0&&r2-sqr(c.x-x1)<=0)); 
} 
bool intersectsCircleRect(const RECTANGLE &r, const CIRCLE &c) 
{ 
    return intersectsCircleLineX(c,r.x,r.y,r.y+r.height)|| 
        intersectsCircleLineX(c,r.x+r.width,r.y,r.y+r.height)|| 
        intersectsCircleLineY(c,r.x,r.x+r.width,r.y)|| 
        intersectsCircleLineY(c,r.x,r.x+r.width,r.y+r.height); 
}

#define WIN32_LEAN_AND_MEAN

#include <windows.h>
#include "resource.h"

const char name[] = "SplashScreen";
const unsigned long window_style = WS_SYSMENU | WS_MINIMIZEBOX | WS_OVERLAPPED;

HBITMAP g_hBitmap;

///////////////////////////////////////////////////////////////////////////////
LRESULT CALLBACK WndProc(HWND hWnd, unsigned int message, unsigned int wParam, long lParam)
{
	switch(message)
	{
	case WM_CREATE:
		{
			RECT rc = {0, 0, 640, 480};

			::AdjustWindowRectEx (&rc, window_style, false, 0);

			int centerX = (::GetSystemMetrics(SM_CXFULLSCREEN)/2) - (abs(rc.left)+rc.right )/2;
			int centerY = (::GetSystemMetrics(SM_CYFULLSCREEN)/2) - (abs(rc.top )+rc.bottom)/2; 

			::MoveWindow (hWnd, centerX, centerY, (rc.right - rc.left), (rc.bottom - rc.top), true);

			g_hBitmap = LoadBitmap(GetModuleHandle(NULL), MAKEINTRESOURCE(IDB_BITMAP1));
		} break;

	case WM_PAINT:
		{
			PAINTSTRUCT ps;
			HDC hDC, hBitmapDC;
			HBITMAP hOldBitmap;
			BITMAP bm;

			hDC = BeginPaint(hWnd, &ps);

			//-- Create a DC for the bitmap and select it
			//   into the created DC.
			hBitmapDC = CreateCompatibleDC(hDC);
			hOldBitmap = (HBITMAP)SelectObject(hBitmapDC, (HBITMAP)g_hBitmap);

			//-- Display the bitmap into window
			GetObject((HBITMAP)g_hBitmap, sizeof(BITMAP), &bm);	
			BitBlt(hDC, 0, 0, bm.bmWidth, bm.bmHeight, hBitmapDC, 0, 0, SRCCOPY);

			//-- Delete the temporary bitmap DC
			SelectObject(hBitmapDC, hOldBitmap);
			DeleteDC(hBitmapDC);

			EndPaint(hWnd, &ps);

  HDC hdc = GetDC(hWnd); 

   CIRCLE c; 
   c.x = 100; 
   c.y = 100; 
   c.r   = 50; 

   RECTANGLE rc; 
   rc.x = 145; 
   rc.y = 0; 
   rc.width = 60; 
   rc.height = 150; 

   Ellipse(hdc, c.x - c.r, c.y - c.r, c.x + c.r, c.y + c.r); 
   Rectangle(hdc, rc.x, rc.y, rc.width+rc.x, rc.height+rc.y); 

   ReleaseDC(hWnd, hdc); 

   if( intersectsCircleRect(rc, c) ) 
      MessageBoxA(hWnd, "COLLISION", "Notify", MB_OK|MB_ICONINFORMATION); 
   else 
      MessageBoxA(hWnd, "NO COLLISION", "Notify", MB_OK|MB_ICONINFORMATION);
		} break;

	case WM_DESTROY:
		{
			if(g_hBitmap)
				DeleteObject(g_hBitmap);

			PostQuitMessage(0);
		} break;
	}

	return DefWindowProc(hWnd, message, wParam, lParam);	
}

int WINAPI WinMain(HINSTANCE hInstance, HINSTANCE hPrevInstance, PSTR szCmdLine, int iCmdShow)
{
		// Läuft die Anwendung schon?
	HANDLE isRunning = ::CreateFileMapping(INVALID_HANDLE_VALUE, NULL, PAGE_READONLY, 0, 32, name);

	if (isRunning && ::GetLastError () == ERROR_ALREADY_EXISTS)
	{
		::MessageBox (NULL, "Läuft schon!", "", MB_OK);
		return 0;
	}

	MSG msg;
	HWND hWnd;
	WNDCLASSEX wc;

	wc.cbSize = sizeof(wc);
	wc.style = CS_VREDRAW | CS_HREDRAW;
	wc.lpfnWndProc = WndProc;
	wc.cbClsExtra = 0;
	wc.cbWndExtra = 0;
	wc.hInstance = hInstance;
	wc.hIcon = LoadIcon(NULL, MAKEINTRESOURCE(IDI_APPLICATION));
	wc.hCursor = LoadCursor(NULL, IDC_ARROW);
	wc.hbrBackground = (HBRUSH)GetStockObject(WHITE_BRUSH);
	wc.lpszMenuName = NULL;
	wc.lpszClassName = name;
	wc.hIconSm = LoadIcon(NULL, MAKEINTRESOURCE(IDI_APPLICATION));

	RegisterClassEx(&wc);

	hWnd = CreateWindowEx(NULL,
								 name,
								 name,
								 window_style,
								 0,
								 0,
								 640,
								 480,
								 NULL,
								 NULL,
								 hInstance,
								 NULL);

	ShowWindow(hWnd, iCmdShow);
	UpdateWindow(hWnd);

	while(GetMessage(&msg, NULL, 0, 0))
	{
		TranslateMessage(&msg);
		DispatchMessage(&msg);
	}

	::UnregisterClass (name, hInstance);

	return (int) msg.wParam;
}
    0
  • M

    Vieleicht hilft dir das HIER weiter

    0
  • ?

    Eigentlich sollte das nicht all zu schwer sein:

    2 Rechteck stoßen zusammen wenn ihre Projektion auf die X Axe und die Y Axe überlappen:

    A 0AA00
A 0AA00
0 00000
B 000BB
B 000BB

  0AABB

    Nein, keine überlappt

    A 00AA0
A 00AA0
0 00000
B 000BB
B 000BB

  00ACB

    Nein, nur die X Axe

    0 00000
0 00000
A 00AA0
C 00ACB
B 000BB

  00ACB

    Ja, X Axe und Y Axe.

    Dieser Trick funz auch ganz ähnlich mit Kreisen, nur muss du hier die Seiten des Rechtecks einzeln betrachten, und jeweils die "Breite" des Kreises mit gleicher X oder Y Koordinate. Beispiel für:

    00000
00A00
0AAA0
00ABB
000BB

    Erste vertikale Seite:

    |
0 00000
0 00A00
A 0AAA0
B 00ABB
B 000BB

    Zweite vertikale Seite:

    |
0 00000
0 00A00
0 0AAA0
B 00ABB
B 000BB

    Erste horizontale Seite:

    00000
 00A00
 0AAA0
-00ABB
 000BB

 00ABB

    Zweite horizontale Seite:

    00000
 00A00
 0AAA0
 00ABB
-000BB

 000BB

    Und ein Beipiel von es eine Kollision gibt:

    00000
00A00
0AACB
00ABB
00000

    Erste vertikale Seite:

    |
0 00000
0 00ABB
C 0AACB
B 00ABB
0 00000

    Zweite vertikale Seite:

    |
0 00000
B 00ABB
B 0AACB
B 00ABB
0 000B0

    Erste horizontale Seite:

    00000
-00ABB
 0AACB
 00ABB
 00000

 00ABB

    Zweite horizontale Seite:

    00000
 00ABB
 0AACB
-00ABB
 00000

 00ABB

    Einziges Problem: Es werden nur die Ränder des Rechtecks getestet, wenn der Kreis komplet im Rechteck liegt wird diese Methode fehlschlagen. Allerdings kann diesen Fall ja sehr einfach einzeln behandlen, man braucht nur den Kreis viereckig zu machen. Also aus:

    00000
00A00
0AAA0
00A00
00000

    wird

    00000
0AAA0
0AAA0
0AAA0
00000

    und schon musst du nur 2 Rechtecke testen.

    Keine Ahnung ob man das besser hin kriegen könnte.

    0
  • C

    tja... damit gehts...

    inline int sqr(const int x){ return x*x; }
inline bool intersectsCircleLineX(const CIRCLE &c, const int x, const int y1,const int y2)
{
    int r2=sqr(c.r)-sqr(c.x-x);
	int aa=r2-sqr(c.y-y1);
	int bb=r2-sqr(c.y-y2);
	int cc=(c.y-y1);
	int dd=(c.y-y2);
	return (r2>=0)&&((aa*bb<=0)||((cc*dd<=0)&&(aa<=0)));
//    return ((r2=sqr(c.r)-sqr(c.x-x))>=0)&&(((r2-sqr(c.y-y1))*(r2-sqr(c.y-y2))<=0)||(((c.y-y1)*(c.y-y2)<=0)&&(r2-sqr(c.y-y1)<=0)));
}
inline bool intersectsCircleLineY(const CIRCLE &c, const int x1, const int x2,const int y)
{
    int r2=sqr(c.r)-sqr(c.y-y);
	int aa=r2-sqr(c.x-x1);
	int bb=r2-sqr(c.x-x2);
	int cc=(c.x-x1);
	int dd=(c.x-x2);
	return (r2>=0)&&((aa*bb<=0)||((cc*dd<=0)&&(aa<=0)));
//    return (r2=sqr(c.r)-sqr(c.y-y))>=0&&((r2-sqr(c.x-x1))*(r2-sqr(c.x-x2))<=0||((c.x-x1)*(c.x-x2)<=0&&r2-sqr(c.x-x1)<=0));
}
bool intersectsCircleRect(const RECTANGLE &r, const CIRCLE &c)
{
    return intersectsCircleLineX(c,r.x,r.y,r.y+r.height)||
        intersectsCircleLineX(c,r.x+r.width,r.y,r.y+r.height)||
        intersectsCircleLineY(c,r.x,r.x+r.width,r.y)||
        intersectsCircleLineY(c,r.x,r.x+r.width,r.y+r.height);
}

    das ist derselbe algorithmus - k.A. wieso es nicht in einer zeile geht... für hinweise bin ich dankbar

    0
  • C

    oh na klar... das alte unsigned/signed problem...

    inline int sqr(const int x){ return x*x; }
inline bool intersectsCircleLineX(const CIRCLE &c, const int x, const int y1,const int y2)
{
    register int r2;
    return ((r2=sqr(c.r)-sqr(c.x-x))>=0)&&(((r2-sqr(c.y-y1))*(r2-sqr(c.y-y2))<=0)||(((int)(c.y-y1)*(int)(c.y-y2)<=0)&&(r2-sqr(c.y-y1)<=0)));
}
inline bool intersectsCircleLineY(const CIRCLE &c, const int x1, const int x2,const int y)
{
    register int r2;
    return ((r2=sqr(c.r)-sqr(c.y-y))>=0)&&(((r2-sqr(c.x-x1))*(r2-sqr(c.x-x2))<=0)||(((int)(c.x-x1)*(int)(c.x-x2)<=0)&&(r2-sqr(c.x-x1)<=0)));
}
bool intersectsCircleRect(const RECTANGLE &r, const CIRCLE &c)
{
    return intersectsCircleLineX(c,r.x,r.y,r.y+r.height)||
        intersectsCircleLineX(c,r.x+r.width,r.y,r.y+r.height)||
        intersectsCircleLineY(c,r.x,r.x+r.width,r.y)||
        intersectsCircleLineY(c,r.x,r.x+r.width,r.y+r.height);
}

    ich hatte es mit den definitionen, die oben angegeben waren getestet - und die waren signed; die windows strukturen benutzen aber unsigned - also hatten wir beide recht 🙂

    0
Anmelden zum Antworten