nÃo hà / Esta dissertaÃÃo descreve quatro mÃtodos implementados para realizar uma quadrilaterizaÃÃo convexa do espaÃo bidimensional que pode conter linhas poligonais ou buracos. Dois destes mÃtodos, ponto mÃdio e ortoquad, utilizam de elementos guia, o baricentro de uma regiÃo ou o locus de cÃrculos mÃximos tangentes e internos a geometria, para produzir uma malha conforme o domÃnio. Os outros dois, triquad e quadrilaterizaÃÃo incremental, utilizam de uma triangulaÃÃo explÃcita e implÃcita combinando elementos aos pares para realizar a geraÃÃo da malha. Todas as tÃcnicas sÃo feitas por decomposiÃÃo de regiÃes o que garante uma quadrilaterizaÃÃo final, jà que o domÃnio à sempre segmentado a cada iteraÃÃo. Estas tÃcnicas sÃo comparadas por um critÃrio de geometria e topologia de forma a tornar evidentes suas vantagens e desvantagens assim como promover melhorias futuras. As tÃcnicas sÃo aplicadas a alguns exemplos, incluindo-se um reservatÃrio natural, a fim de exibir seu funcionamento em um ambiente real ou prÃximo do mesmo, conforme as amostras utilizadas. TambÃm se pretende apresentar ao longo deste trabalho os requisitos necessÃrios, segundo a experiÃncia deste autor com o tema, para o desenvolvimento de uma tÃcnica de geraÃÃo de malha quadrilateral / This work describes four methods implemented to achieve a convex quadrilaterization of the two- -dimensional space that may have polygonal lines or holes. Two of these methods, midpoint and ortoquad make use of guide elements, the centroid of a region or the locus of maximum tangent circles inside a geometry, to produce a mesh for the domain. The other two methods, triquad and incremental quadrilatezation use a implicit and explicit triangulation while combining elements in pairs to generate a mesh. All these methods are made through domain decomposition which assure quadrilaterization at the end, since the domain is always partitioned at each iteration. These techniques are compared by a criterion of geometry and topology in order to make clear its advantages and disadvantages and as means of promoting future improvements. The techniques are applied to some samples, including a natural reservoir, in order to view its operation in a real environment or near reality according to the sample used. Also it intends to present throughout this work the requirements, according to the experience with the theme of this author, to develop a technique for quadrilateral mesh generation

