Orientador: Sérgio Augusto Cunha / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Educação Física / Made available in DSpace on 2018-08-17T12:23:18Z (GMT). No. of bitstreams: 1 Santana_JulianaExel_M.pdf: 6461488 bytes, checksum: 731aaed1e02fe448da4b39f4f7b8fb28 (MD5) Previous issue date: 2011 / Resumo: O desempenho de jogadores de futebol de elite durante uma partida é diretamente influenciado por fatores físicos, psicológicos, técnicos, táticos e entre outros. Um suporte científico capaz de buscar e aplicar metodologias que quantifiquem esses fatores é uma fonte importante de informações para que técnicos e treinadores tenham melhores condições de efetuar uma boa preparação da sua equipe. Dentro dos estudos cinemáticos no esporte, a videogrametria tem se mostrado uma ferramenta acurada para a obtenção da posição dos jogadores em função do tempo. Dentro dos aspectos táticos de um jogo de futebol, a forma como uma equipe divide o campo em áreas de responsabilidade e como essa distribuição se dá ao longo do jogo pode ser descrita através de técnicas matemáticas. Nesse sentido, o objetivo deste estudo será apresentar uma forma de representação da área de responsabilidade de jogadores de futebol durante partidas oficiais, através do Diagrama de Voronoi. Para tal, foram coletadas as imagens de 4 jogos de futebol. Os processos de segmentação das imagens e de rastreamento dos jogadores para a obtenção dos dados 2D em função do tempo foram realizados através do software DVideo®. Para as análises, foi aplicado a metodologia do Diagrama de Voronoi nas coordenadas 2D de 33 jogadores de uma mesma equipe, a cada instante de tempo, em cada jogo. Dado um conjunto de pontos no plano (que nesse caso, representam as posições dos jogadores em função do tempo), o Diagrama de Voronoi divide o plano em regiões de acordo com as distâncias entre os pontos desse conjunto, chamados Polígonos de Voronoi. As áreas dos polígonos foram calculadas. Essa ferramenta permite, através de uma representação por mapas de superfície, obter um resumo dos locais do campo contidos nos Polígonos de Voronoi associados a cada jogador, durante todo o jogo. As áreas de responsabilidade foram maiores para goleiros, laterais e atacantes, quando comparados aos zagueiros e volantes e meias.Para caracterizar a região de responsabilidade dos jogadores, foi utilizado o contorno topográfico correspondente às áreas do campo contidas nos Polígonos dos jogadores por no mínimo 60% do jogo. Os resultados obtidos para os jogos estudados mostram que o contorno que caracteriza a área de responsabilidade para os jogadores é uma boa ferramenta qualitativa e quantitativa, que representa a forma como os jogadores dividem a área do campo entre si. A utilização do Diagrama de Voronoi se mostrou uma técnica eficiente na determinação das áreas de responsabilidade dos jogadores. Técnicos e treinadores podem dessa maneira obter informações adicionais importantes para a criação de melhores estratégias de posicionamento da sua equipe para uma melhor cobertura do espaço do campo de futebol / Abstract: The performance of football elite players is directly influenced by physical, psychological, technical and tactical aspects. A scientific support capable of seek and apply methodologies to quantifying these factors is an important source of information to coaches improve their conditions to well prepare their teams. About football tactical aspects, the manner a team share the pitch in responsibility areas and how this distribution behaviours during the match can be described through mathematical techniques. Thus, the aim of this study is to show players' responsibility area during official matches using Voronoi Diagram (VD). To do so, we collected images of 4 football matches. To extract 2D players' coordinates during the entire match, images segmentation, tracking and 2D reconstruction were performed in DVideo® software. In the analysis, VD method was applied to players' 2D coordinates to all 33 players of a same team, at each instant of time and in the 4 matches. Given a set of points on plan (representing players positions as function of time), VD share the plan in regions according to distances between all points of the set, called Voronoi polygons (VP). Voronoi areas were calculated a determined as players' responsibility areas. This tool permits obtaining a summary of pitchlocations inside Voronoi polygons of each player, during the entire match, using hitmaps. To characterize responsibility areas, the contours of hitmaps corresponding to pitch areas inside VP by, at least, 60% of the match were performed. The results showed contours as an effective tool to qualitatively and quantitatively represent responsibility areas in a match. Besides, mathematical properties related to known geometric structures, as convex polygons, facilitate calculating areas. They showed be higher to goalkeepers, external defenders and forwards when compared to central defenders, defensive and offensive midfielders / Mestrado / Biodinamica do Movimento Humano / Mestre em Educação Física

No description available.

