[es] - Da li je tacka u poligonu (4-stranicnom)

markotasic
BALKAN

Član broj: 8815
Poruke: 93
212.124.182.*

Sajt: sartarata.port5.com

Profil

Da li je tacka u poligonu (4-stranicnom)

^{31.05.2003. u 23:54 - pre 266 meseci}

Da li neko zna kako da resim ovaj problem.

Neka su na primer dati:
1 poligon u 2D prostoru za pocetak 4-stranicni
1 tacka sa kordinatama P(2,2)

kao i tacke tog poligona:
A(0,0)
B(9,0)
C(3,3)
D(0,9)

Kako da znam da li je tacka u njemu.
Napomena: da nije u pitanju linearno programiranje i da to vazi za bilo koji poligon(4-stranicni)!!!

Odgovor na temu

Časlav Ilić
Braunšvajg, Nemačka

Član broj: 4945
Poruke: 565
195.252.80.*

+27 Profil

Re: Da li je tacka u poligonu (4-stranicnom)

^{01.06.2003. u 11:41 - pre 266 meseci}

Imam utisak da je ovo već dobro razrađena tema u svetu algoritama, ali ako se ne javi niko da iznese neko postojeće rešenje, evo jednog na brzinu.

Ako se dobro sećam, tačka A je unutar poligona ako je neparan broj preseka između proizvoljne poluprave, koja polazi iz tačke A, i stranica poligona. Praktično, to se svede na to da izabereš jednu tačku koja je sigurno van poligona (tačka B), a zatim prebrojiš koliko se stranica (duži) polinoma seku sa duži AB. Tačku B možeš da izabereš tako da joj je x-koordinata minimalna od svih x-koordinata temena polinoma, pa još umanjena za neku proizvoljnu vrednost (y-koordinata onda može da bude proizvoljna).

Ono što mene kopka, i što sam mislio uskoro da pitam, pa ajd' sad kad smo već kod toga: kako što brže (u smislu procesorskog vremena) proveriti da li se dve duži u ravni seku? Znači, ne treba da se odredi presek, nego samo da li se seku ili ne.

Odgovor na temu

markotasic
BALKAN

Član broj: 8815
Poruke: 93
212.124.182.*

Sajt: sartarata.port5.com

Profil

Re: Da li je tacka u poligonu (4-stranicnom)

^{01.06.2003. u 16:58 - pre 266 meseci}

TVOJ PROBLEM:
----------------------------------------------------------------------
Posto sam se dans pozabavio svom tematikom u vezi presecanja i poligoniranja pomocu cu ti da resis ovaj problem a kasnije cu navesti svoj.

Da bi znao da li se presecaju dve duzi prvo moras da znas kako se se presecaju dve prave:
1) y=(k1*x)+n1
2) y=(k2*x)+n2

presek ove dve prave je kako vec znas za x:

x=(n2-n1)/(k1-k2)

a za y:

y=(x*(k1+k2)+n1+n2) / 2

sada kada znas da li se presecaju ove dve prave posao je dosta pojednostavljen:

Xp - zajednicki presek za X
Yp - zajednicki presek za y

Xa - pocetna tacka duzi AB za x
Ya - pocetna tacka duzi AB za y
Xb - tacka na kraju duzi AB za x
Yb - tacka na kraju duzi AB za y

Xc - pocetna tacka duzi CD za x
Yc - pocetna tacka duzi CD za y
Xd - tacka na kraju duzi CD za x
Yd - tacka na kraju duzi CD za y

Da bi znao da li se presecaju mora da se ispuni sledeci uslov:

Xa <= Xp <= Xb
Ya <= Yp <= Yb

Xc <= Xp <= Xd
Yc <= Yp <= Yd

NAPOMENA: Ovo vazi samo ako je:
Xa<Xb Ya<Yb
Xc<Xd Yc<Yd
Za neku drugu kombinaciju moras da izvrsis ZAMENU kordinata.
Nadam se da ce ti ovo pomoci oko resavanja tvog problema.Ukoliko ti treba dodatno objasnjenje rado cu ti pojasniti.

