[es] - Odredivanje je li tocka unutar zadanog poligona

digas
Luka Djigas

Član broj: 103788
Poruke: 13
*.cmu.carnet.hr.

Profil

Odredivanje je li tocka unutar zadanog poligona

^{18.09.2006. u 02:12 - pre 226 meseci}

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

Odgovor na temu

Dragi Tata
Malo ispod Kanade

Član broj: 1958
Poruke: 3906
*.hsd1.ma.comcast.net.

+6 Profil

Re: Odredivanje je li tocka unutar zadanog poligona

^{18.09.2006. u 02:27 - pre 226 meseci}

http://local.wasp.uwa.edu.au/~pbourke/geometry/insidepoly/

IOCC

Odgovor na temu

digas
Luka Djigas

Član broj: 103788
Poruke: 13
*.fsb.hr.

Profil

Re: Odredivanje je li tocka unutar zadanog poligona

^{18.09.2006. u 07:44 - pre 226 meseci}

:) 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 : ')'

Odgovor na temu

Mali Misha
Mihajlo Anđelković
NBGD

Član broj: 79396
Poruke: 379
*.powernet.bg.

ICQ: 195487525
Sajt: cpptea.com

+1 Profil

Re: Odredivanje je li tocka unutar zadanog poligona

^{18.09.2006. u 08:29 - pre 226 meseci}

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

. 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.

Ipak se ++uje.

Odgovor na temu

ivan.mile

Član broj: 67586
Poruke: 22
*.adsl.sezampro.yu.

Profil

Re: Odredivanje je li tocka unutar zadanog poligona

^{24.09.2006. u 10:11 - pre 226 meseci}

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?

Odgovor na temu

digas
Luka Djigas

Član broj: 103788
Poruke: 13
*.cmu.carnet.hr.

Profil

Re: Odredivanje je li tocka unutar zadanog poligona

^{02.10.2006. u 23:59 - pre 226 meseci}

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

Odgovor na temu