Najbliže rastojanje između jedne duži i jedne tačke ?

[ Predrag Damnjanovic @ 12.12.2003. 16:28 ] @

Zamislite sledeću situaciju.
Na jednoj površi (recimo ekran) imamo dvadesetak duži, razbacanih nasumice, neke duži se seku...
Naravno, imam koordinate svih duži.
Korisnik treba da klikne na neku duž, a pošto ne može tačno na duž da klikne, znači da će kliknuti par pixela pored duži, i ja trebam da nađem koja je duž najbliža, tj. pored koje duži je korisnik kliknuo.

Rešenje koje ja imam u glavi je da se nađe najbliže rastojanje od te tačke (gde se klikne) do duži, i tako da se ispita svaka duž, pa koja bude najbliža...
To može preko jednačine pravca, ali, mi ovde imamo duži, šta ako projekcija tačke uopšte ne pada na duž?
Dakle, korisnik klikne skroz desno, a duž je skroz levo (recimo horizontalna duž).
Tu jednačina pravca nije od koristi, dobio bi samo rastojanje između tačke i prave, a to mi ne treba.

Tu mogu samo da računam rastojanje od tačke (gde se klikne) do tačke A i B (duž AB).
Ali, lako uopšte da ispitam da li je projekcija tačke izvan duži?

Ili ja idem u pogrešnom smeru, možda ima neko bolje rešenje.
Dakle, treba da se selektuje duž :)

Ima li neko da je imao sličan problem, možda neko ima iskustva sa ovim problemom?

[ filmil @ 12.12.2003. 16:38 ] @

Seti se jednačine trougla. Zbir rastojanja tačke do krajeva duži treba da bude (skoro) jednak dužini te duži. Duž kod koje je razlika minimalna je duž koju tražiš.

f

[ Goran Rakić @ 12.12.2003. 18:20 ] @

analitička geometrija u ravni, matematika za drugu godinu srednje škole

imaju baš primeri koji se odnose na tvoj problem, filmil je (kao i obično) dao dobro rešenje. Meni je pala na pamet površina, ali to može da zavara ako korisnik klikne u produžetku duži jer će P tada biti 0. Problem može biti ukoliko imaš bliske duži ili duži koje se seku (pa u onom delu sa naspramnim uglovima "uhvatiš" klik), ali to možeš rešiti povećanjem preciznosti ili ostaviti kao slučaj gde će se prva duž "izabrati".

[ Mihailo Kolundzija @ 13.12.2003. 02:42 ] @

Moj predlog ti je da prvo izvršiš transformaciju u novi kooridnatni sistem, čiji je početak u jednom od temena duži koju posmatraš, a x osa mu se poklapa sa tom duži. Onda će ti već biti lako – samo treba da odrediš da li je dobijena x koordinata tačke između 0 i l, gde je l dužina duži za koju vršiš proveru. Rastojanje od duži će ti naravno biti nova y koordinata. Doduše, možeš još malo da zakomplikuješ, pa da proveravaš figuru oko duži u obliku atletske staze (dodatne provere da li se tačka nalazi unutar nekog od dva kruga, što nije neki problem).
Ako negde nisam pogrešio, transfomraciju koordinata obaviš sa:

gde su ti

koordinate temena duži,

koordinate tačke u prvobitnom sistemu, a

koordinate u novom sistemu.

Pretpostavljam da se može pogoditi i nula duži, pa bi trebao da imaš neki prag iznad kojeg sve odbacuješ kao promašaj.

[ Predrag Damnjanovic @ 13.12.2003. 13:33 ] @

Resio sam problem sa ispitivanjem da li projekcija pada na duz...
Objavicu sors kad zavrsim funkciju.

[ Goran Rakić @ 13.12.2003. 15:07 ] @

Čekaj, znači tražiš normalnu projekciju klika na duž? Odnosno projekciju duži (Jedan-kraj-duži)-(Tačka-klika)? Pa onda ispituješ "udaljenost" projekcije? Zar ti nije lakše da onda tražiš samo normalu iz tačke na pravu sa ograničenjem na duž? Međutim, postoji problem kada je tačka u pravcu neke duži. Pojasni malo, ako nije problem.

[ Predrag Damnjanovic @ 13.12.2003. 17:21 ] @

Code:

double deli (double a, double b)
{
    if (a==0 || b==0) return 0;
    return a/b;
}

double rastojanje (double x1, double y1, double x2, double y2)
{
    return sqrt (pow(y1-y2,2)+pow(x1-x2,2));
}