Orientador: Eduardo Candido Xavier / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-23T15:26:56Z (GMT). No. of bitstreams: 1 Silveira_Tiago_M.pdf: 2498154 bytes, checksum: 4bbdff83ad5a399e1c436ffdbeb89a92 (MD5) Previous issue date: 2013 / Resumo: O resumo poderá ser visualizado no texto completo da tese digital / Abstract: The complete abstract is available with the full electronic document / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Orientador: Pedro Jussieu de Rezende, Cid Carvalho de Souza / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-19T04:48:53Z (GMT). No. of bitstreams: 1 Kunigami_Guilherme_M.pdf: 3383647 bytes, checksum: 88687783446ea3564995daf2b1ecfd79 (MD5) Previous issue date: 2011 / Resumo: Nesta dissertação, realizamos um estudo extensivo de uma classe de problemas envolvendo mapas de símbolos proporcionais, através de programação linear inteira. Mapas de símbolos proporcionais são uma ferramenta cartográfica para a representação de eventos associados 'a intensidade e localização geográfica. Exemplos clássicos desses tipos de mapas são ocorrências de terremotos e populações de cidades. Devido 'a proximidade e ao tamanho dos símbolos, podem haver sobreposições entre eles. Na ocorrência dessas sobreposições, a decisão sobre quais símbolos ficarão por cima de outros, pode afetar a visibilidade dos símbolos em um desenho. Os problemas envolvendo mapas de símbolos proporcionais dos quais tratamos são restritos ao uso de círculos opacos como símbolos e consistem em decidir a ordem em que estes serão dispostos em vista das sobreposições, de forma a maximizar métricas associadas à qualidade visual desses mapas. Tratam-se, portanto, de problemas de otimização combinatória. Em nosso trabalho, apresentamos modelos de programação linear inteira para resolução de dois desses problemas, um deles foi provado pertencer à classe NP-difícil e o outro tem complexidade ainda não conhecida. Obtivemos resultados teóricos de combinatória poliédrica acerca dos modelos, o que resultou em diversas desigualdades definidoras de facetas que foram incorporadas aos modelos. Desenvolvemos ainda técnicas de pré-processamento que decompuseram as instâncias de entrada em um grande número de componentes de menor tamanho. Essas técnicas permitiram resolver de maneira ótima, pela primeira vez, diversas instâncias criadas a partir de dados reais. Ademais, descrevemos um trabalho que aborda um desses problemas através de uma heurística GRASP, ao qual também contribuímos / Abstract: In this dissertation, we present an extensive study of a class of problems involving proportional symbol maps, through integer linear programming. Proportional symbol maps are a cartographic tool to represent events associated to specified values and geographical coordinates. Classic examples of these maps include representation of earthquakes and city populations. Due to the size and proximity of the symbols, there may be overlap among them. In such case, deciding which symbols will be placed above others may result in maps with different visibility information. The problems dealing with proportional symbol maps we address restrict symbols to be opaque disks and consist of deciding the order of their placement in view of overlaps, so as to maximize metrics related to the visual quality of such maps. Therefore, these amount essentially to combinatorial optimization problems. In our work, we designed integer linear programming models to solve two of these problems, one proven to be NP-hard and the other of complexity yet unknown. We obtained theoretical results concerning these models, through polyhedral combinatorics, which allowed us to include several facet defining inequalities into these models. We also developed preprocessing techniques that successfully broke down the input instances into a large number of smaller components. These techniques lead, for the first time, to optimal solutions of several test instances created from real-world data. Furthermore, we describe work on a heuristic approach to one of these problems using GRASP, to which we also contributed / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Orientador: Cid Carvalho de Souza / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-20T15:20:18Z (GMT). No. of bitstreams: 1 Oliveira_Lucasde_M.pdf: 1308997 bytes, checksum: cc147cd3d3c9f50c61a48d83579b6c49 (MD5) Previous issue date: 2012 / Resumo: Esta dissertação tem como foco a investigação experimental de algoritmos exatos, aproximativos e heurísticos aplicados na resolução do chamado problema do corredor de comprimento mínimo (PCCM). No PCCM recebemos um polígono retilinear P e um conjunto de polígonos retilineares menores formando uma subdivisão S planar conexa de P. Uma solução para este problema, também chamada de corredor, é formada por um conjunto conexo de arestas de S, e tal que cada face interna em S possui pelo menos um ponto em sua borda que pertence a alguma aresta deste conjunto. O objetivo então é encontrar um corredor tal que a soma total dos comprimentos das arestas seja a menor possível. Trata-se de um problema NP-difícil com aplicações em áreas diversas, tais como telecomunicações, engenharia civil e projeto de circuitos VLSI. O PCCM pode ser reduzido polinomialmente a um problema em grafos denominado problema da árvore de Steiner com grupos (PASG). Considerando esta transformação, estudamos e implementamos dois métodos aproximativos, um método exato de branch-and-cut, e um método heurístico baseado na metaheurística GRASP combinada com um evolutionary path relinking (GRASP+EPR). Além disso, propomos três heurísticas de busca local que visam melhorar a qualidade de soluções do PASG. Instâncias do PCCM foram geradas aleatoriamente, nas quais aplicamos os métodos implementados. Analisamos os resultados, e apresentamos as situações onde é interessante utilizar cada método. Verificamos que o método branch-and-cut foi capaz de encontrar soluções ótimas para instâncias que julgamos ser de grande porte em tempos computacionalmente aceitáveis. O melhor algoritmo aproximativo obteve corredores que na média têm comprimento 17% maior que o comprimento ótimo. Se combinarmos este algoritmo com as heurísticas de melhoria propostas este percentual cai para a média de 3,5%. Finalmente, o GRASP+EPR consome mais tempo que este algoritmo aproximativo, entretanto, o comprimento dos corredores obtidos por ele é em média 0,9% maior que o comprimento ótimo / Abstract: This dissertation focuses on the experimental investigation of exact, approximation and heuristic algorithms applied to solve the so-called minimum length corridor problem (MLCP). In the MLCP we receive a rectilinear polygon P and a set of minor rectilinear polygons forming a connected planar subdivision S of P. A solution for this problem, also called corridor, is formed by a set of connected edges of S, and such that each inner face of S has at least one point on its your border which belongs to an edge in this set. The goal is to find a corridor such that the sum of lengths of the edges is as small as possible. This is an NP-hard problem with applications in several areas such as telecommunications, civil engineering and design of VLSI circuits. The MLCP can be polynomially reduced to a graph problem known as group Steiner tree problem (GSTP). Based on this transformation, we studied and implemented two approximation methods, an exact branch-and-cut method, and a heuristic method based on the metaheuristic GRASP combined with an evolutionary path relinking (GRASP+EPR). Furthermore, we propose three local search heuristics to improve the quality of GSTP solutions. MLCP instances were randomly generated, in which we apply the methods implemented. We analyzed the results, and present situations where it is interesting to use each method. We found that the branch-and-cut has been able to find optimal solutions for instances that we consider to be large in acceptable computational times. The best approximation algorithm obtained corridors having average length 17% higher than the optimum length. If we combine this algorithm with the improvement heuristics proposed this percentage drops to an average of 3.5%. Finally, the GRASP+EPR spent more time than this approximation algorithm, however, the length of the corridors obtained by the method is, on average, 0.9% higher than the optimum length / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Neste trabalho estudamos problemas relacionados com a busca de pontos e segmentos em janelas retangulares com os lados paralelos aos eixos. É dado um conjunto de segmentos (ou pontos) no plano. Em uma primeira fase estes segmentos são organizados em estruturas de dados de tal forma a tornar buscas por aqueles que estão contidos em janelas retangulares mais eficiente. Na segunda fase são dadas as janelas de maneira online. Várias destas estruturas de dados são baseadas em árvores balanceadas, tais como, árvore limite, árvore de busca com prioridade, árvore de intervalos e árvore de segmentos. Na dissertação mostramos detalhadamente estas estruturas de dados e os algoritmos para resolver este problema para conjuntos de pontos (versão unidimensional do problema) e para segmentos no plano, tanto horizontais e verticais como com qualquer orientação (sem cruzamentos). Os algoritmos são analisados de forma rigorosa quanto ao seu uso de espaço e de tempo. Implementamos também os vários algoritmos estudados, construindo uma biblioteca destas estruturas de dados. Apresentamos, finalmente os resultados de experimentos computacionais com instâncias do problema. / In this work we study problems about point and segment query in rectangular windows whose edges are parallel to the axis. Given a set of segments (or points) in the plane. In a first phase these segments are organized in data structures such that queries for segments in windows are done more efficiently. In the second phase windows are given online. The data structures are balanced trees as range tree, priority search tree, interval tree and segment tree. In this master\'s thesis we show in details data structures and algorithms for solving windowing queries to sets of points (unidimensional version of the problem) and of segments in the plane, as horizontal and vertical as any orientation (without crossings). The algorithms are analysed rigorously regarding their space and time used. We implement the algorithms studied, building a library of these data structures. Finally, we present, the results of computational experiments with instances of the problem.

