Keskustelu: Ohjelmointikysymykset: VB6: [vb6] Lähin pikseli kohdasta x,y

Hei,

Mikä olis nopein tapa etsiä esim mikä taulukossa olevistä pikseleistä on lähinnä esim. kohtaa 300,300?
Jos toiset x ja y kohdat on määritelty näin:

Dim tempXY() As PointAPI

tempXY(0).X=100
tempXY(0).Y=100

tempXY(1).X=400
tempXY(1).Y=300

tempXY(2).X=200
tempXY(2).Y=600

tempXY(3).X=600
tempXY(3).Y=300

Sen pitäisi siis vain palauttaa yllä olevista X,Y kohdista ne jotka sijaitsee lähimpänä kohtaa 300,300.

Ja toinen kysymys on että miten saan sen tietämään taulukon suurimman indeksin? Eli esim tuossa ylempänä suurin on 3, mutta se saattaa olla vaikka 100, ja olis tyhmää käydä kaikki läpi jos ne ei sisällä mitään.
PHP:ssa se käy kai Foreach funktiolla.. En tiedä onko VB:ssä sitä vaikka olen käyttänyt sitä 5000 kertaa enemmän.

Jos tosiaan muutat taulukon kokoa etkä vain käyttämääsi aluetta siitä, UBound-funktio kertoo ylärajan. Muussa tapauksessa sinulla varmaan olisikin jokin oma laskuri.

Nopeampaa tapaa ei ole kuin käydä taulukko läpi, laskea etäisyys (tai etäisyyden neliö, ettei tarvitse neliöjuurta) ja tarkistaa, onko se parempi kuin paras aiemmista. Aluksi tietenkin paras on tempXY(0).

Metabolix kirjoitti:

Nopeampaa tapaa ei ole kuin käydä taulukko läpi, laskea etäisyys (tai etäisyyden neliö, ettei tarvitse neliöjuurta) ja tarkistaa, onko se parempi kuin paras aiemmista.

Itse asiassa luulen, että on olemassa joissain tapauksissa nopeampi tapa, joka ei aina tarkasta koko taulukkoa. Oletetaan, että halutaan piste, joka on lähimpänä pistettä (0,0) ja taulukossa on pisteet (1,1) ja (100,0). Ensimmäiseksi tarkistetaan pisteen (1,1) etäisyyden neliö (0,0):sta, ja havaitaan, että tämä on 2. Nyt voidaan päätellä, että jos jonkin pisteen koordinaatti on kaksinumeroinen, niin se ei ole lähin piste. Siten pisteen (100,0) etäisyyttä tutkittaessa ei tarvitse tutkia kuin merkit "(10" ja hylätä piste heti tämän jälkeen. Toisaalta ylimääräisen if-lauseen tarkistus vie aikaa, ja nopeusetua saadaan vain jos monessa indeksissä oleva komponentti on liian iso. Aikamoista kikkailua, ja ei välttämättä nopeuta koodia ollenkaan,

Jos koordinaatit on tietyssä järjestyksessä, niin voidaan käyttää vaikkapa binäärihakua.

Jos pisteet voivat olla taulukossa missä tahansa järjestyksessä, koko taulukko täytyy käydä läpi, koska jos yhdenkin pisteen jättää väliin, juuri se voi olla lähin. Tietysti jos jonkin pisteen etäisyys on 0 ja yksi lähin piste riittää, haun voi keskeyttää.

Jos taulukko on järjestetty esim. x-koordinaatin mukaan, koko taulukkoa ei ehkä tarvitse tarkastaa. Esim. jos tutkittava piste on (50,23) ja jonkin pisteen etäisyys siihen on 3, ei tarvitse käydä läpi pisteitä, joiden x-koordinaatti on alle 47 tai yli 53. Kuitenkin muut pisteet voivat olla tutkittavan pisteen ympärillä esim. ympyrän muodossa, jolloin kaikki pisteet täytyy tarkastaa järjestyksestä huolimatta.

Lähimmän pisteen voi etsiä vakioajassa muodostamalla etukäteen taulukon, jossa jokaisesta mahdollisesta pisteestä kerrotaan, mikä piste on sitä lähinnä. On myös olemassa puurakenteita, joiden avulla lähimmän pisteen haun voi toteuttaa tehokkaasti, mutta niistä en tiedä tarkemmin.

Jaska kirjoitti:

Itse asiassa luulen, että on olemassa joissain tapauksissa nopeampi tapa

Joo, mutta nyt ei selvästikään ollut kyseessä "jokin tapaus". Onhan ongelmaan myös vakioaikainen ratkaisu siinä tapauksessa, että tiedetään, että pisteet on jo ennalta järjestetty halutun etäisyyden mukaan. Tosi kätevää, eikö? Kannattaisi ehkä tähänkin käyttää... ;)

Jos nopeus on tarpeen ja pisteitä ja vertailuja tulee paljon, quadtree-rakenne voi olla hyvä ja kohtalaisen helppo lähtökohta.

Antin mainitsema taulukkoratkaisu tunnetaan yleisemmin nimellä Voronoi-diagrammi. Sellaisen voi laskea kohtalaisen tehokkaasti hieman vaativalla algoritmilla, joka löytyy esimerkiksi seuraavan sivun kautta.

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

Luultavasti yksinkertaisempi jo esitetty ratkaisu on käytännössä ihan tarpeeksi nopea. Tällaiseen urheiluun tai puihin kiipeilyyn voi ryhtyä sitten, kun on selvästi nähnyt, että ohjelma viettää yli 90 % ajasta hakemalla näitä pisteitä. Voin rohkeasti arvata, että se ei vietä läheskään noin paljon.

Metabolix kirjoitti:

Jos tosiaan muutat taulukon kokoa etkä vain käyttämääsi aluetta siitä, UBound-funktio kertoo ylärajan. Muussa tapauksessa sinulla varmaan olisikin jokin oma laskuri.

Nopeampaa tapaa ei ole kuin käydä taulukko läpi, laskea etäisyys (tai etäisyyden neliö, ettei tarvitse neliöjuurta) ja tarkistaa, onko se parempi kuin paras aiemmista. Aluksi tietenkin paras on tempXY(0).

Tuota olin tekemässä, mutta ajattelin että on nopeampi tapa.