Intersezione tra due parallelepipedi nello spazio
Salve a tutti!
Mi sono bloccato su un problema che probabilmente è abbastanza banale, ma non sono risuscito a trovare una soluzione.
Ho un parallelepipedo e un cubo in uno spazio 3D entrambi "paralleli" agli assi ( non so come si dice quando tutti i lati di ogni facccia sono paralleli a uno degli assi x,y,z e cioè che i due poliedri non hanno alcuna rotazione).
Sapendo le coordinate di tutti i vertici di ognuno dei poliedri (e quindi posso definire un intervallo [min,max] per ogni coordinata) devo verificare se si intersecano o meno.
Definiamo i due poliedri come P e C.
Molto velocemente posso dire che se le coordinate di un vertice di P sono comprese nei rispettivi intervalli di C (o viceversa) allora questi si intersecano.
Ora il problema è:
Nel caso nessuno dei vertici di P è interno a C (e viceversa) come faccio a verificarlo?
Grazie mille in anticipo.
Mi sono bloccato su un problema che probabilmente è abbastanza banale, ma non sono risuscito a trovare una soluzione.
Ho un parallelepipedo e un cubo in uno spazio 3D entrambi "paralleli" agli assi ( non so come si dice quando tutti i lati di ogni facccia sono paralleli a uno degli assi x,y,z e cioè che i due poliedri non hanno alcuna rotazione).
Sapendo le coordinate di tutti i vertici di ognuno dei poliedri (e quindi posso definire un intervallo [min,max] per ogni coordinata) devo verificare se si intersecano o meno.
Definiamo i due poliedri come P e C.
Molto velocemente posso dire che se le coordinate di un vertice di P sono comprese nei rispettivi intervalli di C (o viceversa) allora questi si intersecano.
Ora il problema è:
Nel caso nessuno dei vertici di P è interno a C (e viceversa) come faccio a verificarlo?
Grazie mille in anticipo.
Risposte
Chiaramente un parallelepipedo è determinato univocamente dal dato dei suoi lati.
Siano allora $X,Y,Z$ e $x,y,z$ i lati dei due parallelepipedi $P$ e $p$: $P\cap p$ è diverso dal vuoto se e solo se tutti e tre i lati si intersecano non-nel-vuoto, cioè se (con una notazione un po' imprecisa ma chiara) \(X\cap x\neq \varnothing, Y\cap y\neq \varnothing, Z\cap z\neq \varnothing\).
E' necessario che tutti i lati si intersechino: prendi $P=p$ il cubo unitario: se trasli uno dei due cubi lungo uno degli assi (facciamo l'asse $e_3$) di un vettore di norma $>1$, i due cubi non si intersecano più.
E' sufficiente che tutti i lati si intersechino: segue dal fatto che $(X\times Y\times Z)\cap (x\times y\times z) = (X\cap x)\times (Y\cap y)\times (Z\cap z)$.
Siano allora $X,Y,Z$ e $x,y,z$ i lati dei due parallelepipedi $P$ e $p$: $P\cap p$ è diverso dal vuoto se e solo se tutti e tre i lati si intersecano non-nel-vuoto, cioè se (con una notazione un po' imprecisa ma chiara) \(X\cap x\neq \varnothing, Y\cap y\neq \varnothing, Z\cap z\neq \varnothing\).
E' necessario che tutti i lati si intersechino: prendi $P=p$ il cubo unitario: se trasli uno dei due cubi lungo uno degli assi (facciamo l'asse $e_3$) di un vettore di norma $>1$, i due cubi non si intersecano più.
E' sufficiente che tutti i lati si intersechino: segue dal fatto che $(X\times Y\times Z)\cap (x\times y\times z) = (X\cap x)\times (Y\cap y)\times (Z\cap z)$.
Detto ciò, dovrebbe essere facile scrivere un programma che verifica queste condizioni date le coordinate dei vertici di un parallelepipedo; è questo che ti serve?
Grazie per la risposta e complimenti per aver intuito che ho a che fare con la programmazione di un software di simulazione grafica in 3D.
Purtroppo il tuo ragionamento riguardo i lati non mi torna molto, in particolare cosa intendi per intersezione tra lati in uno spazio 3D?
Se il parallelepipedo p interseca P esattamente all'interno di una sua faccia quali sono i lati interessati dall' intersezione?
Ti chiedo scusa, ma mi mancano delle nozioni geometria e vorrei cercare una soluzione di tipo algoritmico.
Purtroppo il tuo ragionamento riguardo i lati non mi torna molto, in particolare cosa intendi per intersezione tra lati in uno spazio 3D?
Se il parallelepipedo p interseca P esattamente all'interno di una sua faccia quali sono i lati interessati dall' intersezione?
Ti chiedo scusa, ma mi mancano delle nozioni geometria e vorrei cercare una soluzione di tipo algoritmico.
Purtroppo il tuo ragionamento riguardo i lati non mi torna molto, in particolare cosa intendi per intersezione tra lati in uno spazio 3D?
Intendo che l'intervallo $[a,b]$ interseca $[a',b']$. Questo succede non appena $a\le a'\le b$ oppure $a\le b'\le b$, oppure entrambe queste condizioni insieme.
Ah ok perfetto! Questa mi sembra proprio la soluzione che stavo cercando, anzi a quanto pare non serve calcolare prima l' eventuale intersezione dei vertici, ma basta calcolare direttamente sui lati giusto?
Come ti ho detto, $(X\times Y\times Z)\cap (x\times y\times z) = (X\cap x)\times (Y\cap y)\times (Z\cap z)$.
Questo implica direttamente che due sottoinsiemi della forma $X\times Y\times Z,x\times y\times z$ si intersecano se e solo se ciascun lato interseca l'altro.
A questo punto è facile capire cosa dire alla macchina (in cosa devi programmare?): "per i=1,2,3 controlla che il lato $L_i$ intersechi il lato $l_i$; alla prima istanza di lato che non lo fa, fermati e dimmi che le figure sono disgiunte; altrimenti finisci il ciclo."
A seconda del linguaggio in cui scrivi puoi farlo in $10^n$ modi.
Questo implica direttamente che due sottoinsiemi della forma $X\times Y\times Z,x\times y\times z$ si intersecano se e solo se ciascun lato interseca l'altro.
A questo punto è facile capire cosa dire alla macchina (in cosa devi programmare?): "per i=1,2,3 controlla che il lato $L_i$ intersechi il lato $l_i$; alla prima istanza di lato che non lo fa, fermati e dimmi che le figure sono disgiunte; altrimenti finisci il ciclo."
A seconda del linguaggio in cui scrivi puoi farlo in $10^n$ modi.
Perfetto ora mi è tutto chiaro grazie mille sei stato molto preciso!
Comunque sto programmando in C++ e OpenGl e i problemi non sono finit qui
ho un'altra domanda da chiedere per cui aprirò un' altra discussione 
Comunque sto programmando in C++ e OpenGl e i problemi non sono finit qui
ho un'altra domanda da chiedere per cui aprirò un' altra discussione
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo