[es] - Pronalazenje poligona levo, desno, gore i dole od tekuceg poligona

DarkMan
Darko Matesic

Član broj: 20445
Poruke: 572
*.ptt.yu.

Jabber: DarkMan

Profil

Pronalazenje poligona levo, desno, gore i dole od tekuceg poligona

^{24.10.2007. u 18:50 - pre 200 meseci}

Napisao sam neki svoj algoritam da odredim susedni poligon ali nisam bas zadovoljan.
Da bi bilo lakse za testiranje algoritma napravio sam primer. Pretrazivanje se odvija kada korisnik pritiska tastere strelica gore, dole, levo i desno. U gornjem delu mi je jos i nekako ok, ali mi se odredjivanje suseda u donjem delu ne svidja. Primer izgleda ovako:

Algoritam za odredjivanje suseda je u zadnjoj metodi klase Polygon:

Code:

        public static int NextPolygon(List<Polygon> polygons, int current, Keys direction)
        {
            if(polygons != null && polygons.Count > 0 && current >= 0 && current < polygons.Count) {
                Point currentCenter = polygons[current].Center;
                int min_index = -1;
                double min_dist = -1;
                for(int i = 0; i < polygons.Count; i++) {
                    if((direction == Keys.Up && polygons[i].Center.Y < (currentCenter.Y - 4)) ||
                       (direction == Keys.Down && polygons[i].Center.Y > (currentCenter.Y + 4)) ||
                       (direction == Keys.Left && polygons[i].Center.X < (currentCenter.X - 4)) ||
                       (direction == Keys.Right && polygons[i].Center.X > (currentCenter.X + 4))) {
                        double dist = PointDistance(currentCenter, polygons[i].Center);
                        if(min_dist < 0 || dist < min_dist) { min_dist = dist; min_index = i; }
                    }
                }
                return min_index;
            }
            return -1;
        }

Poligoni se sastoje od 4 tacke. Metodi se prosledjuje lista svih poligona, indeks tekuceg i kojeg suseda trazimo.
U mom algoritmu sam trazio najmanje rastojanje od poligona i to samo od poligona koji se nalaze na zeljenoj strani (ako se trazi gore onda samo ako je centar poligona iznac centra tekuceg, itd...)
Ako poligon nije pronadjen vraca se -1.

Ako neko zna bolje resenje neka postavi.

Primer je napisan u C#.

_{[Ovu poruku je menjao DarkMan dana 25.10.2007. u 13:47 GMT+1]}

Prikačeni fajlovi

PolygonTest.zip - 32.53k

polygontest.png - 35.04k

Odgovor na temu

vlaiv
Vladimir Vlaisavljevic
Novi Sad

Član broj: 15993
Poruke: 352
*.ADSL.neobee.net.

+1 Profil

Re: Pronalazenje poligona levo, desno, gore i dole od tekuceg poligona

^{14.11.2007. u 17:08 - pre 200 meseci}

Da, zanimljiva problematika.

Koliko vidim ti si se kretao po 4 jedinice duzine u datom pravcu dok nisi naleteo na tacku koja je dovoljno blizu datom drugom poligonu u listi...

Ne, greska, gledas one poligone ciji centar se nalazi na ...

Uh skoro da sam se izgubio ... :)

Elem ono sto bih ti ja preporucio da radis je sledece:

Da uzmes Osu (x odnosno y) koja prolazi kroz centar pocetnog poligona, zatim uzmes distance do te ose centara poligona ukoliko sama osa
prolazi kroz poligon ili najblizeg temena ukoliko osa ne prolazi kroz poligon.

I nadjes odgovarajucu metriku tako da ti je za sve slucajeve od interesa (prostorno pozicioniranje poligona) vizuelno zadovoljavajuca
selekcija narednog.

Na osnovu ove metrike sortiras listu poligona i odaberes najblizi (to i radis u kodu, ne kroz sort vec trazeci onaj sa najmanjom metrikom)

Opet i ova postavka moze biti problematicna zato sto za osnovu uzimas centar polaznog poligona, pogotovu kada imas poligone
ciji je odnos dimenzija po x i y osi daleko od 1 (znaci izduzeni po x-u ili y-u)

Sledeci pristup koji bi mogao da usvojis je:

Da nadjes distancu izmedju poligona u odgovarajucem pravcu koja se definise kao

najmanje pravolinijsko rastojanje izmedju dve tacke koje pripadaju pocetnom i trazenom poligonu takvo da je ugao koji duz izmedju te
dve tacke zaklapa sa poluosom koja definise pravac (gore, dole, levo desno) manji od 45 stepeni ...

Ovo neka ti bude metrika za sortiranje.

Da upravo sam mentalno provrteo ovo poslednje i video da na konkretnom primeru koji si dao, moze da dodje do neocekivanih rezultata.

Predlazem da pored minimalnog rastojanja definisanog na ovaj nacin, metriku formiras i iz samog ugla koji zaklapa sa osom ...
(sto blize osi, to blize pocetnom poligonu)

Odgovor na temu

DarkMan
Darko Matesic

Član broj: 20445
Poruke: 572
77.46.228.*

Jabber: DarkMan

Profil

Re: Pronalazenje poligona levo, desno, gore i dole od tekuceg poligona

^{15.11.2007. u 14:30 - pre 200 meseci}

Hvala ti na predlozima!
Probao sam drugi predlog tj. da se proverava ugao izmedju centra tekuceg i posmatranog poligona. Ova tehnika je dala odlicne rezultate sa postojecim poligonima.
Evo i novog algoritma:

Code:

        public static int NextPolygon(List<Polygon> polygons, int current, Keys direction)
        {
            if(polygons != null && polygons.Count > 0 && current >= 0 && current < polygons.Count) {
                Point currentCenter = polygons[current].Center;
                int min_index = -1;
                double min_dist = -1;
                for(int i = 0; i < polygons.Count; i++) {
                    if(i != current && InView(currentCenter, polygons[i].Center, direction)) {
                        double dist = PointDistance(currentCenter, polygons[i].Center);
                        if(min_dist < 0 || dist < min_dist) { min_dist = dist; min_index = i; }
                    }
                }
                return min_index;
            }
            return -1;
        }

        public static bool InView(Point src, Point dest, Keys direction)
        {
            double angle = Math.Atan2(dest.Y - src.Y, dest.X - src.X) / Math.PI * 180;
            if(angle < 0) angle = 360 + angle;
            return (direction == Keys.Up && angle >= 225 && angle <= 315) ||
                   (direction == Keys.Down && angle >= 45 && angle <= 135) ||
                   (direction == Keys.Left && angle >= 135 && angle <= 225) ||
                   (direction == Keys.Right && ((angle >= 0 && angle <= 45) || (angle >= 315 && angle <= 360)));
        }

Hvala jos jednom na savetu!

Prikačeni fajlovi

PolygonTest_v2.zip - 37.07k

Odgovor na temu