C++ pomysł na obliczenie pozycji

Zenek97 · 5 Lipca 2014

Witam, mam następujący problem

Mam układ współrzędnych x,y, znam wierzchołki czworoboku. Na wejściu mam dane pozycji (jakiś punkt x,y) i teraz jak sprawdzić, czy ten punkt należy do czworoboku czy nie? Np.wierzchołki czworoboku x1=23;y1=11; x2=300; y2=25; x3=22; y3=50; x4=60; y4=70;

No i teraz chcę wiedzieć czy punkt x=25;y=35; należy to tej strefy czy nie?

jak to zrobić?

Sopelek997 · 5 Lipca 2014

Co prawda masz czworokąt, ale najlepiej będzie interpretować go jako wielokąt.

http://www.gamasutra.com/view/feature/3429/crashing_into_the_new_year_.php

Algorytm liczący przecięcia osi jest całkiem wydajny, nie wiem czy istnieje lepszy (później opisany z ray castem wydaje się być wolniejszy.)

Podam niżej ładnie opakowany kod w c++, ale postaraj się przeczytać i zrozumieć to co jest pod linkiem. Wstawiam dlatego, że ten pod linkiem jest strasznie chaotyczny. (Lekko przerobiony z moich składów, nie powinno być błędów, ale był zmieniany na szybko)

bool intersection(const Polygon& polygon, const Vec2& point)
{
    auto determineQuadrant = [](const Vec2& point, const Vec2& center) -> int
    {
        if(point.x < center.x)
            return point.y < center.y ? 1 : 4;
        else
            return point.y < center.y ? 2 : 3;
    };
    size_t vertexCount = polygon.size();
    Vec2* currentVertex = &(polygon.vertices[vertexCount - 1]);
    int totalQuadrantCrossDelta = 0;
    for(size_t i = 0; i < vertexCount; ++i)
    {
        const Vec2* nextVertex = &(polygon.vertices[i]);
        //quadrants
        //1 2
        //4 3
        int currentVertexQuadrant = determineQuadrant(*currentVertex, point);
        int nextVertexQuadrant = determineQuadrant(*nextVertex, point);

        int quadrantCrossDelta = nextVertexQuadrant - currentVertexQuadrant;
        switch(quadrantCrossDelta)
        {
            case 2:
            case -2:
                if( (nextVertex->x - ( ( (nextVertex->y - point.y) * (currentVertex->x - nextVertex->x) ) / (currentVertex->y - nextVertex->y) ) ) < point.x) quadrantCrossDelta = -quadrantCrossDelta;
                break;
            case 3:
                quadrantCrossDelta = -1;
                break;
            case -3:
                quadrantCrossDelta = 1;
                break;
        }

        totalQuadrantCrossDelta += quadrantCrossDelta;
        currentVertex = nextVertex;
    }
    return totalQuadrantCrossDelta == 4 || totalQuadrantCrossDelta == -4;
}

Wystarczy go lekko przerobić pod twoją potrzebę.

_LostGalaxy_ · 5 Lipca 2014

Algorytm liczący przecięcia osi jest całkiem wydajny, nie wiem czy istnieje lepszy (później opisany z ray castem wydaje się być wolniejszy.)

A jaka on ma zlozonosc?

Dla dowolnego da sie to zrobic łatwo w O(n), dla wypukłego tak samo łatwo mozna zejść do O(log_2(n)).

http://erich.realtimerendering.com/ptinpoly/

Tutaj opisane różne(prawdopodobnie szybsze) wersje/rodzaje sprawdzania przynależnosci punktu do wielokata.

Sopelek997 · 6 Lipca 2014

Dla dowolnego wielokąta ma on złożoność O(n), gdzie n to liczba wierzchołków.

Przy czym poszczególne kroki są szybkie (ma niską stałą, tak to się mówi?) i jest łatwy w implementacji.

Zenek97 · 6 Lipca 2014

Nie ogarniam tego kodu

W każdym razie wymyśliłem, że jeżeli punkt jest w środku czworoboku, to półproste (góra,dół,lewo,prawo) od wierzchołka muszą przeciąć przedłużone boki czworoboku.

Albo jeszcze prościej chyba będzie tak: odcinki (wierzchołek czworoboku - badany punkt) nie mogą przeciąć żadnego boku.