CoordenaÃÃo de AperfeiÃoamento de NÃvel Superior / Este trabalho descreve uma tÃcnica de decomposiÃÃo de domÃnios bidimensionais para geraÃÃo em paralelo de malhas. Esta tÃcnica funciona tanto para memÃria distribuÃda quanto compartilhada, alÃm de permitir que se utilize qualquer estrutura de dados que gere regiÃes quadrangulares paralelas aos eixos para decompor o domÃnio dado como entrada. Pode se utilizar por exemplo, uma Ãrvore quaternÃria (quadtree) ou uma partiÃÃo binÃria do espaÃo (bsp). AlÃm disso, qualquer processo de geraÃÃo de malha que respeite os prÃ-requisitos estabelecidos pode ser empregado nos subdomÃnios criados, como as tÃcnicas de Delaunay ou AvanÃo de Fronteira, dentre outras. A tÃcnica proposta à dita a priori porque a malha de interface entre os subdomÃnios à gerada antes das suas malhas internas. A estimativa de carga de processamento associada a cada subdomÃnio à feita nesse trabalho com a ajuda de uma quadtree refinada, cujo nÃvel de refinamento orienta a criaÃÃo das arestas que sÃo definidas a partir da discretizaÃÃo das fronteiras das cÃlulas internas. Essa maneira de estimar carga produz resultados que representam, com boa precisÃo, o nÃmero de elementos a serem gerados em cada subdomÃnio. Isso contribui para um bom particionamento do domÃnio, fazendo com que a geraÃÃo de malha em paralelo seja significativamente mais rÃpida do que a geraÃÃo serial. AlÃm disso, a qualidade da malha gerada em paralelo à qualitativamente equivalente Ãquela gerada serialmente, dentro de limites aceitÃveis. / This work describes a technique of two-dimensional domain decomposition for parallel mesh generation. This technique works for both distributed and shared memory and has the freedom to use any data structure that manages rectangular regions parallel to the axes to decompose the domain given as input, such as a quaternary tree (quadtree) or a binary space decomposition (bsp), for example. Any process of mesh generation that respects the prerequisites established can be used in the subdomains created, for instance, Delaunay or Advancing Front, among others. This technique is called a priori because the mesh on the interface of the subdomains is generated prior to the their internal meshes. The load estimation for each sub-domain in this work is performed with the aid of a refined quadtree, whose level of refinement guides the creation of edges that are defined from the bounderies of only inner cells. This way of estimate load produces results that accurately represent the number of elements to be generated in each subdomain. That contributes to a good partitioning of the domain, making the mesh generation in parallel be significantly faster than the serial generation. Furthermore, the quality of the generated mesh in parallel is qualitatively equivalent to that generated serially within acceptable limits.

