Tester si un tétraèdre se trouve à l'intérieur d'un polyèdre

15

J'ai un tétraèdre et un polyèdre . est contraint de telle sorte qu'il partage toujours tous ses sommets avec . Je veux déterminer si se trouve à l' intérieur de .t ptpt p

Je voudrais ajouter un détail au problème au cas où il pourrait contribuer à la solution: est un tétraèdre de Delaunay et les faces de sont triangulaires et sont fortement Delaunay à la fois par rapport aux sommets de . Un tétraèdre est Delaunay si la circonscription de ses sommets ne contient aucun autre sommet à l'intérieur. Une face est fortement Delaunay s'il existe une circonscription contenant des sommets de cette face sur sa surface mais aucun autre sommet sur ou à l' intérieur .tpp

Les figures suivantes montrent le même problème dans espace : 2

Le polygone d'originep :

entrez la description de l'image ici

Triangulation de Delaunay des sommets dep :

entrez la description de l'image ici

Résultat du test intérieur / extérieur sur les triangles t (les triangles ombrés sont à l' intérieur de p et le reste est à l' extérieur ):

entrez la description de l'image ici

Résultat souhaité (élagage à l' extérieur des triangles) :

entrez la description de l'image ici


Mon problème d'origine est dans l'espace 3D, donc les triangles t dans les figures ci-dessus se traduisent par des tétraèdres et le polygone p traduit par un polyèdre arbitraire p . J'ai trouvé quelques formulations de ce problème:

Formulation 1
Les seules parties de qui peuvent être à l'extérieur de p sont ses bords et ses faces triangulaires, mais en général il peut exister un p qui a des bords de tous les t à l' extérieur sur sa surface, donc alternativement, ce problème peut également être formulé quant à tester si pour un tétraèdre t existe- t- il un visage qui se trouve en dehors de p ?tpp tt p

Formulation 2
J'ai une autre perspective possible vers ce problème mais sans idée formelle:
Géométriquement, si est à l'extérieur alors il collera toujours sur la surface externe de p . Donc, si nous pouvons calculer les contours (informellement, la frontière extérieure) C V et C V p tels que V = V tV p et V t , V p sont des ensembles de sommets en t , p respectivement, alors CtpCVCVpV=VtVpVt,Vpt,p ssitse situeintérieurp. CV=CVp tp

J'aimerais savoir:

  • Comment résoudre la formulation 1 ou la formulation 2 ?
  • Ou existe-t-il une approche complètement différente pour résoudre ce problème?

Mise à jour:
Je me rends compte maintenant que ce problème peut être réduit au problème Point dans le polyèdre . Puisqu'un tétraèdre extérieur aura au moins une face qui se trouve en dehors de p , donc tout point arbitraire sur cette face (à l'exception de ses sommets, en général) sera toujours en dehors de p . Par conséquent, pour chaque face de t , je dois prendre un point arbitraire et tester si ce point se situe en dehors de p .tp pt p

À partir d'un point dans un article sur un polygone, j'ai découvert l'algorithme de lancer de rayon et l' algorithme de nombre de bobinage . Le lancer de rayons n'est pas numériquement stable dans les cas où le point se trouve à la surface de . Mais la robustesse numérique de l'algorithme des nombres de Winding n'y a pas été abordée. p

Sur la base de ce qui précède, mon problème principal semble maintenant être (veuillez suggérer s'il devrait être posé comme une question distincte):
Existe - t-il un algorithme numériquement robuste pour le problème de point dans le polygone ?

Pranav
la source
Juste pour clarifier: 1) Le polyèdre peut-il être non convexe, et 2) si t et p partagent une face ou une arête (ou une partie de celle-ci), est-ce que cela disqualifie t d'être "à l'intérieur" de p ? (Évidemment, selon vos besoins, t et p doivent être autorisés à partager des sommets.)ptptptp
Ilmari Karonen
tptp
1
p
1
la non-convexité a la particularité que tous les sommets peuvent être à l' intérieur du polyèdre et pourtant le tétraèdre peut être à l' extérieur (puisqu'un bord n'a pas besoin de se trouver à l'intérieur dans son ensemble). Algorithme possible, voir si les arêtes (entre le polyèdre et le tétraèdre) peuvent avoir des intersections => la probabilité que le tétraèdre se trouve à l'extérieur est excellente
Nikos M.
1
Avez-vous vu l'algorithme de distance Gilbert – Johnson – Keerthi? Vous devrez d'abord décomposer le polygone / polyèdre en formes convexes (comme vous l'avez noté, un complexe simplicial ferait l'affaire). GJK est connu pour être très stable et très rapide.
Pseudonyme

Réponses:

2

J'ai récemment trouvé une solution à ce problème dans un article intitulé `` Robusting inside-outside segmentation using generalized winding numbers '' par Alec Jacobson et.al., ici . Il résout le problème de localiser si un point est à l'intérieur (ou à l'extérieur) d'un maillage polygonal arbitraire (avec auto-intersections, non multiple, à surfaces ouvertes, etc.) en utilisant la notion de nombre d'enroulement généralisé .

tp

Pranav
la source
ptpptppttp