MOJ PROBLEM:
----------------------------------------------------------------------

Imam dva poligona jedan unutar drugog.
Kako da izaberem onaj manji unutra a da se pri tome ne IZABERE ovaj drugi,veci.

Odgovor na temu

filmil
Filip Miletić
Oce Technologies B.V., inženjer
hardvera
Arcen, NL

Član broj: 243
Poruke: 2114
*.ptt.yu

Jabber: filmil@jabber.org
ICQ: 36601391

+3 Profil

Re: Da li je tacka u poligonu (4-stranicnom)

^{01.06.2003. u 20:44 - pre 266 meseci}

Jednostavan način da se utvrdi da li se dve duži seku je da se ispita
položaj krajnjih tačaka jedne duži u odnosu na drugu duž. Preseka ne
može biti ako obe krajnje tačke leže sa iste strane duži. Ovu proveru
svako zna da izvede, samo je pitanje kako izabrati računski
najjednostavniji način.

Probaću da predložim jednu mogućnost.

Da bih nastavio sa objašnjavanjem, moraću da uvedem sledeću
notaciju. Neka su date duži

svojim
krajnjim tačkama. Za prvu duž to su tačke

, a za
drugu

. Sve tačke date su svojim koordinatama, na
primer

.

Uvedimo vektor duži

sa:

i slično

. Par

takođe potpuno određuje duž. Neka je duž

,,prva``, a

,,druga``.

Želimo da proverimo da li se tačke druge duži nalaze sa iste strane
prve duži. To ćemo uraditi tako što nađemo projekciju vektora

na normalu na prvu duž i proverimo
da li projekcije imaju isti znak. Ako imaju, onda preseka ne može biti

(dokaz sledi).

Normalu možemo pronaći rotacijom duži

transformacijom

, i nalaženjem proizvoda

. Ovo se lako
računa jer je potrebna samo operacija promene znaka.

Dakle, neka su date vrednosti projekcije prve i druge razlike

i neka su obe tačke druge duži sa iste strane
prve duži, dakle

.

Sve tačke na drugoj duži su date sa:

Za projekciju svake tačke na drugoj duži važi:

Dakle svaka tačka na drugoj duži ima projekciju istog znaka kao

pa nema preseka, tako da možemo vratiti vrednost
false kao odgovor na pitanje da li presek postoji.

Ako makar jedna od dve provere pokaže da su tačke na drugoj duži sa
iste strane prve duži, preseka nema. Ukoliko oba preseka postoje,
postoje vrednosti

u obe provere koje ispunjavaju

, tj. preseci se nalaze između krajnjih tačaka
odgovarajućih duži. Kako je presek jedinstven, oba rešenja se odnose

na istu tačku. Možemo vratiti vrednost true kao odgovor
na pitanje da li se duži seku.

Kao što vidite, pri računanju koristimo samo računanje skalarnog
proizvoda, poređenja i promenu znaka tako da bi postupak trebalo da
bude (računski) jednostavan. Izbegava se deljenje pa prema tome i singulariteti.

f

[Ovu poruku je menjao filmil dana 02.06.2003. u 00:51 GMT]

[Ovu poruku je menjao Gojko Vujovic dana 04.02.2004. u 18:01 GMT]

Odgovor na temu

markotasic
BALKAN

Član broj: 8815
Poruke: 93
212.124.182.*

Sajt: sartarata.port5.com

Profil

Re: Da li je tacka u poligonu (4-stranicnom)

^{01.06.2003. u 22:39 - pre 266 meseci}

Ako se dobro secam tema ovog foruma je da se dokaze na sto jednostavniji nacin da li je tacka u nekom nekonveksnom ili konveksnom poligonu.

Radio sam malo na ovu temu i dosao do nekog zakljucka ali je to dosta spor processing (napomena: koristio sam linearno programiranje):

