Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Jeli tocka dio nekog lika

[es] :: Art of Programming :: Jeli tocka dio nekog lika

[ Pregleda: 4073 | Odgovora: 7 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

NrmMyth
Ivan Maček
Split

Član broj: 63456
Poruke: 849
*.cmu.carnet.hr.

Sajt: www.dump.hr


Profil

icon Jeli tocka dio nekog lika14.04.2006. u 19:44 - pre 218 meseci
Zadan je lik svojim vrhovima i neka tocka. Kako efikasno odrediti dali je tocka untar toga lika?

:)
 
Odgovor na temu

McKracken
Vladimir Jovanovic
HuxleyDev

Član broj: 465
Poruke: 2941
*.sattvmeteor.co.yu.

ICQ: 203079925


+7 Profil

icon Re: Jeli tocka dio nekog lika14.04.2006. u 20:01 - pre 218 meseci
By using google

http://astronomy.swin.edu.au/%7Epbourke/geometry/insidepoly/


Naravno, postoje i efikasnija resenja
 
Odgovor na temu

NrmMyth
Ivan Maček
Split

Član broj: 63456
Poruke: 849
*.cmu.carnet.hr.

Sajt: www.dump.hr


Profil

icon Re: Jeli tocka dio nekog lika14.04.2006. u 20:45 - pre 218 meseci
thx pogledat cu
 
Odgovor na temu

peromalosutra
Ivan Rajkovic
Software engineer
Luxoft
Berlin

Član broj: 54774
Poruke: 871
*.dialup.blic.net.



+148 Profil

icon Re: Jeli tocka dio nekog lika15.04.2006. u 21:53 - pre 218 meseci
Uzmi proizvoljnu tačku za koju si siguran da se ne nalazi u datom liku (na primjer tacka Z[maxX+1][maxY+1], gdje su maxX i maxY najvece koordinate koje se pojavljuju u tackama koje opisuju zadano tijelo), i zatim spoji tako dobijenu tacku sa tackom koja ti je zadana. Te dve tacke spojene daju duz. Ako je broj ivica koje tako dobijena duz sjece paran, tacka se nalazi izvan lika, a ako nije, tacka se nalazi unutar tog lika. Evo ti i primjer programa koji određuje da li se 2 duzi sijeku... Ostatak je lak.

Code:

#include <iostream>
#include <fstream>
using namespace std;

struct tacka
{
       int x;
       int y;
};

struct duz
{
       tacka poc;
       tacka kraj;
};

int saIsteStr (duz p, tacka C, tacka D);
int intersect (duz d1,duz d2);

int main(int argc, char *argv[])
{
    ifstream in ("c:\\intersect.txt");
    tacka A,B,C,D; 
    in >> A.x >> A.y;
    in >> B.x >> B.y;
    in >> C.x >> C.y;
    in >> D.x >> D.y;
    in.close();

    duz d1,d2;
    d1.poc=A;  d1.kraj=B;
    d2.poc=C;  d2.kraj=D;   
    if (intersect(d1,d2))
       cout << "sijeku se\n";
    else
        cout << "ne sijeku se\n";
    
    system("PAUSE");
    return EXIT_SUCCESS;
}

int intersect (duz d1,duz d2)
{
    if ( (saIsteStr(d1,d2.poc,d2.kraj) ) &&
         (saIsteStr(d2,d1.poc,d2.kraj) ) )
         return 1;
    return 0;
}


int saIsteStr (duz p, tacka C, tacka D)
{
    /* 
       rez<0    ==> tacke C i D su sa suprotnih strana duzi p
       rez=0    ==> jedna od tacaka lezi na duzi p
       rez>0    ==> tacke C i D su sa istih strana duzi p
    */   
    
    int dx,dy,dx1,dx2,dy1,dy2, rez;
    dx=p.kraj.x-p.poc.x;
    dy=p.kraj.y-p.poc.y;
    
    dx1=C.x-p.poc.x;
    dy1=C.y-p.poc.y;
    
    dx2=D.x-p.kraj.x;
    dy2=D.y-p.kraj.y;
    
    rez=(dx*dy1-dy*dx1)*(dx*dy2-dy*dx2);
    if (rez>0)
       return 0;
    else
        return 1;    
}
 


@Toroman: Evo, uradio sam zadacu!!! :-)

[Ovu poruku je menjao peromalosutra dana 15.04.2006. u 22:54 GMT+1]

 
Odgovor na temu

ivan.mile

Član broj: 67586
Poruke: 22
*.ETF.BG.AC.YU.



Profil