傳統之選區劃分多採用人工方式進行，不但費時耗力，同時不容易維持公平公正之原則，導致客觀性受扭曲而產生爭議。歷史上透過選區劃分來操弄選舉最有名的例子首推美國麻州的傑利蠑螈劃分方式，因此後人在選區劃分時必須堅守公平客觀之原則，自動化之選區劃分應運而生。以電腦科技自動劃分選區不但省時省力，同時也能滿足公平公正等客觀的選區劃分要求。 過去我們提出了一系列的選區劃分方法，著重於產生大量的劃分解集合，並從中挑選形狀較佳之解，卻沒有考慮到維持鄉鎮市層級行政區之完整性。本論文中，我們提出了一套新的選區劃分方式，除了考慮鄉鎮市層級行政區之完整性外，同時考慮選取較佳之起始點，以獲得較佳之選區形狀，成功的劃分出良好的選區。 我們首先從挑選較佳之起始點，透過質心范諾圖的觀念劃分出形狀較完整之初始選區，然後修正各選區之人口至合理的誤差範圍內，再進行鄉鎮市層級行政區分割數之修正，以避免該層級行政區被過渡分割。由於行政區分割數修正可能影響並擴大人口誤差，為確保人口誤差維持在合理範圍內，我們進行第二次人口修正，以免人口誤差過大，隨後進行形狀調整以提高凸包面積比，最後再度進行鄉鎮市層級行政區分割數修正，儘量少分割鄉鎮市層級之行政區域。 實作中我們以台北市為例，採用四組不同的起始點進行選區劃分，結果都十分良好。我們將中選會公佈之劃分法與這四組結果進行比較，中選會的劃分方式在行政區分割數上比我們的結果好，但在人口誤差與形狀上都不及我們的劃分方式優異。另外我們也選取行政中心為起始點進行劃分並將結果與中選會的結果比較，也獲得相同的結論。至於選情預估方面，我們也證實了不同的選區劃分方式的確將造成選舉結果之改變。 / Traditionally, electoral redistricting was done manually which was time consumming, inefficient, and hard to maintain fairness. One of the most famous biased electoral redistricting in human history was proposed by Elbridge Gerry in 1812, socalled the Gerrymandering districting. After that, fairness and objectivity are required in every electoral redistricting and, hence, come to the era of automatic redistricting. We have proposed a series of automatic electoral redistricting mechanisms that were emphasized on producing huge amount of feasible solutions and selecting the right solutions from them. However, we did not consider avoiding over partitioning a county in the proposed mechanisms. In this thesis, we developed a new mechanism for electoral redistricting which not only avoiding the over partitioning problem but also start the redistricting by chosing a better set of seeds. Using a set of better seeds, we can get a better set of initial electoral districts through the help of centroidal Voronoi diagram. Then, we adjust the population in every district followed by reducing the partitioning number of each county. Since adjusting the county partitioning number may violate the population requirement of the districts, we shall check the population requirement of all the districts again before checking compactness of all the districts. Finally, we applied the county partitioning number reduction process once more to reduce the partitioning number as many as we can. In the experiments, we used Taipei city to verify our mechanism. Four set of seeds were used to generate different redistricting solutions. We compared our results with the result announced by the Central Election Commission (CEC) and found that CEC’s results has better average county partitioning number but worse population error as well as worse compactness. We also used the administrative districts’ center as the seeds to generate the fifth redistricting solutions and obtained the same conclusion, i. e., CEC’s results has better average county partitioning number but worse population error as well as worse compactness. We also demonstrated that different redistricting results may change the election outcomes.

In this thesis, we study the Euclidean Steiner tree problem (ESTP) which arises in the field of combinatorial optimization. The ESTP asks for a network of minimal total edge length spanning a set of given terminal points in Rd with the ability to add auxiliary connecting points (Steiner points) to decrease the overall length of the network. The graph theory literature contains extensive studies of exact, approximation, and heuristic algorithms for ESTP in the plane, but less is known in higher dimensions. The contributions of this thesis include a heuristic algorithm and enhancements to an exact algorithm for solving the ESTP. We present a local search heuristic for the ESTP in Rd for d ≥ 2. The algorithm utilizes the Delaunay triangulation to generate candidate Steiner points for insertion, the minimum spanning tree to create a network on the inserted points, and second order cone programming to optimize the locations of Steiner points. Unlike other ESTP heuristics relying on the Delaunay triangulation, the algorithm inserts Steiner points probabilistically into Delaunay triangles to achieve different subtrees on subsets of terminal points. The algorithm extends effectively into higher dimensions, and we present computational results on benchmark test problems in Rd for 2 ≤ d ≤ 5. We develop new geometric conditions derived from properties of Steiner trees which bound below the number of Steiner points on paths between terminals in the Steiner minimal tree. We describe conditions for trees with a Steiner topology and show how these conditions relate to the Voronoi diagram. We describe more restrictive conditions for trees with a full Steiner topology and their implementation into the algorithm of Smith (1992). We present computational results on benchmark test problems in Rd for 2 ≤ d ≤ 5.