Sopelek997 · 6 Lipca 2014

A przejrzałeś chociaż link, który podałem? Tam jest wszystko wyjaśnione

A better strategy is to divide the polygon into quadrants centered on the test point, as in Figure 4. Start at the first vertex in the polygon and set a counter to 0. Anytime an edge crosses from one quadrant to the next, add one to the counter if it crosses clockwise around the test point and subtract one if it crosses counter-clockwise. If the edge crosses diagonally across two quadrants, you need to determine which side of the test point it crossed, and then either add or subtract 2. Try it yourself on Figure 4. Start at vertex 1. Add 1 when edge 3-4 crosses from quadrant I to II, and subtract it again with edge 4-5. When you reach the last edge (11-1), you should have 4. When using the routine, if the counter is equal to 4 or –4, the test point is inside the polygon. You can see the code for this routine in Listing 1.

Listing 1. The Quadrant Approach
to the Bounding Box Test
//kod
Figure 4. Dividing the polygon into quadrants.

Zenek97 · 6 Lipca 2014

Nie ogarniam co tam pisze :P

Wymyślając funkcję na wykrywanie przecięć wpadłem na pomysł, żeby wystarczy sprawdzić czy to się przecina kiedy ma się nie przecinać

#include<iostream>
using namespace std;

int n=0;

void oblicz (double Ax,double Ay,double Bx, double By, double Cx, double Cy, double Dx, double Dy)
{
	int x,y;
	x=((Bx-Ax)*(Dx*Cy-Dy*Cx)-(Dx-Cx)*(Bx*Ay-By*Ax))/((By-Ay)*(Dx-Cx)-(Dy-Cy)*(Bx-Ax));
	y=((Dy-Cy)*(Bx*Ay-By*Ax)-(By-Ay)*(Dx*Cy-Dy*Cx))/((Dy-Cy)*(Bx-Ax)-(By-Ay)*(Dx-Cx));
	if  (
		( (((Ax>=x)&&(x>=Bx))||((Ax<=x)&&(x<=Bx))) && (((Cx>=x)&&(x>=Dx))||((Cx<=x)&&(x<=Dx))) )
		&& 
		( (((Ay>=y)&&(y>=By))||((Ay<=y)&&(y<=By))) && (((Cy>=y)&&(y>=Dy))||((Cy<=y)&&(y<=Dy))) )
		)
		{n++; cout<<"wykryto przecięcie!"<<endl;}
	
}

int main()
{
double x1,y1,x2,y2,x3,y3,x4,y4,xp,yp;

	cout<<"wprowadz 4-bok"<<endl;
	cin>>x1>>y1>>x2>>y2>>x3>>y3>>x4>>y4;
	cout<<"wprowadz punkt"<<endl;
	cin>>xp>>yp;
	//////////////////////////////////////

	//odcinek A-P nie może przeciąc B-C i C-D
	oblicz(x1,y1,xp,yp,x2,y2,x3,y3);
	oblicz(x1,y1,xp,yp,x3,y3,x4,y4);

	//odcinek B-P nie może przeciąc A-D i C-D
	oblicz(x2,y2,xp,yp,x1,y1,x4,y4);
	oblicz(x2,y2,xp,yp,x3,y3,x4,y4);

	//odcinek C-P nie może przeciąc A-D i A-B
	oblicz(x3,y3,xp,yp,x1,y1,x4,y4);
	oblicz(x3,y3,xp,yp,x1,y1,x2,y2);


	//odcinek D-P nie może przeciąc B-C i A-B
	oblicz(x4,y4,xp,yp,x2,y2,x3,y3);
	oblicz(x4,y4,xp,yp,x1,y1,x2,y2);

	if (n==0)
		cout<<"punkt lezy w srodku czworoboku"<<endl;
	else 
		cout<<"punkt lezy na zewnatrz"<<endl;

	cin>>x1;
}

_LostGalaxy_ · 6 Lipca 2014

Albo jeszcze prościej chyba będzie tak: odcinki (wierzchołek czworoboku - badany punkt) nie mogą przeciąć żadnego boku.

Dla wklęsłego mogą przeciąć i punkt może leżeć wewnątrz.

