Algoritem za oktilinearno shematizacijo omrežijKeglevič, Domen (Avtor) Robič, Borut (Mentor) Algoritmirisanje grafovceloštevilsko programiranjeRisba grafa, ki ima povezave narisane z vodoravnimi, navpičnimi in diagonalnimi daljicami, se imenuje oktilinearna risba. Takšne risbe veljajo za pregledne in se pogosto uporabljajo za prikaz geografskih omrežij kot je zemljevid podzemne železnice večjih mest. Zaradi števila omrežij in raznolikosti risb nastane potreba po njihovem avtomatskem generiranju. Izkaže se, da je to računsko zahteven problem in algoritmi, ki to počnejo morajo narediti kompromis med časovno zahtevnostjo in kvaliteto izhoda. V tej magistrski nalogi je predstavljen nov algoritem, ki problem razdeli na dva koraka. Najprej generira risbo, ki je oktilinearna in ima vozlišča na istih koordinatah kot vhodni podatki. Nato takšno risbo izboljšuje s spreminjanjem dolžin povezav. To je formulirano v obliki linearnega celoštevilskega programa. Izkaže se, da ima tak pristop več zaželjenih lastnosti in da je njegova časovna zahtevnost konkurenčna v primerjavi z drugimi pristopi.20212021-09-09 08:15:03Magistrsko delo/naloga129881VisID: 119581COBISS_ID: 75340291sl