The objective of this thesis is to design a mobile positioning system on the premise that low system complexity and less modification of components of Mobile Communication System to improve the possibility that adopted by service provider. Therefore we propose a Mobile Service Positioning System for Cellular Mobile Communication System. It works based on location information of base station and mutual relations of signal strength of base stations received by mobile phone. We adjust the environment factor upon different path loss caused by different geographical feature. And then we perform EWVD Algorithm to estimate the area where mobile phone locates in. Eventually, we obtain a Mobile Positioning System which has properties: lower building cost, smaller locating area, and faster response time.

This diploma project is focused on possible applications of computational geometry methods for robot motion planning among static and dynamic obstacles, particularly based on global robot motion planning by means of generalised Voronoi diagrams. The main effort was to convert this complex geometric and analytic problem to graph theory environment where the tasks of planning and searching paths between pairs of the graph vertices are effeciently solvable. The Voronoi diagram is created considering the whole searching space, while edges of this diagram satisfy that the distance from the surrounding obstacles is maximised and the path found along the Voronoi diagram edges is optimised from the point of view of its security (and it is collision-free).

No description available.

No description available.

With many robots now being developed for indoor settings, an autonomous mobile robot should be capable of reaching multiple targets within a dense, complex environment while maintaining the optimal path taken and avoiding all obstacles. In this thesis, we propose a global path planning algorithm that uses data created from a Generalized Voronoi Diagram (GVD) to traverse complex environments. The global route is made from the skeleton of the diagram that ensures the avoidance of static obstacles. Once this route is determined, dynamic programming is used to determine the optimal route to reach each target location while safely navigating obstacles in the map. A Dynamic Window Approach (DWA) local path planner is integrated into the algorithm to provide collision-free navigation in case of unexpected or dynamic obstacles that may be encountered during traversal. Our comprehensive simulations and comparative analyses highlight the proposed model’s robustness, demonstrating its ability to efficiently navigate to multiple targets through the shortest routes while adeptly circumventing obstacles. These findings validate the model’s effectiveness, confirming its superior performance in complex multi-target navigation scenarios and its capability to dynamically adapt to unforeseen obstacles, thereby illustrating a significant advancement in the field of autonomous indoor navigation.

Selon la méthode utilisée pour construire un modèle structural en trois dimensions et selon l'application à laquelle il est destiné, son maillage, en d'autres termes sa représentation informatique, doit être adapté afin de respecter des critères de type, de nombre et de qualité de ses éléments. Les méthodes de maillage développées dans d'autres domaines que la géomodélisation ne permettent pas de modifier le modèle d'entrée. Ceci est souhaitable en géomodélisation afin de mieux contrôler le nombre d'éléments du maillage et leur qualité. L'objectif de cette thèse est de développer des méthodes de maillage permettant de remplir ces objectifs afin de gérer la complexité géométrique des modèles structuraux définis par frontières. Premièrement, une analyse des sources de complexité géométrique dans ces modèles est proposée. Les mesures développées constituent une première étape dans la définition d'outils permettant la comparaison objective de différents modèles et aident à caractériser précisément les zones plus compliquées à mailler dans un modèle. Ensuite, des méthodes originales de remaillage surfacique et de maillage volumique fondées sur l'utilisation des diagrammes de Voronoï sont proposées. Les fondements de ces deux méthodes sont identiques : (1) une optimisation de type Voronoï barycentrique est utilisée pour globalement obtenir un nombre contrôlé d’éléments de bonne qualité et (2) des considérations combinatoires permettant de construire localement le maillage final, éventuellement en modifiant le modèle initial. La méthode de remaillage surfacique est automatique et permet de simplifier un modèle à une résolution donnée. L'originalité de la méthode de maillage volumique est que les éléments générés sont de types différents. Des prismes et pyramides sont utilisés pour remplir les zones très fines du modèle, tandis que le reste du modèle est rempli avec des tétraèdres / Depending on the specific method used to build a 3D structural model, and on the exact purpose of this model, its mesh must be adapted so that it enforces criteria on element types, maximum number of elements, and mesh quality. Meshing methods developed for applications others than geomodeling forbid any modification of the input model, that may be desirable in geomodeling to better control the number of elements in the final mesh and their quality. The objective of this thesis is to develop meshing methods that fulfill this requirement to better manage the geometrical complexity of B-Rep geological structural models. An analysis of the sources of geometrical complexity in those models is first proposed. The introduced measures are a first step toward the definition of tools allowing objective comparisons of structural models and permit to characterize the model zones that are more complicated to mesh. We then introduce two original meshing methods based on Voronoi diagrams: the first for surface remeshing, the second for hybrid gridding. The key ideas of these methods are identical: (1) the use of a centroidal Voronoi optimization to have a globally controlled number of elements of good quality, and (2) combinatorial considerations to locally build the final mesh while sometimes modifying the initial model. The surface remeshing method is automatic and permits to simplify a model at a given resolution. The gridding method generates a hybrid volumetric mesh. Prisms and pyramids fill the very thin layers of the model while the remaining regions are filled with tetrahedra