[pt] Apresenta-se nesta dissertação um novo algoritmo para o cálculo de algumas funções distância entre polígonos convexos, no caso geral em que os polígonos podem se interseptar, cuja complexidade linear de pior caso é melhor do que a dos algoritmos até então conhecidos na literatura. O algoritmo é baseado em um algoritmo de complexidade linear originalmente proposto para determinação da distância de Hausdorff entre polígonos convexos disjuntos e utiliza como sua principal componente um algoritmo linear para o cálculo da interseção entre polígonos convexos. A motivação para o estudo de algoritmos eficientes para este problema de cálculo de distâncias decorre de aplicações em reconhecimento de formas e superposição ótima de contornos. Resultados computacionais também são apresentados. / [en] We present in this dissertation a new algorithm for the computation of some distance functions between convex polygons, in the general case where they can intersect, whose worst case time complexity is better than of the previously known algorithms. The algorthm is based on an algorithm originally proposed for the computation of the Hausdorff distance between disjoint polygons and uses as its main component a linear time algorithm for finding the intersection of convex polygons. The motivation for the study of efficient algorithms for this distance computation problem comes from applications in pattern recognition and contour fitting. Computatioal results are also presented.

Denna studie undersöker om det är möjligt att införa nåbarhetstestning i en baneditor. Testets syfte är att ersätta manuell testing, det vill säga att bankonstruktören inte ska behöva spela igenom banan för att säkerställa att denne kommer kunna nå alla nåbara positioner.För att kunna utföra studien skapas en enkel baneditor som testplattform. Vidare utförs en jämförande studie av flera alternativa algoritmer för att fastställa vilken som är mest passande för nåbarhetstestning i en baneditor.Resultatet från den jämförande studien visade att A* (A star) var den mest passande algoritmen för funktionen. Huruvida automatisk testning kan ersätta manuell testning är diskutabelt, men resultatet pekar på en ökad effektivitet i tid när det kommer till banbygge. / The following study examines whether it is possible to implement reachability testing in a map editor designed for 2D-platform games. The purpose of reachability testing is to replace manual testing, that being the level designer having to play through the map just to see if the player can reach all supposedly reachable positions in the map.A simple map editor is created to enable the implementation after which we perform a theoretical study in order to determine which algorithm would be best suited for the implementation of the reachability testing.The results comparing algorithms shows that A* (A star) worked best with the function. Whether or not manual testing can be replaced by automatic testing is open for debate, however the results points to an increase in time efficiency when it comes to level design.

No description available.