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

Lajovic, Luka (author), 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.

• Language: Slovenian
• Keywords: najkrajša pot, pot z najmanj ovinki, triangulacija, večkotnik vidljivosti, večkotnik
• Work type: Final seminar paper
• Typology: 2.11 - Undergraduate Thesis
• Organization: FMF - Faculty of Mathematics and Physics
• Year: 2019
• PID: 20.500.12556/RUL-112556
• UDC: 519.1
• COBISS.SI-ID: 18771033
• Publication date in RUL: 24.10.2019

Secondary language

• Language: English
• Title: Shortest path and minimal link path

Abstract

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.

• Keywords: shortest path, minimum link path, triangulation, visibility polygon, polygon