Aquesta tesi tracta del disseny, implementació i discussió d'algoritmes per resoldre problemes de visibilitat i bona-visibilitat utilitzant el hardware gràfic de l'ordinador. Concretament, s'obté una discretització dels mapes de multi-visibilitat i bona-visibilitat a partir d'un conjunt d'objectes de visió i un conjunt d'obstacles. Aquests algoritmes són útils tant per fer càlculs en dues dimensions com en tres dimensions. Fins i tot ens permeten calcular-los sobre terrenys. / In this thesis we design, implement and discuss algorithms that run in the graphics hardware for solving visibility and good-visibility problems. In particular, we compute a discretization of the multi-visibility and good-visibility maps from a set of view objects (points or segments) and a set of obstacles. This computation is carried out for two-dimensional and three-dimensional spaces and even over terrains, which in computational geometry are defined as a 2.5D space.

TEIXEIRA, Daniel Nascimento. Uma técnica de decomposição a priori para geração paralela de malhas bidimensionais. 2014. 94 f. : Dissertação (mestrado) - Universidade Federal do Ceará, Centro de Ciências, Departamento de Computação, Fortaleza-CE, 2014. / Submitted by guaracy araujo (guaraa3355@gmail.com) on 2016-06-15T19:57:36Z No. of bitstreams: 1 2014_dis_dnteixeira.pdf: 17919971 bytes, checksum: 092ad12b33cf64a31552e6a839a5a5bc (MD5) / Approved for entry into archive by guaracy araujo (guaraa3355@gmail.com) on 2016-06-15T19:58:41Z (GMT) No. of bitstreams: 1 2014_dis_dnteixeira.pdf: 17919971 bytes, checksum: 092ad12b33cf64a31552e6a839a5a5bc (MD5) / Made available in DSpace on 2016-06-15T19:58:41Z (GMT). No. of bitstreams: 1 2014_dis_dnteixeira.pdf: 17919971 bytes, checksum: 092ad12b33cf64a31552e6a839a5a5bc (MD5) Previous issue date: 2014 / This work describes a technique of two-dimensional domain decomposition for parallel mesh generation. This technique works for both distributed and shared memory and has the freedom to use any data structure that manages rectangular regions parallel to the axes to decompose the domain given as input, such as a quaternary tree (quadtree) or a binary space decomposition (bsp), for example. Any process of mesh generation that respects the prerequisites established can be used in the subdomains created, for instance, Delaunay or Advancing Front, among others. This technique is called a priori because the mesh on the interface of the subdomains is generated prior to the their internal meshes. The load estimation for each sub-domain in this work is performed with the aid of a refined quadtree, whose level of refinement guides the creation of edges that are defined from the bounderies of only inner cells. This way of estimate load produces results that accurately represent the number of elements to be generated in each subdomain. That contributes to a good partitioning of the domain, making the mesh generation in parallel be significantly faster than the serial generation. Furthermore, the quality of the generated mesh in parallel is qualitatively equivalent to that generated serially within acceptable limits. / Este trabalho descreve uma técnica de decomposição de domínios bidimensionais para geração em paralelo de malhas. Esta técnica funciona tanto para memória distribuída quanto compartilhada, além de permitir que se utilize qualquer estrutura de dados que gere regiões quadrangulares paralelas aos eixos para decompor o domínio dado como entrada. Pode se utilizar por exemplo, uma árvore quaternária (quadtree) ou uma partição binária do espaço (bsp). Além disso, qualquer processo de geração de malha que respeite os pré-requisitos estabelecidos pode ser empregado nos subdomínios criados, como as técnicas de Delaunay ou Avanço de Fronteira, dentre outras. A técnica proposta é dita a priori porque a malha de interface entre os subdomínios é gerada antes das suas malhas internas. A estimativa de carga de processamento associada a cada subdomínio é feita nesse trabalho com a ajuda de uma quadtree refinada, cujo nível de refinamento orienta a criação das arestas que são definidas a partir da discretização das fronteiras das células internas. Essa maneira de estimar carga produz resultados que representam, com boa precisão, o número de elementos a serem gerados em cada subdomínio. Isso contribui para um bom particionamento do domínio, fazendo com que a geração de malha em paralelo seja significativamente mais rápida do que a geração serial. Além disso, a qualidade da malha gerada em paralelo é qualitativamente equivalente àquela gerada serialmente, dentro de limites aceitáveis.