Sopelek997 · 6 Lipca 2014

To albo robisz po swojemu, albo próbujesz nas posłuchać i robisz dobrze.

Dostałeś nawet kod. I nie potrafisz nawet z tego zrobić pożytku.

Zenek97 · 8 Lipca 2014

Nie rozważałem 4boku wklęsłego, bo u mnie taka sytuacja nie może mieć miejsca

Długo się zastanawiałem i doszedłem do wniosku, że metoda jest dobra.

Tylko coś mój program nie do końca dobrze działa. Nie mogę zrozumieć dlaczego

wpisałem przykładowe dane i np w 3 przypadku jest błąd

help

#include<iostream>
using namespace std;

bool obliczpozycje (float Ax,float Ay,float Bx, float By, float Cx, float Cy, float Dx, float Dy)
{
	float x,y;
	x=((Bx-Ax)*(Dx*Cy-Dy*Cx)-(Dx-Cx)*(Bx*Ay-By*Ax))/((By-Ay)*(Dx-Cx)-(Dy-Cy)*(Bx-Ax));
	y=((Dy-Cy)*(Bx*Ay-By*Ax)-(By-Ay)*(Dx*Cy-Dy*Cx))/((Dy-Cy)*(Bx-Ax)-(By-Ay)*(Dx-Cx));
	//cout<<"x="<<x<<"  y="<<y<<endl;
	//cout<<"Ax="<<Ax<<" x="<<x<<" Bx="<<Bx<<"   ";//test

	if  (
		// (	(((Ax<=x)&&(x<=Bx))||((Bx<=x)&&(x<=Ax))) && (((Cx<=x)&&(x<=Dx))||((Dx<=x)&&(x<=Cx)))	) 
		// &&
		// (	(((Ay<=y)&&(y<=By))||((By<=y)&&(y<=Ay))) && (((Cy<=y)&&(y<=Dy))||((Dy<=y)&&(y<=Cy)))	) 
			(((Cx<=x)&&(x<=Dx))||((Dx<=x)&&(x<=Cx)))	
		 &&
			(((Cy<=y)&&(y<=Dy))||((Dy<=y)&&(y<=Cy)))	 



		)
		{cout<<"przeciecie"<<endl;	return false;} //przecięcie w zakresie
		else {cout<<"brak"<<endl;	return true;}  //przecięcie po za zakresem 
}

bool sprwadzpozycje (float x1, float y1, float x2, float y2, float x3, float y3, float x4, float y4, float xp, float yp)
{

	if (
	//odcinek A-P nie może przeciąc B-C i C-D
	(obliczpozycje(x1,y1,xp,yp,x2,y2,x3,y3))&&
	(obliczpozycje(x1,y1,xp,yp,x3,y3,x4,y4))&&
	//odcinek B-P nie może przeciąc A-D i C-D
	(obliczpozycje(x2,y2,xp,yp,x1,y1,x4,y4))&&
	(obliczpozycje(x2,y2,xp,yp,x3,y3,x4,y4))&&
	//odcinek C-P nie może przeciąc A-D i A-B
	(obliczpozycje(x3,y3,xp,yp,x1,y1,x4,y4))&&
	(obliczpozycje(x3,y3,xp,yp,x1,y1,x2,y2))&&
	//odcinek D-P nie może przeciąc B-C i A-B
	(obliczpozycje(x4,y4,xp,yp,x2,y2,x3,y3))&&
	(obliczpozycje(x4,y4,xp,yp,x1,y1,x2,y2))
	)
	return true;
	else  return false;
}

