20.500.12556/RUL-87074 Problem pokrivnih poti Coverage path problem V nalogi obravnavamo problem pokrivnih poti. Pokrivna pot območja O je pot-krivulja P, od katere je vsaka točka območja O oddaljena največ za d, hkrati pa P poteka samo v notranjosti območja O. Iščemo pokrivno pot kar se da majhne dolžine. Omejimo se na primere s poligonskimi območji in poligonskimi pokrivnimi potmi. K problemu pristopimo na način deli in vladaj, poligonsko območje tlakujemo z manjšimi tlakovci, pokrivne poti na tlakovcih pa zlepimo v pokrivno pot celotnega območja. V nalogi opazujemo dve različni tlakovanji, trapezno in Boustrophedonovo tlakovanje, optimizacijo dolžine poti pa naredimo vzdolž različnih zaporedij pokrivanja tlakovcev in izbire ustrezne smeri tlakovanja. Metodi primerjamo na različnih tipih poligonov. Zaključimo lahko, da je Boustrophedonov pristop učinkovitejši, izbira optimalnega kota tlakovanja pa je bistveno odvisna od zveze med zahtevano bližino d in velikostjo območja. The thesis considers the coverage path planning CPP problem. A coverage path of a region O is a path-curve P ⊆ Q, so that for every point x ∈ O the distance between x and P is at most d. We are looking for a coverage path whose length is as small as possible. We focus on polygonal regions and also require that P is a polygonal line. We use a divide-and-conquer approach, we first tesselate our region with smaller tiles, respective coverage paths of individual tiles are later combined in a global coverage path. We limit ourselves to two different tesselations, a tesselation using trapeze tiles and the Boustrophedon tesselation. We optimize the length of the coverage path using different orderings of tiles along a coverage path as well as changing the direction of our tesselation. Considering several families of polygons we can state that choosing Boustrophedon tesselation outperforms the trapeze one, and that the choice of the optimal direction of the tesselation is highly dependent on the ratio between size of O and required resolution d. pokrivna pot območje ravninski poligon tlakovanje optimizacija poti najboljša smer coverage path region plane polygon tesselation path optimization best direction true false false Slovenski jezik Angleški jezik Diplomsko delo/naloga 2016-11-18 15:45:06 2016-11-18 15:45:10 2022-08-09 11:00:58 0000-00-00 00:00:00 2016 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 1970-01-01 18186 Komatar_Rok_-_Problem_pokrivnih_poti.pdf Komatar_Rok_-_Problem_pokrivnih_poti.pdf 1 EDB6D59BAED0731A3215A1027E8B5D72 de4caddab8c03e91bda84e2d54cb48c35c917a601a69fe0667fa70c232ad7cf7 15530f74-a1b1-11eb-a523-00155dcfd717 20.500.12556/rul/727d53f1-2549-4416-af22-78501f165904 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=90420 Fakulteta za računalništvo in informatiko 0 0 0