În problema determinării intersecției unei drepte cu un poliedru are aplicații importante în grafica digitală, optimizare și chiar în unele dintre . Poate fi privită ca o versiune tridimensională a problemei .
Dacă poliedrul este dat ca intersecție a unui număr finit de semispații, atunci se pot clasifica semispațiile în trei submulțimi: cele care cuprind doar unul din capetele infinite ale dreptei, cele care cuprind celălalt capăt și cele care cuprind ambele capete. Semispațiile care cuprind ambele capete trebuie să fie paralele cu dreapta dată și nu contribuie la soluție. Fiecare dintre celelalte două submulțimi (dacă nu sunt vide) contribuie cu un singur punct final la intersecție, care poate fi găsit prin intersectarea dreptei cu fiecare dintre planele de frontieră ale semiplanului și alegerea punctului de intersecție cel mai apropiat de capătul dreptei conținute de semispațiile din submulțime. Această metodă, o variantă a , lucrează în timp liniar în funcție de numărul de plane ale fețelor poliedrului dat. Alternativ, prin testarea dreptei în raport cu fiecare dintre fețele poligonale ale poliedrului dat, este posibil să se oprească căutarea mai devreme atunci când se găsește o față intersectată de dreaptă.
Dacă un singur poliedru urmează să fie intersectat de mai multe drepte, este posibilă preprocesarea poliedrului într-o structură de date ierarhică, astfel încât intersecțiile cu fiecare dreaptă de interogare să poată fi determinate în timp logaritmic per interogare.
Note
Vezi și Intersecția unei drepte cu un plan
Legături externe
Intersection of convex hull with a line with pseudo code
Categorie:Geometrie euclidiană Categorie:Algebră liniară Categorie:Algoritmi de geometrie