int main()
{
//double x1,y1,x2,y2,x3,y3,x4,y4,xp,yp;
//double Ax,Ay,Bx,By,Cx,Cy,Dx,Dy;
int n=0;

	cout<<"wprowadz 4-bok"<<endl;
	//cin>>x1>>y1>>x2>>y2>>x3>>y3>>x4>>y4;
	cout<<"wprowadz punkt"<<endl;
	//cin>>xp>>yp;
	//////////////////////////////////////
	//if (sprwadzpozycje (x1,y1,x2,y2,x3,y3,x4,y4,xp,yp))
	if (sprwadzpozycje (-293,16,-282,26,-276,113,-298,117,278.6,66.3))//powinien być na zewnatrz
		cout<<"punkt leży wewnatrz"<<endl;
	else 
		cout<<"punkt leży na zewnatrz"<<endl;
	cout<<"////////////////////"<<endl;
		if (sprwadzpozycje (-293,16,-282,26,-276,113,-298,117,16.1,-499.1))//powinien być na zewnatrz
		cout<<"punkt leży wewnatrz"<<endl;
	else 
		cout<<"punkt leży na zewnatrz"<<endl;

		cout<<"////////////////////"<<endl;
		if (sprwadzpozycje (286,82,275,88,300,183,316,200,298.2,149.8))//powinien być wewnatrz
		cout<<"punkt leży wewnatrz"<<endl;
	else 
		cout<<"punkt leży na zewnatrz"<<endl;

	cin>>n;
}

_LostGalaxy_ · 8 Lipca 2014

Nie wiem czy komus bedzie sie chcialo to sprawdzac.

Odpal debugera i sprawdzaj po kolei czy dobrze liczy.

Ale prosciej byloby na mniejszych wspolrzednych punktow to testowac.

Sopelek997 · 8 Lipca 2014

Dlatego, że nadal nie rozumiesz co robisz.

co to ma sprawdzać?

(obliczpozycje(x1,y1,xp,yp,x2,y2,x3,y3))

http://screenshooter.net/2148672/jhqkvps

sprawdzasz czy linie zielona i fioletowa się przecinają.

A potem robisz to dla 7 innych przypadków, i wszystkie muszą się przecinać, żeby punkt był w wielokącie.

Totalnie błędne założenia.

Wróć do linków, które podaliśmy, przeczytaj, zrozum, zobacz kod w tym temacie, zrozum, użyj.

Bo kurde znowu wymyślasz jakieś bzdety totalnie nas ignorując.

Poza tym formatuj kod i dawaj dobre nazwy funkcjom i zmiennym, bo tego się czytać nie da.

btw.

@_LostGalaxy

ciekawy link, dzięki

Zenek97 · 9 Lipca 2014

Dlaczego błędne? (co prawda, metoda nie zadziała na wklęsłe, ale u mnie takich nie ma)

Dokładnie robię tak jak narysowałeś! Jeżeli te wszystkie - 8 przypadków się nie przetną, to świadczy o tym że punkt jest w środku.

Natomiast wystarczy że któraś się przetnie, czyli punkt jest na zewnątrz...

Sopelek997 · 9 Lipca 2014

A w kodzie sprawdzasz czy wszystkie na raz się przecinają.

Po za tym jest to mało wydajne.

Zenek97 · 9 Lipca 2014

w kodzie sprawdzam czy wszystkie na raz się nie przecinają = true, bo jak się przecina = false i ten długi IF się zatrzymuje

ale dobra zrobiłem inaczej, metodą z linków - zrozumiałem to tak że parzystą liczbę ma się przeciąć wzdłuż x i parzystą wzdłuż y (w moim przypadku dokładnie 4 razy)

kod zrobiłem po swojemu, nie wiem czy dobrze, trzeba po testować

#include<iostream>
using namespace std;

int licznikprzeciec=0;

void czysieprzecina(float Ax,float Ay,float Bx, float By, float Cx, float Cy, float Dx, float Dy)
{
	float x,y;
	x=((Bx-Ax)*(Dx*Cy-Dy*Cx)-(Dx-Cx)*(Bx*Ay-By*Ax))/((By-Ay)*(Dx-Cx)-(Dy-Cy)*(Bx-Ax));
	y=((Dy-Cy)*(Bx*Ay-By*Ax)-(By-Ay)*(Dx*Cy-Dy*Cx))/((Dy-Cy)*(Bx-Ax)-(By-Ay)*(Dx-Cx));


	if  (
			(((Cx<=x)&&(x<=Dx))||((Dx<=x)&&(x<=Cx)))	
			 &&
			(((Cy<=y)&&(y<=Dy))||((Dy<=y)&&(y<=Cy)))	 
		)
		{
			
		cout<<"przeciecie"<<endl;	licznikprzeciec++;} //text dla testu
		else {cout<<"brak"<<endl;	} //text dla testu
}