Ako sa A,B,C i D nazomvemo tacke postavljene u suprotnom smeru od smera kretanja kazaljke na satu,a sa P oznacimo proizvoljnu tacku.

Prvo odredimo za dve tacke pravu a zatim, u njoj zamenimo vrednosti za X i Y od preostale dve tacke(ako je prava kroz A i B tacke, onda su koordinate koje se zamenjuju od C i D). Ukoliko se dobije negativna vrednost onda se ta tacka nalazi ispod (-) prave u suprotnom iznad (+).
Pojasnjnje:
(+)
---
(-)

(+)/(-)

(-)|(+)

(-)\(+)

Isti postupak se primeni za ostale tri prave.Zatim posto smo npr dobili da je:
za pravu AB: C(+) i D(+)
za pravu BC: A(-) i D(+)
za pravu CD: A(-) i B(+)
za pravu DA: B(+) i C(+)

Napomena: ukoliko su obe tacke sa pozitivne strane onda one daju da se od jednacine za datu jednacinu dobije nejednacina koja je potpuno ista samo sto se umesto "=" pise ">="; ukoliko su oba znaka ili bar jedan od njih onda pisemo "<" umesot znaka jednakosti.
Posto smo formirali nejednacine vidimo da li data tacka P(x,y) zadovoljava uslov za svaku nejenacinu.
Napomena: ova fora pali samo kod konveksnih poligona, mada radi kod nekonveksnih poligona ali kod nekih u odredjenom podrucju.

MENI JE POTREBAN DOSTA JEDNOSTAVNIJI I BRZI PROCES ZA OVU TEMU !!!!
Napomena: pokusao sam onu foru koje se "secas" ali bez nekih uspeha, ili si mi je ti rekao pogresno ili sam ja nesto pogresno uradio!!

Odgovor na temu

filmil
Filip Miletić
Oce Technologies B.V., inženjer
hardvera
Arcen, NL

Član broj: 243
Poruke: 2114
*.ptt.yu

Jabber: filmil@jabber.org
ICQ: 36601391

+3 Profil

Re: Da li je tacka u poligonu (4-stranicnom)

^{01.06.2003. u 22:53 - pre 266 meseci}

Marko,

Izvini zbog prekomerkog drvljenja u prethodnoj poruci. :) Trebalo je držati se teme. Rešenje problema koji te zanima postoji u knjizi:

