[ digas @ 18.09.2006. 02:12 ] @
Pozdrav svima !

Iz filea ucitavam x,y koordinate tocaka, koji se spajaju pravcima i cine obicno neki nepravilni poligon. Problem se sastoji u odredivanju da li se neka nova tocka, nalazi unutar ili van tog poligona.
Primjer: imamo cetiri tocke
(0,0)
(0,5)
(5,5)
(5,0)
(kvadrat)
Da li tocka (6,5) upada unutra ili van ?

Ne znam kako uopce pristupiti problemu. Razmisljao sam da vrsim linearnu interpolaciju, pa ispitujem za zadanu tocku da li je veca ili manja od x odnosno y koordinate... je li se netko do sada susretao s ovako necim?
Sve ideje dobrodosle.

pozdrav
dig
[ Dragi Tata @ 18.09.2006. 02:27 ] @
http://local.wasp.uwa.edu.au/~pbourke/geometry/insidepoly/
[ digas @ 18.09.2006. 07:44 ] @
:) Nevjerojatno. Bas sam prije kojih pola sata naletio na istu.

Ne vidim sto ne valja s ovim drugim dijelom. Prijedlozi ?

pozdrav
dig

p.s. uz ovo bi jos trebala ici neka rutina koja provjerava da li je neka od tocaka jednaka nekoj
od tocaka polinoma. Ali kako mi to ne treba za ovo sto radim, nije mi se dalo trudit.
/////////////////////////////////source
#include <iostream.h>
#include <fstream.h>
#include <math.h>

int pnpoly(int npol, float *xp, float *yp, float x, float y)
{
int i, j, c = 0;
for (i = 0, j = npol-1; i < npol; j = i++)
{
if ( ( ((yp <= y) && (y < yp[j])) || ((yp[j] <= y) && (y < yp)) ) &&
(x < (xp[j] - xp) * (y - yp) / (yp[j] - yp) + xp) );
c = !c;
}
return c;
}

main()
{
int npol=4;
float xp[]={0,0,5,5};
float yp[]={0,5,5,0};
float x=6;
float y=7;
cout << pnpoly(int npol, float *xp, float *yp, float x, float y);
return 0;
}
/////////////////////////////////output
pol.cpp
pol.cpp(24) : error C2144: syntax error : missing ')' before type 'int'
pol.cpp(24) : error C2660: 'pnpoly' : function does not take 0 parameters
pol.cpp(24) : error C2059: syntax error : ')'
[ Mali Misha @ 18.09.2006. 08:29 ] @
Da, prepoznajem ideju..

Dve stvari na koje bi trebalo paziti su (1) moguća pripadnost tačke nekoj stranici poligona, kao što je napomenuto u tekstu i (2) mogućnost da tačka leži na pravoj koja pripada stranici poligona i da je ta prava paralelna sa polupravom kojom ispituješ poligon.

Pripadnost tačke A duži PQ:

Možeš naći jednačinu prave PQ, i nakon toga proveriti (1) da li koordinate A zadovoljavaju tu jednačinu (2) da li je za . To znači da tačka pripada duži.

Prvi deo uslova možeš da zameniš i sa:

Ako ovo nije slučaj, i uz to ni jedna stranica poligona nije paralelna sa vektorom poluprave kojom ispituješ preseke, možeš bezbedno da ispitaš broj preseka. Pazi na slučaj kada poluprava prolazi tačno kroz neko teme.
[ ivan.mile @ 24.09.2006. 10:11 ] @
Citat:

int npol=4;
float xp[]={0,0,5,5};
float yp[]={0,5,5,0};
float x=6;
float y=7;
cout << pnpoly(int npol, float *xp, float *yp, float x, float y);
return 0;
}
/////////////////////////////////output
pol.cpp
pol.cpp(24) : error C2144: syntax error : missing ')' before type 'int'
pol.cpp(24) : error C2660: 'pnpoly' : function does not take 0 parameters
pol.cpp(24) : error C2059: syntax error : ')'


Promeni ovaj red sa cout tako da bude
cout << pnpoly(npol, xp, float yp, x, y);

Jel' sad radi?
[ digas @ 02.10.2006. 23:59 ] @
Da, naravno da radi. Shvatio sam u cemu je greska iduci dan, valjda sam bio malo preumoran kada
sam ovo postao. Elementarna stvar.
U svakom slucaju, hvala svima na pomoci.

pozdrav
dig