Voronoin diagrammin sovellukset reitinhaussa

Abstract

Reitinhaussa on tavoitteena löytää sopiva reitti paikasta toiseen. Reitinhaulle on sovelluksia monella alalla. Tässä tutkielmassa käsitellään erään laskennallisen geometrian rakenteen, Voronoin diagrammin, käyttöä reitinhaussa. Voronoin diagrammin avulla saadaan löydettyä reittejä, jotka pysyttelevät mahdollisimman kaukana esteistä. Tällainen reitti ei ole pituudeltaan optimaalinen, minkä takia sitä muokataan useissa sovelluksissa lyhyemmäksi säilyttäen kuitenkin tarvittava etäisyys esteisiin. Tutkielmassa esitellään myös sovelluksia, joissa käytetään Voronoin diagrammin eri variaatioita tai yhdistetään se muihin menetelmiin. Lisäksi Voronoin diagrammiin perustuvia reitinhakumenetelmiä vertaillaan muihin reittikarttapohjaisiin menetelmiin.

The goal of pathfinding is to find a suitable path from one place to another. Pathfinding has applications in several fields. This thesis deals with the use of a computational geometry structure called the Voronoi diagram in pathfinding. With the help of the Voronoi diagram one can find paths that stay as far away from obstacles as possible. This kind of path is not optimal with respect to length, which is why in many applications it is modified to be shorter while only the required distance to obstacles is retained. The thesis also presents applications where different variations of the Voronoi diagram are used or where it is combined with other methods. In addition, pathfinding methods based on the Voronoi diagram are compared with other roadmap-based methods.