Udi Manber, "Algorithms, a creative approach" (http://www.amazon.com/exec/obi.../002-3590181-4022410?vi=glance)

Ne bi trebalo da je veliki problem da nabaviš ovu knjigu, bilo iz biblioteke ili, khm, na, ovaj, drugi način.

Ako je poligon konveksan, dovoljno je proveriti na način koji si opisao da se tačka P nalazi sa iste strane svake od stranica kao i težište poligona. Ako poligon nije konveksan onda nema druge nego da se pronađe broj preseka sa stranicama poligona, a da bi to uradio efikasno pametno je kupiti zanat iz gore pomenute knjige.

f

Odgovor na temu

markotasic
BALKAN

Član broj: 8815
Poruke: 93
212.124.182.*

Sajt: sartarata.port5.com

Profil

Re: Da li je tacka u poligonu (4-stranicnom)

^{02.06.2003. u 00:45 - pre 266 meseci}

Nikada ti nebi zameri, ti meni pomazes.Hvala u svakom slicaju.
Svario sam onu teoriju sa parnim i neparnim presecima.

Ali se javlja sledeci problem:
Imam jedan mali u jedan veliki poligon. Kako to da kad je tacka u veliki, ali izvan malog, da znam da je tacka u velikom. Odnosno kad je tacka u malom da se zna da se ne radi sa velikim jer tacka naravno da pripada.

Posto imam "malo" godina a "puno" znanja ne mogu sve proobleme da resim.Dobro bi mi dosla ova pomoc jer sam danas redio matematiku od 10:00 do 17:00 pa od 21:00 do 22:30, mozes da predpostavis kako je mom mozgu, a kako mom "najboljem drugu" bez ijedne devojke u blizini, naravno sutra cu da nadoknadim vreme.Hahaha.

Odgovor na temu

tOwk
Danilo Šegan
Zemun/Beograd

Član broj: 94
Poruke: 2743
*.beograd-3.tehnicom.net

ICQ: 9344053
Sajt: alas.matf.bg.ac.yu/~mm011..

+2 Profil

Re: Da li je tacka u poligonu (4-stranicnom)

^{02.06.2003. u 04:49 - pre 266 meseci}

Ako sada imaš f-ju u_poligonu(P, X), i imaš dva poligona A (veći), i B (manji).

Traženi rezultat je (u_poligonu(A,X) && !u_poligonu(B,C)).

Ako ti je ideja da ubrzaš implementaciju, onda koristiš:
u_poligonu(B,X) || u_poligonu(A,X)

što će u većini programskih jezika proveriti prvo da li je u malom poligonu (B), a ako nije samo onda proveriti da li je u velikom (A) poligonu.

Možda se moje mišljenje promenilo, ali ne i činjenica da sam u pravu.

Odgovor na temu

Časlav Ilić
Braunšvajg, Nemačka

Član broj: 4945
Poruke: 565
195.252.80.*

+27 Profil

Re: Da li je tacka u poligonu (4-stranicnom)

^{02.06.2003. u 10:47 - pre 266 meseci}

Kôd za proveru preseka duži, prema Filipovom tekstu, brži je za khm, khm, oko 70 puta od onog što sam prethodno imao :) Pošto sam se pažljivije pogledao kakvo sam to čudovište prethodno napravio, ispalo je da je zbog jedne gluposti bilo oko 7 puta sporije nego što treba, što znači da je ovo novo rešenje realno oko 10 puta brže. Svoj problem sam ovim rešio, pošto je problematični program od 30-ak sekundi rada, gubio 20-ak na provere preseka (inače, u pitanju je program za crtanje dijagrama :)

Evo kôda:

Code:

bool
check_same_side (double a1x, double a1y, double a2x, double a2y,
                 double b1x, double b1y, double b2x, double b2y)
{
    double p1 = (b1x - a1x) * (a1y - a2y) + (b1y - a1y) * (a2x - a1x);
    double p2 = (b2x - a1x) * (a1y - a2y) + (b2y - a1y) * (a2x - a1x);
    return p1 * p2 > 0;
}

bool
check_intersect (double a1x, double a1y, double a2x, double a2y,
                 double b1x, double b1y, double b2x, double b2y)
{
    if (check_same_side(a1x, a1y, a2x, a2y, b1x, b1y, b2x, b2y))
        return false;
    return not check_same_side(b1x, b1y, b2x, b2y, a1x, a1y, a2x, a2y);
}

Za Marka, vvo i provere da li je tačka u polinomu:

Code:

bool
check_in_poly (double px[], double py[], uint np, double ax, double ay)
// px[] - polynom point x-coordinates
// py[] - polynom point y-coordinates
// np   - number of polynom points
// ax   - point x-coordinate
// ay   - point y-coordinate
{
    // Find outer point: point with minimal x-coordinate, and then minus some.
    double aox = px[0];
    double aoy = py[0];
    for (uint i = 0; i < np; i++)
        if (px[i] < aox)
        {
            aox = px[i];
            aoy = py[i];
        }
    aox -= 1.0;
    aoy -= 1.0;

    // Count intersections.
    uint numint = 0;
    for (uint i = 0; i < np - 1; i++)
        if (check_intersect(ax, ay, aox, aoy,
                            px[i], py[i], px[i + 1], py[i + 1]))
            numint++;

    // Don't forget to check for intersection with side [0, np - 1].
    if (check_intersect(ax, ay, aox, aoy,
                        px[0], py[0], px[np - 1], py[np - 1]))
        numint++;

    // If number of intersections is odd, the point is in poly.
    return numint % 2 == 1;
}

