Poligon formula - algoritam

[mslavko]

Da li postoji neka matematicka formula da se odredi da li odredjena tacka pripada poligonu?

Npr. Imamo sve tacke koje kada se spoje dobije se poligon i ostale tacke kojima je potrebno odrediti da li su unutar poligona?

Verovatno postoji neka matematicka formula ili algortiam???

Najblize sto sam nasao je ovo: http://sr.wikipedia.org/sr/%D0%A1%D0...82%D0%B0%D0%BC

[Br@nkoR]

Ukoliko ti je potebno za Google Maps Javascript API, u istom imaš metod containsLocation u okviru google.maps.geometry.poly

https://developers.google.com/maps/d...reference#poly

[ivanhoe]

http://en.wikipedia.org/wiki/Point_in_polygon

[mslavko]

Originalno napisao Br@nkoR

Ukoliko ti je potebno za Google Maps Javascript API, u istom imaš metod containsLocation u okviru google.maps.geometry.poly

https://developers.google.com/maps/d...reference#poly

Nije za google maps vec za bazu podataka... poligon crtam na google mapi medjutim sad moram iz baze da izvucem lokacije koje su unutar poligona...

[Miroslav Ćurčić]

Onako iz glave:
Tačka je u poligonu ako se nalazi unutar svih njegovih uglova.
Nađi kako odrediti da li je unutar ugla i eto rešenja.

[mslavko]

teorijski da, takodje

odredi se tacka koja je u poligonu i tacka ciju pripdnost treba ispitati, pa ako linija koja spaja te dve tacke preseca poligon znaci da tacka ciju vrednost treba ispitati nije u poligonu, obrnuto jste u poligonu...

sa neta sam naso ovo:

function insidePoly(poly, pointx, pointy) {
    var i, j;
    var inside = false;
    for (i = 0, j = poly.length - 1; i < poly.length; j = i++) {
        if(((poly[i].y > pointy) != (poly[j].y > pointy)) && (pointx < (poly[j].x-poly[i].x) * (pointy-poly[i].y) / (poly[j].y-poly[i].y) + poly[i].x) ) inside = !inside;
    }
    return inside;
}

videcu dal radi pa cu postaviti odgovor

[ivanhoe]

Jos lakse ti je da odredis tacku koja je sigurno van poligona (nju lako nadjes), spojis je linijom sa ovom drugom tackom i onda prebrojis koliko puta preseca ivice poligona. Ako je broj preseka neparan u poligonu je. Obrati paznju da moze da bude i paran broj preseka, u kom slucaju tacka nije u poligonu.

To se zove raycasting, ima detaljnije u onom Wiki clanku sto sam gore linkovao..

[mslavko]

A moze i ovako:

SELECT *  from locations where GISWithin(location, GeomFromText('Polygon(( 1 1, 1 100,100 1, 1 1))'));

[ivanhoe]

To je za PostgreSQL ili je i mySQL dobio GIS funkcije?

[mslavko]

Klasican mysql ali s obzirom da kolega radi backend deo (roadvoyage.com) nisam detaljno bas upoznat sa tim, ali mysql baza je upitanju...