01.11.2007 10:48
[#1]
[algorytm] czy punkt jest wewnatrz wielokata
Hej, macie moze jakis pomysl jak rozwiazac taki problem?
Danych jest n punktow (p1, p2, ..., pn) ktore sa kolejnymi wierzcholkami wielokata wypuklego. Sprawdzic czy punkt X lezy wewnatrz tego wielokata. Macie moze jakis pomysl jak rozwiazac ten problem? Chodzi mi tylko o podpowiedz. Bo myslalem zeby znalesc 2 punkty, pomiedzy ktorymi lezy X z lewej i z prawej, i 2 pomiedzy ktorymi jest z gory i z dolu. A pozniej... no wlasnie, musialbym jakos sprawdzic czy lezy "nad" czy "pod" linia ktora wyznaczaja te punkty. Czy to jest dobry pomysl czy mozna to zrobic jakos inaczej?
Danych jest n punktow (p1, p2, ..., pn) ktore sa kolejnymi wierzcholkami wielokata wypuklego. Sprawdzic czy punkt X lezy wewnatrz tego wielokata. Macie moze jakis pomysl jak rozwiazac ten problem? Chodzi mi tylko o podpowiedz. Bo myslalem zeby znalesc 2 punkty, pomiedzy ktorymi lezy X z lewej i z prawej, i 2 pomiedzy ktorymi jest z gory i z dolu. A pozniej... no wlasnie, musialbym jakos sprawdzic czy lezy "nad" czy "pod" linia ktora wyznaczaja te punkty. Czy to jest dobry pomysl czy mozna to zrobic jakos inaczej?
01.11.2007 11:38
[#3]
Re: [algorytm] czy punkt jest wewnatrz wielokata
@mailman, post #2
Pomysl ciekawy ale bylby trudny do zrealizowania, bo np nie jest powiedziane w ktorym kierunku mialbym poprowadzic polprosta. Jesli np w lewo, a wielokat jest po prawej, to polprosta nigdy nie znajdzie wielokata i mogloby to sugerowac ze punkt lezy na zewnatrz (przynajmniej w granicach zakresu float) a matematycznie nie zawsze musi to byc prawdziwe. Wolalbym jakies bardziej "ogolne" rozwiazanie.
DODANO:
Znalazlem cos takiego: Link, ale zanim to skumam to minie troche czasu...
Ostatnia modyfikacja: 01.11.07 11:42
DODANO:
Znalazlem cos takiego: Link, ale zanim to skumam to minie troche czasu...
Ostatnia modyfikacja: 01.11.07 11:42
01.11.2007 11:45
[#4]
Re: [algorytm] czy punkt jest wewnatrz wielokata
@Lorak, post #3
kiedys to napisalem i dzialalo:
struct wspolrzedne
{
int x;
int y;
};
class area
{
string name; // nazwa obszaru
vector granica; // vector opisujacy granice
..
}
int sprawdz(int x, int y)
{
vector::iterator iter1;
vector::iterator iter2;
vector lista_x;
int x1,x2,y1,y2,x3,y3;
double a,b;
// cout <<"nX: " << x << " Y: " << y <<"n" << name << endl;
iter1 = granica.begin();
iter2 = granica.end();
iter1++;
// bedzimy badac w pętli od punktu 2 i 2-1
while(iter1 != iter2)
{
y1=(*(iter1-1)).y;
y2=(*(iter1)).y;
// cout <<"Y1: " << y1 << " Y2: " << y2 <<"n" << endl;
// sprawdzamy czy odcinek przecina wspolrzedna Y punktu
if (y1>y2)
{
if( (y2<=y) && (y1>y) )
{
x1=(*(iter1-1)).x;
x2=(*(iter1)).x;
if(x1==x2)
{
x3=x1;
}
else
{
// obliczamy wspolczynniki prostej przechodzacej przez 2 pkty
a=(y1-y2);
a/=(x1-x2);
b=y1-a*x1;
// printf("a: %f, b: %fn", a,b);
// obliczamy X punkt przeciecia
x3=(int)((y-b)/a);
}
// cout <<"X_3: " << x3 << " " << endl;
lista_x.push_back(x3);
}
}
else
if( (y2>=y) && (y1
x1=(*(iter1-1)).x;
x2=(*(iter1)).x;
if(x1==x2)
{
x3=x1;
}
else
{ // obliczamy wspolczynniki prostej przechodzacej przez 2 pkty
a=(y1-y2);
a/=(x1-x2);
b=y1-a*x1;
// printf("a: %f, b: %fn", a,b);
// obliczamy X punkt przeciecia
x3=(int)((y-b)/a);
}
// cout <<"X3: " << x3 << " "<< endl;
lista_x.push_back(x3);
}
iter1++;
}
sort(lista_x.begin(), lista_x.end());
for( int i = 0; i < lista_x.size(); i++ )
{
if(lista_x[ i ]>x)
if(i%2)
{
cout << "--------->" << name << endl;
return 1;
}
else
return 0;
}
return 0;
}
Ostatnia modyfikacja: 01.11.07 11:46
Ostatnia modyfikacja: 01.11.07 11:48
struct wspolrzedne
{
int x;
int y;
};
class area
{
string name; // nazwa obszaru
vector
..
}
int sprawdz(int x, int y)
{
vector
vector
vector
int x1,x2,y1,y2,x3,y3;
double a,b;
// cout <<"nX: " << x << " Y: " << y <<"n" << name << endl;
iter1 = granica.begin();
iter2 = granica.end();
iter1++;
// bedzimy badac w pętli od punktu 2 i 2-1
while(iter1 != iter2)
{
y1=(*(iter1-1)).y;
y2=(*(iter1)).y;
// cout <<"Y1: " << y1 << " Y2: " << y2 <<"n" << endl;
// sprawdzamy czy odcinek przecina wspolrzedna Y punktu
if (y1>y2)
{
if( (y2<=y) && (y1>y) )
{
x1=(*(iter1-1)).x;
x2=(*(iter1)).x;
if(x1==x2)
{
x3=x1;
}
else
{
// obliczamy wspolczynniki prostej przechodzacej przez 2 pkty
a=(y1-y2);
a/=(x1-x2);
b=y1-a*x1;
// printf("a: %f, b: %fn", a,b);
// obliczamy X punkt przeciecia
x3=(int)((y-b)/a);
}
// cout <<"X_3: " << x3 << " " << endl;
lista_x.push_back(x3);
}
}
else
if( (y2>=y) && (y1
x1=(*(iter1-1)).x;
x2=(*(iter1)).x;
if(x1==x2)
{
x3=x1;
}
else
{ // obliczamy wspolczynniki prostej przechodzacej przez 2 pkty
a=(y1-y2);
a/=(x1-x2);
b=y1-a*x1;
// printf("a: %f, b: %fn", a,b);
// obliczamy X punkt przeciecia
x3=(int)((y-b)/a);
}
// cout <<"X3: " << x3 << " "<< endl;
lista_x.push_back(x3);
}
iter1++;
}
sort(lista_x.begin(), lista_x.end());
for( int i = 0; i < lista_x.size(); i++ )
{
if(lista_x[ i ]>x)
if(i%2)
{
cout << "--------->" << name << endl;
return 1;
}
else
return 0;
}
return 0;
}
Ostatnia modyfikacja: 01.11.07 11:46
Ostatnia modyfikacja: 01.11.07 11:48
01.11.2007 12:04
[#5]
Re: [algorytm] czy punkt jest wewnatrz wielokata
@Lorak, post #3
Jesli np w lewo, a wielokat jest po prawej, to polprosta nigdy nie znajdzie wielokata i mogloby to sugerowac ze punkt lezy na zewnatrz (przynajmniej w granicach zakresu float) a matematycznie nie zawsze musi to byc prawdziwe.
Dlaczego? Skoro półprosta nie znajduje punktów przecięcia to znaczy, że w wyniku dzielenia tej liczby przecięć (czyli 0) przez dwa nie otrzymujesz reszty (a więc liczba parzysta). Zgodnie z tym co napisałem, parzysta oznacza punkt poza wielokątem. Kiedy będzie to matematycznie nieprawdziwe?
Dlaczego? Skoro półprosta nie znajduje punktów przecięcia to znaczy, że w wyniku dzielenia tej liczby przecięć (czyli 0) przez dwa nie otrzymujesz reszty (a więc liczba parzysta). Zgodnie z tym co napisałem, parzysta oznacza punkt poza wielokątem. Kiedy będzie to matematycznie nieprawdziwe?
01.11.2007 13:49
[#6]
Re: [algorytm] czy punkt jest wewnatrz wielokata
@mailman, post #5
Nie chodzi mi o to:) Chodzi o to ze petla ktora szuka punktu przeciecia musi sie kiedys skonczyc. A boki wielokata leza na tyle dalego ze int czy float do nich nie 'dojedzie' a mimo to punkt jest w srodku to wlasnie matematycznie to sie nie zgadza:) Ale to juz jest chyba problem zasiegu zmiennych.
Tylko chodzi o to ze ja chce samemu napisac i nie chodzilo mi o gotowca, a tylko o podpowiedzi. Niemniej jeszcze raz dzieki.
No wlasnie 