Keskustelu: Ohjelmointikysymykset: VB.NET: Kahden pisteen välinen etäisyys älyttömän nopeasti!

Normaalisti kahden pisteen välinen etäisyys lasketaan näin(kuten kaikki varmaan tietävät):
2D:
sqrt((x1-x2)^2 + (y1-y2)^2)

Neliöjuuren ottamisessa kestää noin 70 kellojaksoa!
(liukulukukertolasku vie vain 1-3)

Nopeampi tapa on olemassa:
2D (.NET):

x = Math.Abs(x)
y = Math.Abs(y)
Dim mn as Integer = Math.Min(x,y)
Dim etaisyys as Integer = x+y-(mn>>1)-(mn>>2)+(mn>>4)

Tämä ei kuitenkaan ole täysin tarkka, vaan likiarvo!
maksimivirhe on kuitenkin vain 3,5%

Toivottavasti tästä on hyötyä jollekin, joka suunnittelee tekevänsä peliä. En tiedä käyttääkö esimerkiksi Linkku3D tätä tekniikkaa, jos ei käytä, niin tämä voisi sitä huomattavasti nopeuttaa!(Jos se ylipäätään käyttää kahden pisteen etäisyyttä)

Edit: Tämä algoritmi laskee pisteen etäisyyden origosta, muuta sitä voi silti soveltaa, kun transformoidaan pisteet maailmakoordinaatistosta siten, että toinen pisteistä on origo

Kuulostaa kiinnostavalta, mutta nyt en kyllä tajunnut tuota ohjelmaa kokonaan. Miten se toinen piste laitetaan tuohon mukaan (ohjelmassa on vain yksi x ja y)?

Hyvä huomio! Unohdin tuossa mainita! Tässä lasketaan pisteen etäisyys origosta. Näköjään muotioilin viestin epähuomiossa väärin.
No mutta kun ajatellaan, että origo on tuo toinen piste, niin on helppo sitten transformoida nämä koordinaatit maailmakoordinaatistoon. (Vie vieläkin vähemmän tehoa, kuin tavallinen algoritmi!)

Kiinnostavia juttuja VB.NETissä. Jos tulos on likiarvo, niin mikä tuo Math.Min(x,y) tarkkaanottaen on ja mitä mn>>1 jne. 3,5% on aika iso virhe joka kumuloituessa voi viedä metsään. Onko tuo 70 kellojaksoa .NETissä vai jossain muussa?

setä kirjoitti:

niin mikä tuo Math.Min(x,y) tarkkaanottaen on

Se palauttaa kahdesta arvosta pienemmän.

setä kirjoitti:

ja mitä mn>>1 jne.

mn >> 1 tarkoittaa shiftaa mn:n bittikuviota oikealle yksi askel. eli mn = 1/2^1, ainoa ero on se, että shift on konekielinen käsky ja siksi paljon nopeampaa on shiftata oikealle yksi askel kuin jakaa kahdella(jakokin on konekieltä, mutta shiftaaminen on tietääkseni nopeampaa)

setä kirjoitti:

3,5% on aika iso virhe joka kumuloituessa voi viedä metsään.

Jos tätä käytetään pelkästään etäisyyden laskemiseen ja sen käyttöön törmäystesteissä, niin tästä ei mielestäni ole haittaa. Ja tuo 3.5 % on ehdoton maksimi virhe!

setä kirjoitti:

Onko tuo 70 kellojaksoa .NETissä vai jossain muussa?

Ihan perus prosessorissa(konekielellä)

Tietääkö joku muuten vielä nopeampaa keinoa?

Nopeitten algoritmien kehittely on hieno juttu, mutta sikäli kuin oikein ymmärsin tuo kaava antaa epätarkimman tuloksen kun x = y ja sain virheeksi 7,2%. Mahdoinko laskea oikein. Eli jos x=y=10, tuo etäisyyden likiarvo on 20 - 5 - 2,5 + 0,625 = 13,13 ja oikea arvo on 14,14

Löysin yhden pienen vian. 20 - 5 - 2,5 + 0,625 = 13,13
mistä tuo 2,5 tulee?
10 >> 2 on 2, sillä binääri operaatioissa käytetään kokonaislukuja? Sehän on bittikuvion siftausta, jolloin desimaaleja ei tule. ja silloin siis 10 >> 4 on nolla.
Silloin tulos on pienempi.

En nyt halua sun hienoja systeemejä tyrmätä mutta kun olen ehkä taipuvainen pikkumaisuuksiin. Jos kokonaisosat ainoastaan otetaan mukaan, niin silloin tuo 0,625 jää myös pois ja tulos on 13 eli vielä huonompi. Toisaalta eihän noilla desimaalien poistamisilla ole suurta merkitystä. otetaan isommat luvut alkuun tai sopivat luvut, esim 16 ja 16. Silloin tulos on 32-8-4+1 = 21. oikea arvo 22,6 ja virhe 7,2%

No joo, mutta on tämä kai silti käyttökelpoinen joissakin tilanteissa?

Tottakai kun nopeus on etusijalla ja tarkkuudesta ei ole niin väliä. Virheen voi muuten laskea kaavasta:
cos(x) + 0,3125*sin(x) - 1, jossa x = 0 ... pii/4 eli asteina 0 .. 45. Virhe on aluksi 0, kasvaa 17 asteeseen, jossa se on lähes 5%, pienenee ja on taas 0 34 asteen kohdalla ja sitten putoaa tuohon -7,2%:iin 45 asteessa, jossa siis pysty- ja vaakaetäisyys on sama. Laskurutiinissa on huomattava myös käyttää aina x:n ja y:n itseisarvoja.

Eihän etäisyydessä vältämättä tarvita neliöjuurta, voihan esim. törmäystarkistuksessa korottaa vertailtava etäisyys myös toiseen potensiin.

etaisyys = sqrt((x1-x2)^2+(y1-y2)^2)
etaisyys^2 = (x1-x2)^2+(y1-y2)^2

Mielestäni tuo oma kaavani on vieläkin nopeampi, sillä jos ihan pikkumaisuuksiin lähdetään, niin kertolasku on paljon hitaampaa, kuin bittikuvion shiftaus tai yhteenlasku.