[pt] Este trabalho surgiu da seguinte observação: os clássicos algoritmos de busca em 2d-tree começam da raiz para acessar dados armazenados nas folhas. Entretanto, como as folhas são os nós mais distantes da raiz, por que começar as buscas pela raiz? Com representações clássicas de 2d-trees, não existe outra forma de acessar uma folha. Existem 2d- trees, porém, que permitem acessar em tempo constante qualquer nó, dado sua posição e seu nível. Para o algoritmo de busca, a posição é conhecida, mas o nível não. Para estimar o nível de um nó qualquer, um método de otimização estatística do custo médio das buscas é proposto. Como os piores custos de busca são obtidos quando se começa da raiz, este método melhora ambos: o consumo de memória pelo uso de 2d-trees que permitem acessar em tempo constante qualquer nó, e o tempo de execução através da otimização proposta. / [en] This work emerged from the following observation: usual search procedures for 2d-trees start from the root to retrieve the data stored at the leaves. But since the leaves are the farthest nodes to the root, why start from the root? With usual 2d-trees representations, there is no other way to access a leaf. However, there exist 2d-trees which allow accessing any node in constant time, given its position in space and its depth in the 2d-tree. Search procedures take the position as an input, but the depth remains unknown. To estimate the depth of an arbitrary node a statistical optimization of the average cost for the search procedures is introduced. Since the highest costs of these algorithms are obtained when starting from the root, this method improves on both, the memory footprint by the use of 2d-trees which allow accessing any node in constant time, and execution time through the proposed optimization.

