Discussion :

[mangeclous]

Bonjour,

J'aimerai savoir si étant donné un ensemble de points définis par une fonction caractérisque
f: R^3 -> {0,1}

A = {x| f(x)=1}
si il est possible de faire un algo qui détermine si un point appartient à l'enveloppe convexe de A?
Le cas où la liste des points est connue a déjà été fait par différent algo.

Thanks.

[Aleph69]

Bonjour,

oui bien sûr que c'est possible mais il faut faire attention aux erreurs d'arrondis en virgule flottante. Tu vas devoir introduire une tolérance pour dire qu'un point appartient ou pas à l'enveloppe convexe. Le principe consiste à généraliser la notion de coordonnées barycentriques aux ensembles convexes : les points situés sur l'enveloppe convexe sont caractérisés par (i) une seule coordonnée non nulle et (ii) cette coordonnée est comprise entre 0 et 1. Je crois me souvenir (mais ça fait longtemps je peux me tromper) que dans l'algorithme de triangulation de Delaunay, les points de l'enveloppe convexe sont déterminés en calculant des déterminants et en obervant leur signe. Cela revient en fait à regarder si un point se trouve à gauche ou à droite d'une droite (signe + ou - pour le déterminant) : lorsque le déterminant vaut zéro, le point appartient au segment. L'idée se généralise assez bien mais je te dirais sûrement des bêtises si j'essayais de t'expliquer comment. Par contre, une chose dont je suis sûr et certain, c'est que l'algorithme est donné dans le bouquin de O'Rourke "Computational Geometry in C".