Bonjour,
 
J'aimerai savoir quel est le moyen le plus rapide pour savoir si un point quelconque x se trouve à l'intérieur d'une cellule de Voronoi V(y), y étant le centre de la cellule.  Si j'ai bien compris dans une cellule de Voronoi, tout point x à l'intérieur à l'intérieur de V(y) comme plus proche voisin y.
 
Le seul moyen que j'ai trouvé c'est :  
 
 - Pour x,  
            Pour tous les voisins yv_i de y,  calculer la distance d (x,vy_i),  (i=1 ... nombre de voisins de y)
            Prendre la plus petite des distance d (x,vy_i), je l'appelle d_min_xvy
            Regarder si d_min_xvy < d(x,y) ? Si oui x n'est pas dans la cellule, sinon il l'est.
 
 
Y'a t'il plus rapide ....?? Peut on savoir si le point est à l'intérieur de manière géométrique ??? car a chaque fois je dois parcourir tous les x, car je teste sur plein de x pour savoir s'il sont dans la cellule    
 
merci bien par avance !            

Bonjour,
je ne sais pas si ça va t'aider mais bien souvent, une région de Voronoi est décrite comme l'intersection de demi-espaces (en 3D) ou bien de demi-plans (en 2D), chacun d'eux étant délimité par un plan (en 3D) ou bien une droite (en 2D)...  
Ensuite, établir si un point se situe dans un demi-espace (ou bien un demi-plan) est trivial... tu devrais chercher autour de ça.

 
salut,
 
Merci pour votre réponse, je travaille en 2D ... comment est défini un demi-plan ?  

c'est tout ce qui est sur un côté de la droite non ?
 
c'est à dire que :
 
y >= ax + b ou y <= ax + b selon le côté de la droite que tu veux
 
si tu as beaucoup de point à vérifier, avant de lancer un test sur des formules relativement complexes de ce genre, tu peux déjà faire ce qu'on appelle une "bounding box" en 3D (dans ton cas, un carré) et isoler dans un premier temps les points présents entre x1 et x2 / y1 et y2, x1 correspondant au point le plus à gauche de ta cellule, x2 le point le plus à droite, y1 le point le plus en haut et y2 le point le plus en bas.
 
ça te fait faire des calculs supplémentaires pour déterminer x1, x2, y1, y2, mais ensuite tu pourras déterminer quels points sont candidats au test de la présence dans la cellule de façon plus rapide afin d'écarter un maximum de points avant de lancer les calculs plus complexes.

En gros, je sais pas trop ce que veut dire Voronoi et Delaunay. Mais si j'ai bien pigé :
- Tu as une "cellule" avec un centre
- Et celle cellule est représentée par l'intersection de 3 ou plus demi-plans
 
Donc dans une première passe, afin de déterminer les valeurs x1, x2, y1 et y2, tu recherches les intersections de toutes tes droites définissant les demi-plans.
Pour chaque point d'intersection, tu vérifies qu'il est présent dans ta cellule.
Pour tous les points d'intersection effectivement dans la cellule, tu récupère les valeurs min et max de leurs coordonnées.
=> Tu auras alors ta bounding box.
 
Pour tous tes points, tu peux alors vérifier que x1 <= x <= x2 et y1 <= y <= y2
=> Les points qui ne répondent pas à ces 4 conditions ne peuvent en aucun cas être présents dans ta cellule.
 
Ensuite, tu vérifies pour chacun des points restant s'il est dans la cellule (il doit répondre à toutes les fonctions définissant tes demi-points)
Pour ceux qui sont dans la cellule, tu conserves uniquement celui qui est le plus proche du centre.
 
Si j'ai bien compris ton problème, cet algo devrait fonctionner et rester "relativement" performant (il y a certainement mieux)

pour ce qui est la représentation d'un demi-plan, tu dois pouvoir le caractériser par les coefficients A,B et C d'une inéquation de la forme  
A.x + B.y + C > 0.
Cette évalution est très rapide pour un nombre de demi-plans par cellule "petit"... Comme le propose MagicBuzz, pour les cellules composées d'un grand nombre de demi-plans (>10 ou 20), tu peux envisager une "phase d'évaluation grossière" à base de rectangles englobants.
Pour ce qui est du calcul des coefficients A, B et C à partir des coordonnées d'un segment délimitant le demi-plan, tu peux par exemple revenir à la définition d'un demi-plan par le produit scalaire...

Par définition (si mes souvenirs sont bons), tu peux avoir plusieurs approches:
- géométrique: un point x appartient à une cellule de centre y si la distance (x,y) est la plus faible (comparée à tous les centres de toutes les autres cellules)
- graphe: le diagramme de Voronoï est un graphe régulier d'ordre 3 car chaque sommet du diagramme possède exactement 3 voisins (éventuellement rejetés à l'infini dans le cas des bords de l'image).
Soit G un ensemble de points (appellés germes). Pour chaque point P de G, la région polygonale composée de points plus proches du germe P que de tous les autres germes est appellée polygone de Voronoï et notée V(P) (c'est ce qu'on appelle aussi cellule).
Tout sommet du diagramme de Voronoï plus proche du germe P dans l'ensemble G appartient à une arrête du polygone V(P).
 