bool sprawdzpozycje(float x1, float y1, float x2, float y2, float x3, float y3, float x4, float y4, float xp, float yp)
{

	licznikprzeciec=0; //zerowanie licznika
	(czysieprzecina(-10000,yp,10000,yp,x1,y1,x2,y2)); // A-B wzdluż osi x
	(czysieprzecina(xp,-10000,xp,10000,x1,y1,x2,y2)); // A-B wzdluż osi y

	(czysieprzecina(-10000,yp,10000,yp,x2,y2,x3,y3)); // B-C wzdluż osi x
	(czysieprzecina(xp,-10000,xp,10000,x2,y2,x3,y3)); // B-C wzdluż osi y

	(czysieprzecina(-10000,yp,10000,yp,x3,y3,x4,y4)); // C-D wzdluż osi x
	(czysieprzecina(xp,-10000,xp,10000,x3,y3,x4,y4)); // C-D wzdluż osi y

	(czysieprzecina(-10000,yp,10000,yp,x4,y4,x1,y1)); // D-A wzdluż osi x
	(czysieprzecina(xp,-10000,xp,10000,x4,y4,x1,y1));   // D-A wzdluż osi y
	if (licznikprzeciec==4) //2x po x + 2x po y
		return true;
	else return false;
}

int main()
{
//double x1,y1,x2,y2,x3,y3,x4,y4,xp,yp;
//double Ax,Ay,Bx,By,Cx,Cy,Dx,Dy;
int n=0;

	cout<<"wprowadz 4-bok"<<endl;
	//cin>>x1>>y1>>x2>>y2>>x3>>y3>>x4>>y4;
	cout<<"wprowadz punkt"<<endl;
	//cin>>xp>>yp;
	//////////////////////////////////////
	//if (sprwadzpozycje (x1,y1,x2,y2,x3,y3,x4,y4,xp,yp))
	if (sprawdzpozycje(-293,16,-282,26,-276,113,-298,117,278.6,66.3))//powinien być na zewnatrz
		cout<<"punkt leży wewnatrz"<<endl;
	else 
		cout<<"punkt leży na zewnatrz"<<endl;
	cout<<"////////////////////"<<endl;
		if (sprawdzpozycje(-293,16,-282,26,-276,113,-298,117,16.1,-499.1))//powinien być na zewnatrz
		cout<<"punkt leży wewnatrz"<<endl;
	else 
		cout<<"punkt leży na zewnatrz"<<endl;

		cout<<"////////////////////"<<endl;
		if (sprawdzpozycje(286,82,275,88,300,183,316,200,298.2,149.8))//powinien być wewnatrz
		cout<<"punkt leży wewnatrz"<<endl;
	else 
		cout<<"punkt leży na zewnatrz"<<endl;


	cin>>n;
}

Sopelek997 · 9 Lipca 2014

Tylko po co liczysz te przecięcia w taki sposób. I po co aż 8. Nie musisz tych osi uznawać za odcinki, nawet nie powinieneś. Przeglądnij to jeszcze raz, dwa, spróbuj zrozumieć ten kod.

btw. Teraz widzę co w tym kodzie chciałeś zrobić (tym poprzednim), ale żeś to tak nielogicznie rozplanował, że sam się pewnie zgubiłeś, a ja dalej nie wiem co tam może być źle.

REPREDATOR · 10 Lipca 2014

Dlaczego błędne? (co prawda, metoda nie zadziała na wklęsłe, ale u mnie takich nie ma)

Dokładnie robię tak jak narysowałeś! Jeżeli te wszystkie - 8 przypadków się nie przetną, to świadczy o tym że punkt jest w środku.

Natomiast wystarczy że któraś się przetnie, czyli punkt jest na zewnątrz...

Zenek97 · 10 Lipca 2014

ale fail

Już mam na 100% działający, sprawdzam w prawo po x ma się przeciąć raz, następnie po y do góry ma się przeciąć raz

W sumie na wypukłe wystarczy sprawdzić raz, albo po x, albo po y. Ale zrobiłem po obu, żeby się wklęsłych nie bać :P

REPREDATOR · 10 Lipca 2014

Już mam na 100% działający,

Jak mozesz to wlep ten "na 100% dzialajacy" kod

