Iskanje najbližjega para točk

Pritisnite F11

Iz varnostnih razlogov je mogoče celozaslonski način vključiti samo s pritiskom na gumb F11 na tipkovnici.

Ko ste enkrat v celozaslonskem načinu, ga izključite spet s pritiskom na F11.

Iskanje najbližjega para točk

Avtor: Klavdia Budak

Iskanje najbližjega para točk

Najbližji par točk med točkami v ravnini

V dani množici točk v ravnini iščemo par najbližjih točk.

Sestava problema:

M je množica točk v ravnini = ,
Točka ima določene koordinate in
Razdalja med točkama dobimo z
Iščemo taka in , da bo razdalja najmanjša

Enostavni algoritem

Enostavni algoritem je neposredni pristop za izračun najkrajše razdalje med točkama. Izračunamo razdaljo za vsak par točk in nato poiščemo najmanjšo.

Psevdokoda enostavnega algoritma:

Algoritem najblizjiParTočk_enostavno(M):
        d <- razdalja(t1,t2) #izračunamo razdaljo med prvima dvema točkama
        n <- dolzina M
        for i from 1 to n-1 do:  #gremo od prve do predzadnje točke
            for j from i+1 to n-1 do:  #pri vsaki točki pregledamo vse točke od te točke do konca
                if razdalja(ti,tj) < d: #če je razdalja med točkama manjša od sedanje
                   d <- razdalja (ti,tj)   #jo shranimo
        vrnemo d

Vhodni podatek: Množica točk
Izhodni Podatek: Najmanjša razdalja med točkama v

Analiza algoritma

Osnovni operaciji pri enostavnem algoritmu sta izračun med dvema točkama in primerjava razdalij.
V primeru, ko imamo točk, se izvede izračunov razdalj in za eno manj primerjav razdalj.
Časovna zahtevnost takšnega algoritma je

Kako rešiti hitreje?
Z uporabo zahtevnejšega algoritma, kot na primer Deli in Vladaj, lahko rešimo problem hitreje in časovna zahtevnost zmanjšamo na .

Problem Deli in Vladaj

Problem najprej razdelimo na tri faze:

Faza DELI:
- Razdelimo problem na podprobleme
- Množico točk razdelimo na dva dela, kjer je v vsaki polovici približno polovico točk
Faza VLADAJ:
- Poda rešitev podproblemov rekurzivno, za vsako ravnino poišče par najbližjih točk
Faza ZDRUŽITEV:
- Združimo rešitve vsakega podproblema
- Ugotovimo, katera je najmanjša razdalja oz. par najbližjih točk

Določiti moramo zaustavitveni pogoj za rekurzivni algoritem

Problem delimo na podprobleme in te probleme še na manjše podprobleme, dokler ni problem majhen. Zaustavitveni pogoji zaustavijo delitev, če imamo 2 ali 3 točke.

Če : problem razdelitve nadaljujemo
Če : izračunamo razdaljo med točkama in vrnemo razdaljo
Če : izračunamo razdaljo med vsemi tremi točkami in vrnemo najkrajšo razdaljo

Faze Deli in Vladaj

Faza deli in vladaj

Faza delitve

V primeru če je točk v množici M več kot 3.
Množico točk v ravnini razdelimo na dve podmnožici (označeni z in ) z navpično mejo .

=> in =>
= in =
= => sredina med -koordinatami srednjih dveh točk.

Faza vladaj

V obeh delih in rekurzivno iščemo najkrajšo razdaljo oz. najbližji par točk.
Rešitev levi del množice nam poda najmanjšo dolžino in enako naredi za množico , pri kateri dobimo .

Prikaz delitve

Kako razdelimo množico točk na podmnožice? Najprej uredimo množico točk, tako da jih uredimo po -koordinati. Nato izračunamo . Spomnimo se enačbe, ki smo jo prej omenili = .

Primer:

Imamo množico 6 točk. Črto potegnemo ravno na sredi med točkama in . Na vsaki polovici ležita natanko 3 točke.
Če imamo množico 7 točk, črta tudi potegnemo na sredi med točkama in . Razlika je število točk na levi in desni polovici množice. V tem primeru na levi polovici ležita 3 točke, na desni pa 4 točke. Razpoloviščih njinuh koordinat je = .

Faza Združitve

Faza zdužitev

Izračunamo najmanjšo razdajo med in .
Pogledati je treba če obstaja kakšna manjša razdalja med točkama iz in (ena točka leži v , ena pa leži v ) kot dobljena razdalja.

Dobljeno razdaljo odmerimo od ločilne črte v levi in desni pas. V čezmejnem pasu poiščemo najkrajšo razdaljo in jo primerjamo z razdaljo . Točke razvrstimo po -koordinatah in nato po -koordinatah. Zato uporabimo metodo urejanje.

Sredinski pas

Pogledamo kako lahko omejimo na -smeri:
Ni potrebno preveriti vseh točk, le tiste, ki ležijo v pasu P. Oddaljene razdaljo za levo od in desno , od ločilne črte .
Pogledamo še kako lahko omejimo po -smeri:
Spet ni potrebno pogledati vseh parov točk. Pogledamo le tisto na množici točk, ki leži na drugi strani meje. Katera je oddaljena za manj kot razdalja .

Točke v sredinskem pasu 1.del

Točke v sredinskem pasu

Pogledali smo vse razdalje točk leve podmnožice in desne podmnožice. Pregledamo še ostale možne razdalje. Ostale možne razdalje so razdalje, ki imajo eno točko v levem pasu, drugo pa v desnem pasu. Smiselno je pogledat le točke, ki so možni kandidati. S pomočjo trenutne razdalje in mejne črte, ne potrebujemo pregledati vse razdalje od vseh točk do ostalih točk. Pas P nam omogoča hitrejše reševanje.