Doduše, nisam ovu funkciju nešto specijalno testirao. Biće problema ako se spoljna tačka namesti tako da dobijena duž za prolazi „tačno“ kroz neko teme polinoma.

Odgovor na temu

markotasic
BALKAN

Član broj: 8815
Poruke: 93
212.124.182.*

Sajt: sartarata.port5.com

Profil

Re: Da li je tacka u poligonu (4-stranicnom)

^{02.06.2003. u 23:01 - pre 266 meseci}

Zanima me sta predstavlja (i da li se dobija nekako) px() i py() , kakvi su to polinomi x i y kordinata.
Nazalost znam da radim u basic-u malo mi teze ide kada prevodim ove codove za c(planiram da za otprilike mesec dana pocnem da ucim), pa bih zamolio ako nije problem da mi pojasnite na neki nacin basic-srpskog jezika (ako to - onda to).

Odgovor na temu

Časlav Ilić
Braunšvajg, Nemačka

Član broj: 4945
Poruke: 565
*.ppp-bg.sezampro.yu

+27 Profil

Re: Da li je tacka u poligonu (4-stranicnom)

^{03.06.2003. u 12:05 - pre 266 meseci}

Najbolje da ti pokažem na tvom primeru iz prve poruke:

Code:

    // ...

    const uint np = 4; // 4-sided polygon.
    double px[np], py[np];
    px[0] = 0; py[0] = 0; // A(0,0)
    px[1] = 9; py[1] = 0; // B(9,0)
    px[2] = 3; py[2] = 3; // C(3,3)
    px[3] = 0; py[3] = 9; // D(0,9)

    double ax, ay;
    ax = 2; ay = 2; // P(2,2)

    if (check_in_poly(px, py, np, ax, ay))
        cout << "Point is inside polygon." << endl;
    else
        cout << "Point is outside polygon." << endl;

    // ...

Odgovor na temu

markotasic
BALKAN

Član broj: 8815
Poruke: 93
212.124.182.*

Sajt: sartarata.port5.com

Profil

Re: Da li je tacka u poligonu (4-stranicnom)

^{04.06.2003. u 12:02 - pre 266 meseci}

Hvala na objasnjenju. Napravio sam to sto sam hteo.
Medjutim, interesuje me kako da znam da li se tacka nalazi u pligonu ali sa 3D kordinatama .

Odgovor na temu

tOwk
Danilo Šegan
Zemun/Beograd

Član broj: 94
Poruke: 2743
*.beograd-3.tehnicom.net

ICQ: 9344053
Sajt: alas.matf.bg.ac.yu/~mm011..

+2 Profil

Re: Da li je tacka u poligonu (4-stranicnom)

^{04.06.2003. u 15:37 - pre 266 meseci}

Prvo proveriš da li su sve te tačke u istoj ravni (za svake 4 treba da proveriš, a ako je već poznato da su tačke koje navodno predstavljaju poligon zaista u jednoj ravni, onda samo tu novu tačku uporediš sa proizvoljne tri nekolinearne tačke iz poligona). To ti je najlakše pomoću linearne kombinacije.

Zatim, sve ove gore date formule proširiš jednom koordinatom, i dodaš jednu transformaciju koordinatnog sistema :-P

Možda se moje mišljenje promenilo, ali ne i činjenica da sam u pravu.

Odgovor na temu

markotasic
BALKAN

Član broj: 8815
Poruke: 93
212.124.182.*

Sajt: sartarata.port5.com

Profil

Re: Da li je tacka u poligonu (4-stranicnom)

^{04.06.2003. u 20:43 - pre 266 meseci}

Hvala ti na objasnjenju,ali...

kako da kad imam mnogo,mnogo,monog poligona, neki se nalaze unutar drugih, neki presecaju druge, kako to da znam da ako sam unutra nekog koji je unutar nekog a on unutar nekog (i tako redom) da je to onaj sto meni treba.

kako da znam gde su presecne tacke dve duzi, bez da koristim jednacine prave, ili da izbegnem rad sa koeficijentima pravca.

Odgovor na temu