double rol (double x1, double y1, double x2, double y2, double x3, double y3) // rastojanje od linije
{
    if ((x1==x2) || (y1==y2))
    {
        if (x1==x2)
        {
            if (((y1<=y3)&&(y3<=y2)) || ((y1>=y3)&&(y3>=y2))) return fabs (x3-x1);
        }
        else
        {
            if (((x1<=x3)&&(x3<=x2)) || ((x1>=x3)&&(x3>=x2))) return fabs (y3-y1);
        }
    }
    else
    {
        double A = y2 - y1;
        double B = x1 - x2;
        double C = ( x2 - x1 ) * y1 - ( y2 - y1 ) * x1;
        double x4 = deli ( ((x2-x1)*(y2-y1)*(y3-y1)) + ((y2-y1)*(y2-y1)*x1) + ((x2-x1)*(x2-x1)*x3), ((y2-y1)*(y2-y1))+((x2-x1)*(x2-x1)) );
        double y4 = deli(x4*(y2-y1), x2-x1) + y1 - deli(x1*(y2-y1), (x2-x1));

        char h, v;

        if (x1<x2)
        {
            if (x1<=x4 && x4<=x2) h=1;
            else h=0;
        }
        else
        {
            if (x1>=x4 && x4>=x2) h=1;
            else h=0;
        }

        if (y1<y2)
        {
            if (y1<=y4 && y4<=y2) v=1;
            else v=0;
        }
        else
        {
            if (y1>=y4 && y4>=y2) v=1;
            else v=0;
        }
        if (h==1 && v==1) return fabs (deli ( A * x3 + B * y3 + C, sqrt (A*A + B*B) ));
    }

    double d1 = rastojanje (x3, y3, x1, y1);
    double d2 = rastojanje (x3, y3, x2, y2);
    if (d1<d2) return d1;
    else return d2;
}

[ Časlav Ilić @ 14.12.2003. 11:45 ] @

Ovo je pomalo neodređen problem, ako se posmatra kao „rastojanje tačke od duži“, pošto to baš i nije definisan pojam. Ako je zaista potrebno da korisnik bira duži (tj. to nije bila samo ilustracija), mislim da je Filipovo rešenje, koga bih nazvao „gravitacionim“, najbolje. Sa njim se može desiti da je tačka bliža manjoj nego većoj duži, i da njena projekcija pada na obe duži, pa da ipak bude izabrana veća duž. Ali to je upravo ono što bi korisniku i odgovaralo, pošto oko više upoređuje rastojanja (podložno optičkim varkama), nego što može da odredi stvarno rastojanje. Eventualno bi za tačke krajeva duži koje ne staju cele na ekran mogli da se uzmu ne stvarni krajevi, već preseci sa ovirom pogleda.

[ Predrag Damnjanovic @ 14.12.2003. 13:37 ] @

Citat:

filmil:
Seti se jednačine trougla. Zbir rastojanja tačke do krajeva duži treba da bude (skoro) jednak dužini te duži. Duž kod koje je razlika minimalna je duž koju tražiš.

f

Ne bi smeo tu metodu da koristim, jer...
zamisli jednu liniju od 100 cm, i jednu od 10 cm.
Recimo da su paralelne, da je rastojanje izmedju te dve duzi 20 cm, i da je ova mala duz na sredini.

Zamisli da klikne samo 2 cm od te velike duzi, bas na sredini, gde je i ova mala duz.
Znaci, on je udaljen 18 cm od te male duzi, a samo 2 cm od te velike.

Ako uzmemo tvoju metodu - izabrace se mala duz, iako je 9 puta dalja od velike duzi.

... jer, tacke ove velike duzi su dalje (52+52) od tacke ove male duzi (20+20).

[ filmil @ 14.12.2003. 14:03 ] @

Citat:

"Predrag Damnjanovic" wrote:
Ako uzmemo tvoju metodu - izabrace se mala duz, iako je 9 puta dalja od
velike duzi.

Mislim da si pogrešno razumeo ideju. A ideja je da je tačka blizu duži ako izlomljena linija koju čine početna tačka duži, izabrana i krajnja „dovoljno dobro“ liči na duž. Ako je tačka negde blizu duži, onda će razlika dužine duži i dužine izlomljene linije biti mala. Što je tačka bliža duži, razlika će biti sve manja, da bi, kada je tačka tačno na duži, razlika bila 0.