icon Re: Jeli tocka dio nekog lika17.04.2006. u 09:05 - pre 218 meseci
Citat:
peromalosutra: Uzmi proizvoljnu tačku za koju si siguran da se ne nalazi u datom liku (na primjer tacka Z[maxX+1][maxY+1], gdje su maxX i maxY najvece koordinate koje se pojavljuju u tackama koje opisuju zadano tijelo), i zatim spoji tako dobijenu tacku sa tackom koja ti je zadana. Te dve tacke spojene daju duz. Ako je broj ivica koje tako dobijena duz sjece paran, tacka se nalazi izvan lika, a ako nije, tacka se nalazi unutar tog lika. Evo ti i primjer programa koji određuje da li se 2 duzi sijeku... Ostatak je lak.


Sve je to lepo ali nije baš tako. Šta ako je zadata tačka kolinearna sa jednom ili više ivica poligona? Šta ako je poligon konkavan? Šta ako je zadata tačka na liniji koja (zamišljeno) seče dve ivice poligona u istoj tački?

Malo pojašnjenje za ovaj poslednji slučaj: neka je zajedničko teme za neke dve ivice poligona na koordinatama (3,5) a zadata tačka na koordinatama (2,5). Tada detektuješ presek i sa jednom i sa drugom ivicom (ukupno 2 preseka) a tačka je unutar poligona. Po tvom algoritmu ispada da je napolju!

Poz,
-+- I V A N -+-
 
Odgovor na temu

NrmMyth
Ivan Maček
Split

Član broj: 63456
Poruke: 849
*.net.t-com.hr.

Sajt: www.dump.hr


Profil

icon Re: Jeli tocka dio nekog lika17.04.2006. u 11:18 - pre 218 meseci
Primjetio sam to... najbolje je sa onim jeli tocka lijevo/desno od pravca i to ce rijesiti problem.
 
Odgovor na temu

peromalosutra
Ivan Rajkovic
Software engineer
Luxoft
Berlin

Član broj: 54774
Poruke: 871
*.dialup.blic.net.



+148 Profil

icon Re: Jeli tocka dio nekog lika17.04.2006. u 21:00 - pre 218 meseci
Citat:
Po tvom algoritmu ispada da je napolju!


Nisam siguran da je to bas moj algoritam! Salu na stranu, algoritam samm preuzeo iz Sedgewickove knjige "Algorithms", gdje on za ovaj problem kaže:

Citat:

A straightforward solution to this problem immediately suggests itself:
draw a long line segment from the point in any direction (long enough
so that its other endpoint is guaranteed to be outside the polygon) and
count the number of lines from the polygon that it crosses. If the number
is odd, the point must be inside; if it is even, the point is outside.
This is easily seen by tracing what happens as we come in from the endpoint
on the outside: after the first line we hit, we are inside, after the second
we are outside, etc. If we proceed an even number of times, the point at
which we end up (the original point) must be outside.


@ivan.mile
Citat:
Malo pojašnjenje za ovaj poslednji slučaj: neka je zajedničko teme za neke dve ivice poligona na koordinatama (3,5) a zadata tačka na koordinatama (2,5). Tada detektuješ presek i sa jednom i sa drugom ivicom (ukupno 2 preseka) a tačka je unutar poligona. Po tvom algoritmu ispada da je napolju!

Nisi baš dao potpuni primjer, u redu, tačke se sjeku u koordinati (3,5), ali nisi naveo i drugu tačku za ove duži (da se odredi smjer prostiranja).
Koliko ja vidim, sam alogritam je dobar, ja sam ga provjerio i radi sa svim oblicima likova.
Ipak, čini mi se da si u pravu za jedno: ako duž koja spaja zadanu tačku u tijelu i proizvoljnu tačku izvan tijela prolazi kroz samu tačku gdje se sijeku 2 ivice, taj slučaj je kritičan... U svim ostalim slučajevima, algoritam bi ipak trebao raditi, a razmisliću malo o ovom zadnjem.

[Ovu poruku je menjao peromalosutra dana 17.04.2006. u 22:06 GMT+1]

 
Odgovor na temu

masetrt
Marko Djurovic
Programer, Omni-Explorer
Beograd

Član broj: 3129
Poruke: 228
195.252.94.*

Sajt: www.vast.com


+2 Profil

icon Re: Jeli tocka dio nekog lika20.04.2006. u 12:02 - pre 218 meseci
Uzmi sve presecne tacke duzi sa linijama poligona pa izbaci duplikate. I dalje ide ako je broj neparan unutra je u suprotnom van poligona je. Ako se duz preklapa sa nekom linijom poligona tretiraj to kao dve presecne tacke (pocetak i kraj linije poligona). Nisam bas dokazao da je ovo tacno, ali za sada nisam naisao na slucaj kada nije. Ukoliko neko jeste MOLIM da javi.
His majesty Grand Duke of Shumadija and Western Pomoravlje
 
Odgovor na temu

[es] :: Art of Programming :: Jeli tocka dio nekog lika

[ Pregleda: 4073 | Odgovora: 7 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.