_LostGalaxy_ · 10 Lipca 2014

ale fail

Już mam na 100% działający, sprawdzam w prawo po x ma się przeciąć raz, następnie po y do góry ma się przeciąć raz

W sumie na wypukłe wystarczy sprawdzić raz, albo po x, albo po y. Ale zrobiłem po obu, żeby się wklęsłych nie bać :P

I tak pewnie znowu znajdzie sie jakis blad :P A nawet jesli nie to twoja metoda pewnie ma spora zlozonosc. Pokaz ja na przykladzie albo omow lepiej to zobaczymy.

Nie prosciej zaimplementowac jakis gotowy algorytm?

Sopelek podał kod, a na stronie którą wkleiłem też jest link do kodu wszystkich metod.

Zenek97 · 11 Lipca 2014

#include<iostream>

using namespace std;

int licznikprzeciec=0;

void czysieprzecina(float Ax,float Ay,float Bx, float By, float Cx, float Cy, float Dx, float Dy)

{

float x,y;

x=((Bx-Ax)*(Dx*Cy-Dy*Cx)-(Dx-Cx)*(Bx*Ay-By*Ax))/((By-Ay)*(Dx-Cx)-(Dy-Cy)*(Bx-Ax));

y=((Dy-Cy)*(Bx*Ay-By*Ax)-(By-Ay)*(Dx*Cy-Dy*Cx))/((Dy-Cy)*(Bx-Ax)-(By-Ay)*(Dx-Cx));

if (

((((Ax<=x)&&(x<=Bx))||((Bx<=x)&&(x<=Ax))))&&((((Cx<=x)&&(x<=Dx))||((Dx<=x)&&(x<=Cx))))

&&

((((Ay<=y)&&(y<=By))||((By<=y)&&(y<=Ay))))&&((((Cy<=y)&&(y<=Dy))||((Dy<=y)&&(y<=Cy))))

)

{

cout<<"przeciecie"<<endl; licznikprzeciec++;} //text dla testu

else {cout<<"brak"<<endl; } //text dla testu

}

bool sprawdzpozycje(float x1, float y1, float x2, float y2, float x3, float y3, float x4, float y4, float xp, float yp)

{

licznikprzeciec=0; //zerowanie licznika

(czysieprzecina(xp,yp,10000,yp,x1,y1,x2,y2)); // A-B wzdluż osi x na prawo od x

(czysieprzecina(xp,yp,10000,yp,x2,y2,x3,y3)); // B-C wzdluż osi x na prawo od x

(czysieprzecina(xp,yp,10000,yp,x3,y3,x4,y4)); // C-D wzdluż osi x na prawo od x

(czysieprzecina(xp,yp,10000,yp,x4,y4,x1,y1)); // D-A wzdluż osi x na prawo od x

if (licznikprzeciec==1) // ma byc 1 przeciecie po x na prawo od x

{

licznikprzeciec=0; //zerowanie licznika

(czysieprzecina(xp,yp,xp,10000,x4,y4,x1,y1)); // D-A wzdluż osi y do góry

(czysieprzecina(xp,yp,xp,10000,x3,y3,x4,y4)); // C-D wzdluż osi y do góry

(czysieprzecina(xp,yp,xp,10000,x2,y2,x3,y3)); // B-C wzdluż osi y do góry

(czysieprzecina(xp,yp,xp,10000,x1,y1,x2,y2)); // B-A wzdluż osi y do góry

if (licznikprzeciec==1)// ma byc 1 przeciecie po y do góry od y

return true;

else return false;

}

else return false;

}

int main()

{

//double x1,y1,x2,y2,x3,y3,x4,y4,xp,yp;

//double Ax,Ay,Bx,By,Cx,Cy,Dx,Dy;

int n=0;

cout<<"wprowadz 4-bok"<<endl;

//cin>>x1>>y1>>x2>>y2>>x3>>y3>>x4>>y4;

cout<<"wprowadz punkt"<<endl;

//cin>>xp>>yp;

//////////////////////////////////////

//if (sprwadzpozycje (x1,y1,x2,y2,x3,y3,x4,y4,xp,yp))

if (sprawdzpozycje(-293,16,-282,26,-276,113,-298,117,278.6,66.3))//powinien być na zewnatrz