Submitted by Renata Lopes (renatasil82@gmail.com) on 2017-03-02T14:44:36Z No. of bitstreams: 1 rogercorreiapinheirosilva.pdf: 22838442 bytes, checksum: 0bd115f462fc7572058a542e9ed91fcc (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2017-03-06T19:52:42Z (GMT) No. of bitstreams: 1 rogercorreiapinheirosilva.pdf: 22838442 bytes, checksum: 0bd115f462fc7572058a542e9ed91fcc (MD5) / Made available in DSpace on 2017-03-06T19:52:42Z (GMT). No. of bitstreams: 1 rogercorreiapinheirosilva.pdf: 22838442 bytes, checksum: 0bd115f462fc7572058a542e9ed91fcc (MD5) Previous issue date: 2011-08-26 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Um sistema câmera-projetor é capaz de capturar informação geométrica tridimensional de objetos e ambientes do mundo real. A captura de geometria em tal sistema baseia-se na projeção de luz estruturada sobre um objeto através do projetor, e na captura da cena modulada através da câmera. Com o sistema previamente calibrado, a deformação da luz projetada causada pelo objeto fornece a informação necessária para reconstruir a geometria do mesmo por meio de triangulação. Este trabalho descreve o desenvolvimento de um digitalizador câmera-projetor de alta definição (com resoluções de até 1920x1080 e 1280x720); são detalhadas as etapas e processos que conduzem à reconstrução de geometria, como calibração câmera-projetor, calibração de cores, processamento da imagem capturada e triangulação. O digitalizador desenvolvido utiliza a codificação de luz estruturada (b; s)-BCSL, que emprega a projeção de uma sequência de faixas verticais coloridas sobre a cena. Este esquema de codificação flexível oferece um número variado de faixas para projeção: quanto maior o número de faixas, mais detalhada a geometria capturada. Um dos objetivos deste trabalho é estimar o número limite de faixas (b,s)-BCSL possível dentro das resoluções atuais de vídeo de alta definição. Este número limite é aquele que provê reconstrução densa da geometria alvo, e ao mesmo tempo possui baixo nível de erro. Para avaliar a geometria reconstruída pelo digitalizador para os diversos números de faixas, é proposto um protocolo para avaliação de erro. O protocolo desenvolvido utiliza planos como objetos para mensurar a qualidade de reconstrução geométrica. A partir da nuvem de pontos gerada pelo digitalizador, a equação do plano para a mesma é estimada por meio de mínimos quadrados. Para um número fixo de faixas, são feitas cinco digitalizações independentes do plano: cada digitalização leva a uma equação; também é computado o plano médio, estimado a partir da união das cinco nuvens de pontos. Uma métrica de distância no espaço projetivo é usada para avaliar a precisão e a acurácia de cada número de faixas projetados. Além da avaliação quantitativa, a geometria de vários objetos é apresentada para uma avaliação qualitativa. Os resultados demonstram que a quantidade de faixas limite para vídeos de alta resolução permite uma grande densidade de pontos mesmo em superfícies com alta variação de cores. / A camera-projector system is capable of capturing three-dimensional geometric information of objects and real-world environments. The capture of geometry in such system is based on the projection of structured light over an object by the projector, and the capture of the modulated scene through the camera. With a calibrated system, the deformation of the projected light caused by the object provides the information needed to reconstruct its geometry through triangulation. The present work describes the development of a high definition camera-projector system (with resolutions up to 1920x1080 and 1280x720). The steps and processes that lead to the reconstruction of geometry, such as camera-projector calibration, color calibration, image processing and triangulation, are detailed. The developed scanner uses the (b; s)-BCSL structured light coding, which employs the projection of a sequence of colored vertical stripes on the scene. This coding scheme offers a flexible number of stripes for projection: the higher the number of stripes, more detailed is the captured geometry. One of the objectives of this work is to estimate the limit number of (b; s)-BCSL stripes possible within the current resolutions of high definition video. This limit number is the one that provides dense geometry reconstruction, and at the same has low error. To evaluate the geometry reconstructed by the scanner for a different number of stripes, we propose a protocol for error measurement. The developed protocol uses planes as objects to measure the quality of geometric reconstruction. From the point cloud generated by the scanner, the equation for the same plane is estimated by least squares. For a fixed number of stripes, five independent scans are made for the plane: each scan leads to one equation; the median plane, estimated from the union of the five clouds of points, is also computed. A distance metric in the projective space is used to evaluate the precision and the accuracy of each number of projected stripes. In addition to the quantitative evaluation, the geometry of many objects are presented for qualitative evaluation. The results show that the limit number of stripes for high resolution video allows high density of points even on surfaces with high color variation.