Najkrajša pot in pot z najmanj ovinki : delo diplomskega seminarja

Lajovic, Luka (avtor), Cabello, Sergio (mentor)

V diplomski nalogi opišemo algoritem za iskanje najkrajše poti v večkotniku in algoritem za iskanje poti z najmanj ovinki. Algoritma delujeta v večkotniku, katerega triangulacijo že poznamo. Prvi algoritem direktno uporablja triangulacijo. Drugi algoritem pri iskanju poti z najmanj ovinki poišče večkotnike vidljivosti. Pri tem si pomaga z najkrajšo potjo iz prvega algoritma. Opišemo tudi več algoritmov za konstruiranje večkotnikov vidljivosti. Algoritem za najkrajšo pot sem tudi implementiral v obliki mobilne aplikacije.

• Jezik: Slovenski jezik
• Ključne besede: najkrajša pot, pot z najmanj ovinki, triangulacija, večkotnik vidljivosti, večkotnik
• Vrsta gradiva: Delo diplomskega seminarja/zaključno seminarsko delo/naloga
• Tipologija: 2.11 - Diplomsko delo
• Organizacija: FMF - Fakulteta za matematiko in fiziko
• Leto izida: 2019
• PID: 20.500.12556/RUL-112556
• UDK: 519.1
• COBISS.SI-ID: 18771033
• Datum objave v RUL: 24.10.2019

Sekundarni jezik

• Jezik: Angleški jezik
• Naslov: Shortest path and minimal link path

Izvleček

In this thesis we describe an algorithm for computing the shortest path between two points in a simple polygon and an algorithm for computing a minimum link path between two points in a simple polygon. Both algorithms require that a triangulation of the polygon is already given. The first algorithm uses the triangulation directly, while the algorithm for the minimal link path makes use of the shortest path already computed with the first algorithm in order to compute visibility polygons. We also describe several algorithms for computing visibility polygons. I also implemented the algorithm for computing shortest path as a mobile application.

• Ključne besede: shortest path, minimum link path, triangulation, visibility polygon, polygon