Točke morejo biti na vsaki strani med seboj oddaljene za razdaljo . V tem levem ali desnem pasu ležijo točke, ki so od mejne črte oddaljene za najmanj . V tem pasu pregledamo še ostale možne razdalje.

Razporedimo točke v pasu P po - smeri kot na sliki. Izberemo na primer točko C ( najbolj skrajna točka) in preverimo, ali je kakšna točka oddaljena za manj kot .

Točke v sredinskem pasu 2.del

Po pregledu okolice točke C za razdaljo , izključimo možnosti točk izven tega območja. V našem primeru ostane le točka D primerna. Z omejitvijo sredinskega pasu po -smeri smo dobili območje pravokotnika in višine .

Zadnja primerjava

Ugotoviti moremo le, koliko točk bi lahko ležalo na takem omejenem območju. S tem seznamom točk urejenih po -smeri lahko ugotovimo, ali je kakšna točka, ki bi zasedla mesto pred točko D.

Na vsaki strani meje lahko postavimo v kvadrat največ štiri točke, ki so najmanj oddaljena za razdaljo . Razdalja med oglišči je , točke zato lahko ležijo le v ogliščih kvadrata. Drugih točk ne moremo postaviti v to območje pri zahtevi, da morajo biti točke oddaljene med seboj za vsaj .

Če bi imeli točke po y koordinati urejene C,A,E,B,F,D (razporeditev točk na sliki spodaj), katere imamo po tri točke isto koordinato . Pregledamo razdalje glede na točko C, točka D je peta oddaljena točka. Vse nadaljnje točke so sigurno oddaljena za več kot razdalja .

Primer več točk

Točke v sredinskem pasu uredimo po -koordinati.Za vsako točko preverimo razdaljo za le pet nadaljnjih točk v seznamu. S tem zagotovimo pregled vseh morebitnih kandidatov za najbližji par točk. Namesto, da pregledujemo vse pare točk iz obeh polovic sredinskega pasu, pogledamo le razdaljo najbližjih pet v seznamu, urejenemu po -koordinati.

Analiza algoritma deli in vladaj

Zapis iskanja najbližjega para točk smo poenostavili na iskanje razdalje med najbližjima točkama. V samem algoritmu pa moramo poskrbeti, da se zabeležita in vrneta točki pripadajoči najmanjši razdalji.

Pred rekurzivno metodo uredimo točke po -koordinatah. Časovna zahtevnost je .

Ker za vsak podproblem iščemo rešitev rekurzivno in s tem je delitev približno polovica, bo skupno število rekurzivnih stopenj .

Časovna zahtevnost podfaze urejanja je , na vsaki fazi rekurzije algoritma se faza združevanja ponovi za . Celotni algoritem ima časovno zahtevnost = , kar je boljše od .

Algoritem lahko še izboljšamo, s pomočjo algoritma urejanje z zlivanjem. Z uporabo tega algoritma bi bil naš algoritem učinkovitejši. Pri zaustavitveni fazi, ko lahko problem rešimo neposredno, poskrbimo za ureditev točk po -koordinatah in tako dobimo urejen seznam. Pri višjih stopnjah rekurzije bo potrebno pri sestavljanju rešitve le združiti dva urejena seznama.

Vsaka faza združevanja vrne poleg najkrajše razdalje in para najbližjih točk še točke urejene po -koordinatah. Združevanje dveh urejenih množic zahteva le linearni čas .

Fazo združevanja dominirajo tri podfaze s časovno zahtevnostjo . Vseh rekurzivnih nivojev je , časovna zahtevnost algoritma je .

Psevdokoda algoritma Deli in Vladaj

Algoritem najblizjiParTočk_DiV(M):
    uredi M glede na x-koordinatah #pokličemo metodo za ureditev točk v M
    d,Y <-najdiNajblizjiParTočk(M) #pokličemo metodo za iskanje para najbližjih točk med urejenimi točkami
    vrnemo d

Vhodni podatki: Množica točk
Izhodni podatki: Razdalja najbližjega para točk

Algoritem najdiNajblizniParTočk(M):
    if je n <= 3 #če so v ravnini največ tri točke, izračunamo d neposredno
        if je  n = 2 #če sta le dve točki
            d <- razdalja(t1,t2) #izračunamo razdaljo med njima
        else #če so tri točke, izračunamo razdalje vseh treh točk
            d <- min(razdalja(t1,t2),min(razdalja(t2,t3), razdalja(t1,t3))) #poiščemo minimalno razdaljo teh treh točk
        Y <- uredi točke po y-koordinati
    else  #če je točk več kot 3, problem razdelimo
        razdeli M na dva enaka dela po številu točk ML in MD
        #v vsakem delu poiščemo rekurzivno par najbližjih točk
        dL,YL <- najdiNajbizjiParTočk(ML)
        dD,YD <- najdiNjablizjiParTočk(MD)

        Y <- zlij(YL in YD) #združimo oba urejena seznama v en seznam Y
        d <- min(dL,dD) #pogledamo katera rešitve  iz obeh delov je manjša
        P je sredinski pas, ki predstavlja točke v Y
        for i from 1 to |P|-1 do: #pogledamo vse točke v sredinskem pasu od prve do predzadnje
            j=1
            while i + j <= |P| & j <= 5:#od vsake točke pogledamo nadaljnje točke do konca seznama
                if razdalja(Pi,Pi+j) < d #če je razdalja manjša sedanje si zapolnimo
                    d <- razdalja(Pi,Pi+j)
            j = j + 1
    vrnemo d in Y

Vhodni podatki: Množica točk v ravnini , urejene po -koordinatah
Izhodni podatki: Razdalja med najbližjima točkama v množici in seznam točk, urejene po -koordinatah.