Triangulation de Delaunay

En mathématiques et plus particulièrement en géométrie algorithmique, la triangulation de Delaunay d'un ensemble P de points du plan est une triangulation DT(P) telle qu'aucun point de P n'est à l'intérieur du cercle circonscrit d'un des triangles de DT(P). Les triangulations de Delaunay maximisent le plus petit angle de l'ensemble des angles des triangles, évitant ainsi les triangles « allongés ». Cette triangulation a été inventée par le mathématicien russe Boris Delaunay, dans un article publié en 1924. D'après la définition de Delaunay, le cercle circonscrit d'un triangle constitué de trois points de l'ensemble de départ est vide s'il ne contient pas d'autres sommets que les siens. Ainsi, les autres points sont autorisés sur le périmètre en lui-même mais pas à l'intérieur strict du cercle circonscrit. La condition de Delaunay affirme qu'un réseau de triangles est une triangulation de Delaunay si tous les cercles circonscrits d

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (23)

Publications associées

Chargement

Personnes associées (3)

Personnes associées

Chargement

Unités associées (2)

Unités associées

Chargement

Concepts associés (9)

Concepts associés

Chargement

Cours associés (6)

Cours associés

Chargement

Séances de cours associées (6)

Afficher plus

Séances de cours associées

Chargement

Dominating Sets in Triangulations on Surfaces

A dominating set D of a graph G is a set such that each vertex v of G is either in the set or adjacent to a vertex in the set. Matheson and Tarjan (1996) proved that any n-vertex plane triangulation has a dominating set of size at most n/3, and conjectured a bound of n/4 for n sufficiently large. King and Pelsmajer recently proved this for graphs with maximum degree at most 6. Plummer and Zha (2009) and Honjo, Kawarabayashi, and Nakamoto (2009) extended the n/3 bound to triangulations on surfaces. We prove two related results: (i) There is a constant c such that any n-vertex plane triangulation with maximum degree at most 6 has a dominating set of size at most n/6 + c. (ii) For any surface S, nonnegative t, and epsilon > 0, there exists C such that for any n-vertex triangulation on S with at most tvertices of degree other than 6, there is a dominating set of size at most n(1/6 + epsilon) + C. As part of the proof, we also show that any n-vertex triangulation of a non-orientable surface has a non-contractible cycle of length at most 2sqrt(n). Albertson and Hutchinson (1986) proved that for n-vertex triangulation of an orientable surface other than a sphere has a non-contractible cycle of length sqrt(2n), but no similar result was known for non-orientable surfaces.

2010

Chargement

Camera Tracking using natural feature point matching for Augmented Reality

Touradj Ebrahimi, Cecilia Torralbo Gimeno

For augmented reality applications, accurate estimation of the camera pose is required. An existing video-based marker tracking system developed at the ITS presents some limitations when the marker is completely or partially occluded. The objective of this project is to improve the tracking of the camera on those cases. For this purpose, the tracking of the marker is extended to that of natural feature points around the marker's environment. The extension to natural features works as follows. Feature point candidates are being searched in the image. Depth estimation is implemented in a recursive method triangulating points between the first frame and subsequent frames. A particle filter is used to take into account the new measures received with every frame. Particle's weights are sensible to the state of the camera tracker and the proximity of the triangulated point to the expected depth. Eventually the distribution of the depth particle filter for a given feature converges at one point. This position is added to a map of feature points used to update the camera pose. Results show that tracking was improved. The camera pose was tracked even though the marker was not visible. However a small drift in its pose is detected due to the imprecision of feature point positions. This drift is not excessive in the sense that the tracker is able to recover the right camera pose. Future work will focus on improving the accuracy of the depth estimates.

2007

Chargement

LiftPose3D, a deep learning-based approach for transforming two-dimensional to three-dimensional poses in laboratory animals

Marco Pietro Abrate, Pascal Fua, Adám Gosztolai, Semih Günel, Victor Lobato Rios, Daniel Eduardo Morales Garza, Pavan P Ramdya, Helge Jochen Rhodin

LiftPose3D infers three-dimensional poses from two-dimensional data or from limited three-dimensional data. The approach is illustrated for videos of behaving Drosophila, mice, rats and macaques. Markerless three-dimensional (3D) pose estimation has become an indispensable tool for kinematic studies of laboratory animals. Most current methods recover 3D poses by multi-view triangulation of deep network-based two-dimensional (2D) pose estimates. However, triangulation requires multiple synchronized cameras and elaborate calibration protocols that hinder its widespread adoption in laboratory studies. Here we describe LiftPose3D, a deep network-based method that overcomes these barriers by reconstructing 3D poses from a single 2D camera view. We illustrate LiftPose3D's versatility by applying it to multiple experimental systems using flies, mice, rats and macaques, and in circumstances where 3D triangulation is impractical or impossible. Our framework achieves accurate lifting for stereotypical and nonstereotypical behaviors from different camera angles. Thus, LiftPose3D permits high-quality 3D pose estimation in the absence of complex camera arrays and tedious calibration procedures and despite occluded body parts in freely behaving animals.

NATURE PORTFOLIO2021

Chargement

Enveloppe convexe

L'enveloppe convexe d'un objet ou d'un regroupement d'objets géométriques est l'ensemble convexe le plus petit parmi ceux qui le contiennent. Dans un plan, l'enveloppe convexe peut être comparée à

Géométrie algorithmique

vignette|Rendu d'un cylindre à l'aide d'un programme d'ordinateur. La géométrie algorithmique est le domaine de l'algorithmique qui traite des algorithmes manipulant des concepts géométriques.

Mesh generation

Mesh generation is the practice of creating a mesh, a subdivision of a continuous geometric space into discrete geometric and topological cells. Often these cells form a simplicial complex. Usually

MATH-410: Riemann surfaces

This course is an introduction to the theory of Riemann surfaces. Riemann surfaces naturally appear is mathematics in many different ways: as a result of analytic continuation, as quotients of complex domains under discontinuous group actions, as algebraic curves.

ENV-342: Geographic information system (GIS)

Acquisition de concepts et compétences de base liées à la représentation numérique des données géographiques et à leur insertion dans des SIG. Apprentissage de processus d'analyse spatiale pour les ingénieurs SIE et GC (autocorrélation spatiale, interpolation, modèles numériques d'altitude).

ME-474: Numerical flow simulation

This course provides practical experience in the numerical simulation of fluid flows. Numerical methods are presented in the framework of the finite volume method. A simple solver is developed with Matlab, and a commercial software is used for more complex problems.