Comment calculer l'intersection entre un polyèdre convexe et un autre polyèdre?

Question

Le problème en question fait partie d'une simulation scientifique portant sur la croissance 2D dans l'espace 3D. La forme 2D se développe en ajoutant des segments (triangulaires) à la forme précédemment développée.

Notez que les segments réels en 3D ont une épaisseur, donc, mon code fonctionne en fait avec des prismes triangulaires.

À un moment donné, ces formes 2D (quelle que soit l'orientation et la position relatives) entrent en collision.

Si l'un des nouveaux prismes triangulaires croise des segments précédemment insérés, je veux seulement insérer la "partie" d'un segment qui ne recoupe pas les segments précédemment insérés. Comme indiqué ci-dessous pour les segments étiquetés T1 et T2.

Dans la première étape, je calcule toutes les intersections des bords de faces. J'ai ensuite utilisé le package CGAL Delaunay Triangulation en 3D pour mailler l'ensemble de points résultant dans un maillage tétraédrique. En dernier lieu, je rejette tous ces tétraèdres qui se croisent avec des segments précédemment insérés. Cela fonctionne magnifiquement dans la plupart des cas - mais je suis convaincu maintenant que l'idée ne peut pas fonctionner pour des raisons fondamentales.

Quel est un moyen plus fiable de calculer cela?

Answer 1

Alors vous cherchez à trouver l'intersection de 2 coques convexes?

Je pense que vous avez raison de dire que votre approche ne fonctionnera pas dans tous les cas, mais seulement dans certains cas dégénérés. Par exemple, si une coque convexe est entièrement à l'intérieur de l'autre, il n'y a pas d'intersections face/bord. Une approche plus évidente est de commencer avec une coque convexe assez grande pour entourer les deux coques (représentant ainsi tout l'espace), puis pour chaque avion dans vos deux coques convexes partitionner cette coque par ce plan, jeter la partie sur le "dehors".

Le résultat sera l'intersection - qui peut être rien.