Poređenje ovih razlika za razne duži i biranje one čija je razlika minimalna će ti dati duž koju je korisnik „izabrao“. Naravno, da bi mogao da porediš razlike koje potiču od različitih duži, svaku razliku možeš podeliti dužinom te duži.

Tako dobijaš niz relativnih razlika za svaki par (duž, izabrana tačka), iz koga biraš najmanju razliku i iz nje određuješ o kojoj se duži radi.

Možeš proveriti da 1) tvoj primer u tom slučaju radi baš kako bi se očekivalo i 2) da je oblast oko svake duži unutar koje klik znači da je duž izabrana zapravo oblika elipse čije su žiže u krajnjim tačkama duži a ekscentricitet zavisi kako se izabere ona „dovoljno mala“ veličina.

f

[ Predrag Damnjanovic @ 14.12.2003. 16:37 ] @

sada kapiram :)
nisam te razumeo na pocetku, jer nisi spomenuo 'relativnost' :)

mozda sprovedem to u delo, jer je proces racunanja znatno manji, pa ce funkcija verovatno raditi brze...

[ Mihailo Kolundzija @ 14.12.2003. 17:13 ] @

Samo da se ispravim, pošto sam napravio grešku kod onih sinusa i kosinusa. Treba da stoji:

su koordinate temena duži. Mislim da bi na ovaj način funkcija bila jednostavnija.
Uzgred, zašto pozivaš funkciju za deljenje kad si u startu obezbedio da imenilac ne može biti nula?

U stvari, evo ti funkcija, pa ti vidi (samo da napomenem da je pisana "po suvom", tako da može da bude i grešaka).

Code:

double rastojanje(double x1, double y1, double x2, double y2, double x, double y) {
  double cos_a, sin_a, duzina_duzi, dx, dy;
  double x_p, y_p;

  if (x1 == x2 && y1 == y2) /* u slucaju da se temena duzi poklapaju */
    return ((x - x1) * (x - x1) + (y - y1) * (y - y1));

  dx = x2 - x1;
  dy = y2 - y1;

  duzina_duzi = sqrt(dx * dx + dy * dy);

  cos_a = dx / duzina_duzi;
  sin_a = dy / duzina_duzi;

  x_p = (x - x1) * cos_a + (y - y1) * sin_a;
  y_p = -(x - x1) * sin_a + (y - y1) * cos_a;

  /* nije naspram duzi, vec sa leve strane */
  /* racuna se rastojanje od desnog temena */
  if (x_p < 0)
    return sqrt(x_p * x_p + y_p * y_p);

  /* nije naspram duzi, vec sa desne strane */
  /* racuna se rastojanje od desnog temena */
  else if (x_p > duzina_duzi)
    return sqrt((x_p - duzina_duzi) * (x_p - duzina_duzi) + y_p * y_p);

  /* tacka naspram duzi, pa je rastojanje jednako */
  /* apsolutnoj vrednosti y_p */
  else
    return fabs(y_p);
}

[ Predrag Damnjanovic @ 17.12.2003. 19:28 ] @

Citat:

Mihailo Kolundzija:
U stvari, evo ti funkcija, pa ti vidi (samo da napomenem da je pisana "po suvom", tako da može da bude i grešaka).

Funkcija nema greske, radi odlicno :)
Hvala!

[ zi:: @ 29.12.2003. 06:02 ] @

Za ovaj, a i za ostale geometrijske algoritme toplo preporučujem sledeći sajt:
http://www.geometryalgorithms.com/
Kodovi su pisani čitkim pseudojezikom i lako se implementiraju u bilo kojem jeziku.
Naravno, matematička poleđina je isto prisutna zbog kompletnosti.

Za tvoj problem se odnosi konkretno ova strana:
http://www.geometryalgorithms....orithm_0102/algorithm_0102.htm

[ septembar @ 05.01.2004. 13:55 ] @

Meni za tačno računanje rastajanja tačke od duži izgleda najjednostavniji sljedeći postupak:

Skalarni proizvod:
1) (a,b)=a1*b1+a2*b2+a3*b3 ili
2) (a,b)=|a|*|b|*cos(a,b)

3) abs_AB=sqrt((A1-B1)^2+(A2-B2)^2);

Ako su A i B tjemena duži a C tačka do koje treba izračnati rastojanje.

sa=(AB,AC)... po (1)
sb=(BA,BC)

ako je abs_AB>0 onda
ako je sa*sb>0 d=sa/abs_AB
ako je sa<0
d=abs_AC
inače
d=abs_BC
inače
d=abs_AC

Za nalaženje najbliže duži nema potrebe racunati sqrt u (3).