Computação Gráfica
Cálculo de Interseção entre Segmentos de Reta


Uma das formas de cálculo do ponto de interseção entre dois segmentos de reta é o uso da equação paramétrica das retas.
Supondo um segmento de reta entre os pontos K e L e outro entre os pontos  M  e N, os trechos de código abaixo determinam os valores dos parâmentros S(da reta KL) e T(da reta MN) no ponto de intersecção das retas-suporte dos segmentos passados como parâmetro.

Se S e T retornados pela função estiverem entre 0 e 1, então a interseção dos segmentos existe, senão não.

Interseção em 2D


/* ********************************************************************** */
/*                                                                        */
/*  Calcula a interseccao entre 2 retas (no plano "XY" Z = 0)             */
/*                                                                        */
/* k : ponto inicial da reta 1                                            */
/* l : ponto final da reta 1                                              */
/* m : ponto inicial da reta 2                                            */
/* n : ponto final da reta 2                                              */
/*                                                                        */
/* s: valor do parâmetro no ponto de interseção (sobre a reta KL)         */
/* t: valor do parâmetro no ponto de interseção (sobre a reta MN)         */
/*                                                                        */
/* ********************************************************************** */
int intersec2d(Ponto k, Ponto l, Ponto m, Ponto n, double &s, double &t)
{
 double det;

 det = (n.x - m.x) * (l.y - k.y)  -  (n.y - m.y) * (l.x - k.x);

 if (det == 0.0)
  return 0 ; // não há intersecção

  s = ((n.x - m.x) * (m.y - k.y) - (n.y - m.y) * (m.x - k.x))/ det ;
  t = ((l.x - k.x) * (m.y - k.y) - (l.y - k.y) * (m.x - k.x))/ det ;

 return 1; // há intersecção
}

Para obter o ponto de interseção, basta substituir "t" na equação paramétrica da reta "mn" ou "s" na equação paramétrica da reta "kl", conforme o exemplo a seguir.

    Pi.x = K.x + (L.x-K.x)*s;
    Pi.y = K.y + (L.y-K.y)*s;
 
Para maiores informações sobre a fórmula da equação paramétrica de uma reta, utilizada acima, consulte a página sobre Curvas Paramétricas.

Interseção em 3D

/* ********************************************************************** */
/*                                                                        */
/*  Calcula a interseccao entre 2 retas (no espaco)                       */
/*                                                                        */
/* k : ponto inicial da reta 1                                            */
/* l : ponto final da reta 1                                              */
/* m : ponto inicial da reta 2                                            */
/* n : ponto final da reta 2                                              */
/*                                                                        */
/* s: valor do parâmetro no ponto de interseção (sobre a reta KL)         */
/* t: valor do parâmetro no ponto de interseção (sobre a reta MN)         */
/*                                                                        */
/* ********************************************************************** */
int intersec3d(k, l, m, n, s, t)
XYZR *k, *l, *m, *n;
double *t, *s ;
{
  double det;


 if (((k->x != l->x) || (k->y != l->y))  &&
     ((m->x != n->x) || (m->y != n->y)) )  /* se nao e' paralela ao plano XY*/
 {
  det = (n->x - m->x) * (l->y - k->y)  -  (n->y - m->y) * (l->x - k->x);

  if (det == 0.0)
   return 0 ;

  *s = ((n->x - m->x) * (m->y - k->y) - (n->y - m->y) * (m->x - k->x))/ det ;
  *t = ((l->x - k->x) * (m->y - k->y) - (l->y - k->y) * (m->x - k->x))/ det ;

  return 1;
 }

 if (((k->x != l->x) || (k->z != l->z))  &&
     ((m->x != n->x) || (m->z != n->z)) )  /* se nao e' paralela ao plano XZ*/
 {
  det = (n->x - m->x) * (l->z - k->z)  -  (n->z - m->z) * (l->x - k->x);

  if (det == 0.0)
   return 0 ;

  *s = ((n->x - m->x) * (m->z - k->z) - (n->z - m->z) * (m->x - k->x))/ det ;
  *t = ((l->x - k->x) * (m->z - k->z) - (l->z - k->z) * (m->x - k->x))/ det ;

  return 1;
 }

 if (((k->y != l->y) || (k->z != l->z))  &&
     ((m->y != n->y) || (m->z != n->z)) )  /* se nao e' paralela ao plano YZ*/
 {
  det = (n->y - m->y) * (l->z - k->z)  -  (n->z - m->z) * (l->y - k->y);

  if (det == 0.0)
   return 0 ;

  *s = ((n->y - m->y) * (m->z - k->z) - (n->z - m->z) * (m->y - k->y))/ det ;
  *t = ((l->y - k->y) * (m->z - k->z) - (l->z - k->z) * (m->y - k->y))/ det ;

  return 1;
 }

 return 1;
}

Para obter o ponto de interseção, basta substituir T na equação paramétrica da reta MN ou S na equação paramétrica da reta KL
Para maiores informações sobre a fórmula da equação paramétrica de uma reta, consulte a página sobre Curvas Paramétricas.