Discussion :

[Mucho]

Salut, salut,

est-ce que qulqu'un connaît une méthode permettant de déterminé si un point de l'espace est à l'intérieur d'un polyèdre quelconque.
( NB : J'entends par polyedre quelconque un objet 3D convexe ou concave formé de faces, convexes ou concaves, et qui ne sont pas forcement planes)

J'ai entendu parler de la méthode des demi-droites, mais elle pose problème si la demi-droite rencontre un sommet ou si elle est tangente à une face.

[ToTo13]

Bonjour,

la méthode de la demi droite fonctionne tres bien mais est extrement couteuse.
Si ton objet est convexe, tu peux projeter tout tes points sur différents plans (trois au maximum) et vérifier que le projeté de ton point est dans le projeté des points de contours. Cela est tres facile ne regardant l'alternance des angles.

[Graffito]

Bonjour,

La méthode qui consiste à compter le nombre d'intersection avec la surface des faces de la demi-droites verticale (axe Z) partant du point.
Si le nombre est impair alors le point est dans le polyédre.

Les problèmes de cette mérthode réside dans les effets de bord lorsque :

• P1) les points des angles du polyedre sont sur la droite,
  P2) la droite coupe une arete,
  P3) la droite est contenue dans une face verticale,

Si on ne désire pas une solution parfaite, on peut résoudre les différents problèmes P1, P2 et P3 en appliquant successivement les solutions S1 et S2:

• S1) on décale légérement en X les points des angles qui posent problème
  S2) on décale légerement en Y les sommets des arètes occasionnant le cas 2
  P3 est automatiquement résolu par la combinaison de S1 et S2.

PS : J'ai extrapolé la méthode de celle que j'utilise sur des polygones 2D.

[FrancisSourd]

Si tu peux définir ton "polyèdre" comme l'intersection des volumes d'équations

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
f1(x) <= 0 
f2(x) <= 0 ...

il suffira de vérifier que toutes les équations sont vérifiées.

[Mucho]

la méthode de la demi droite fonctionne tres bien mais est extrement couteuse.
Si ton objet est convexe

Le problème est que les objets ne sont pas toujours convexes, et si c'est pour une question de performances, déterminé si l'objet est convexe ou non me parait compliqué. A moins qu'il existe une méthode rapide a laquelle je n'ai pas pensé.

S1) on décale légérement en X les points des angles qui posent problème
S2) on décale légerement en Y les sommets des arètes occasionnant le cas 2
P3 est automatiquement résolu par la combinaison de S1 et S2.

Désolé je n'ai pas bien compris cette astuce de décalage leger (ie leger par rapport a quoi ?). Et n'est-t-il pas possible qu point se trouvant a l'intérieur, se retrouve a l'extérieur après le décalage et reciproquement ?

Si tu peux définir ton "polyèdre" comme l'intersection des volumes d'équations, il suffira de vérifier que toutes les équations sont vérifiées.

Oui, effectivement, mais j'ai du mal a comprendre comment décider si pour qu'une equation soit vérifiée il faut :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

f1(x) <= 0

ou bien

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

f1(x) >= 0

puisque pour decider il faut savoir reconnaitre l'intérieur et l'exterieur du solide, non ?

[FrancisSourd]

Pour plus de clarté, je me mets en dimension 3 donc le vecteur que j'appelé x est maintenant ecrit (x,y,z) où x,y et z sont des réels

Si tu sais que ton volume est délimité par la surface d'équation f(x,y,z) = 0 mais si tu ne sais pas si les points à l'intérieur du volume doivent vérifier f(x,y,z) <= ou >= 0, tu peux prendre un point qui est assurément en dehors du volume. Le point (10000,10000,10000) par exemple.
Si f(10000,10000,10000) <=0 alors les points (x,y,z) à l'intérieur de la surface doivent vérifier f(x,y,z) >= 0.

Par exemple, les équations suivantes définissent une demi-sphère:
x² + y² + z² <= 1 et z >= 0

La première inéquation dit que le point doit être dans la boule centrée en 0 et de rayon 1. La deuxième équation dit qu'on doit être dans le demi-espace au dessus du plan "horizontal".

[Graffito]

Bonjour,

Désolé je n'ai pas bien compris cette astuce de décalage leger (ie leger par rapport a quoi ?). Et n'est-t-il pas possible qu point se trouvant a l'intérieur, se retrouve a l'extérieur après le décalage et reciproquement ?

Par léger, j'entendais une valeur qui correspondait à la précision recherchée. En dehors des points situés au voisinage immédiat des faces du polyèdre (distance inférieure à la précision), on n'aura pas d'effet indésirable.