Tu peux ainsi représenter ton diagramme avec une liste d'arrêtes. Chaque arrête est représentée par ses 2 extrèmités, l'étiquette du germe voisin, l'arrête suivante et l'arrête précédente (définies par exemple suivant un parcours dans le sens trigonométrique de la frontière).
 
Donc avec une approche en distance par rapport aux "centres de cellules" avec une représentation comme ça, ça devrait te permettre de tester assez rapidement l'appartenance de tes points.

salut,
 
merci pour ta réponse, je vais essayer le coup de la BoundingBox, je pense que ca peut éliminer pas mal de tests inutiles Sinon pour la triangulation de Delaunay, c'est l'unique triangulation tel qu'un cercle circonscrit à un triangle ne contienne aucun autre point. Le diagramme de voronoi est le graphe dual de la triangulation de delaunay. Y'a un applet pas mal pour se rendre compte stv : http://www.pi6.fernuni-hagen.de/GeomLab/VoroGlide/
 
merci encore  

Je crois que j'ai trouvé un autre technique, mais je sais pas si ca prendra moins de temps que ma première technique :
 
je regarde si mon point x est du meme coté que y (le centre de la cellule V(y) ) par rapport à la droité définie par les deux point d'un bord de la cellule V(y). Je fais ca pour tous les bords, et si x est du même côté pour tous les bords ca veut dire qu'il est dans ma cellule...mais je sais pas si ca prendra plus ou moins de temps que de calculer des distances et de les comparer ??

C'est exactement ce que nous t'avons proposé depuis le début... et oui, ce sera plus rapide...
 
EDIT : Ce que tu appelles "regarder si le point est du même côté (par rapport à une droite) que le centre de ta cellule", c'est regarder s'il est dans le demi-plan délimité par ta droite et contenant le centre. Ce que tu appelles "faire ça pour tous les bords", c'est ce qu'on appelle une intersection (d'un point de vue ensembliste)... Note que bien souvent, quand le point n'est pas dans la cellule, tu peux conclure sans tester tous les bords...

tiens, oui (mon algo reste bon, avec les bounding box) j'ai pas bien pigé l'histoire de la distance. c'était pour faire quoi ? mon algo est à priori bon jusqu'au moment où je parle de distances.
 
(en fait, j'avais cru comprendre que tu cherchais parmi les points présents dans ta cellule, celui qui était le plus prochedu centre, d'où mes étapes supplémentaires

 
oui c'est vrai c'est ce que tu m'avais proposé, j'avais pas fait le lien jusqu'a ce que je retombe dessus    
 
C'est vrai que ca devrait être plus rapide car, à moins d'etre dans le pire des cas, je ne serais pas obligé de faire ca sur tous les bords ! youpi !!  
 
MagicBuzz : oui mais ton algo m'aide qd meme
 
merki  

tiens, juste comme ça...
 
j'ai vraiment la tête creuse par moment, je me fait peur...
 
j'ai 3 points représentant un triangle (A, B, C)
j'ai 1 point : je veux savoir s'il est dans mon triangle (P)
 
niveau algo, y'en a plusieurs, dont un des plus rapides, c'est de savoir si :
A et P sont du même côté de BC
B et P sont du même côté de AC
C et P sont du même côté de BC
=> Le truc à la base, tout bête et simple (surtout, rapide)
 
Sauf que /me is a quiche lorraine sans lardons, et du coup je sais même plus comment je détermine de quel côté d'une droite se trouve un point...
 
http://www.blackpawn.com/texts/poi [...] fault.html
=> supaire, mais "crossproduct" je sèche, et "dotpoint" là c'est même pas la peine
 
 
/me n'a rien dit (mais poste quand même )
 
Avec ce petit exemple en JS ça devrait le faire

Déjà, plutôt que de chercher si P est du même côté que A par rapport à (BC), tu devrais supposer que tes triangles sont tous bien orientés (sens horaire ou trigo, mais faut s'y tenir, ensuite !)...  
Une fois le "sens du triangle" connu, le signe d'un déterminant bien choisi devrait te permettre de conclure à propos de la position de P par rapport à (BC) sans te soucier de A...
A l'époque, pour trouver la solution, j'étais revenu à la définition du produit vectoriel...

=> En fait, j'ai mis en place ce truc hier et ça marchait parfaitement et à 10% comme je voulais.
 
En gros, c'était pour faire "un oeil". L'ouverture de ce dernier est petit (pi/8) donc l'aire de vision est assimilable à un triangle (en partant du principe que le champ de vision est limité en profondeur).
 
J'ai testé avec une bestiolle tournant sur elle même, et elle réagissait correctement à tout ce qui étant dans son champ de vision. Le truc que j'ai trouvé est fonc fonctionnel
 
(ps: vivi, je suis pas du tout en train de traîter le même problème qu'à l'origine, j'avais juste besoin de forumules géo et comme on en avait déjà abordé ici... )