***********************************************
*** Apresentao ******************************
***********************************************

   Este texto tem o propsito de apresentar as
retas paramtricas bem como algumas aplicaes.


***********************************************
*** Algumas definies ************************
***********************************************

   Para facilitar o entendimento e possvel
troca de idias,  proveitoso que lembremos
algumas definies da geometria:

Segmento de reta:  uma poro delimitada de
reta, tendo incio e fim definidos.

Reta: abstrao matemtica cujo comprimento 
infinito (no tem extremidades!).

Semi-reta: tem apenas uma das extremidades
delimitada, seu comprimento tambm  infinito.

   Assim enquanto dois segmentos de reta podem
ser no paralelos e no se cruzarem, duas retas
no paralelas, no plano, *sempre* se cruzam.


***********************************************
**** Representando um segmento atravs de *****
**** funes paramtricas                 *****
***********************************************

Seja um segmento de reta definido pelos pontos
A e B:

             * B(xb,yb)
            /
           /
          /
 A(xa,ya)*

Podemos representar este segmento atravs de
funes paramtricas:

 x1= (xb-xa)*t + xa
 y1= (yb-ya)*t + ya

O parmetro 't' variando de 0 a 1 representa os
pontos pertencentes ao segmento. Assim quando
t=0, x1=xa e y1=ya; quando t=1, x1=xb e y1=yb;
valores intermedirios resultam em pontos do
segmento, por exemplo, para t=0.5 resulta no
ponto mdio do segmento.

Podemos representar analogamente outro segmento
definido pelos pontos C e D:

 x2= (xd-xc)*u + xc
 y2= (yd-yc)*u + yc

O parametro 'u' tem a mesma funcao de 't'.


***********************************************
*** Verificando se ocorre interseco *********
*** e, caso ocorra, sua coordenada ************
***********************************************

Para sabermos se dois segmentos AB e CD se
interseccionam fazemos:

x1=x2
y1=y2

substituindo:

(xb-xa)*t + xa = (xd-xc)*u + xc
(yb-ya)*t + ya = (yd-yc)*u + yc

rearranjando:

(xb-xa)*t - (xd-xc)*u = xc - xa
(yb-ya)*t - (yd-yc)*u = yc - ya

rearranjando:

(xb-xa)*t + (xc-xd)*u = xc - xa
(yb-ya)*t + (yc-yd)*u = yc - ya

Obtemos assim um sistema de equaes lineares
em 't' e 'u', com todos os outros parmetros
conhecidos.

Para resolver simbolicamente este sistema de
equaes podemos utilizar o mtodo de Cramer.

Antes uma pequena otimizao:

A11= xb - xa
A12= xc - xd
B1= xc - xa
A21= yb - ya
A22= yc - yd
B2= yc - ya

O sistema fica assim:

A11*t + A12*u = B1
A21*t + A22*u = B2

Aplicando o referido mtodo obtemos:

t= (A22*B1-A12*B2)/(A11*A22-A21*A12)

u= (A11*B2-A21*B1)/(A11*A22-A21*A12)

Como o denominador  o mesmo para 't' e para
'u' podemos calcul-lo somente uma vez, por
exemplo:

Delta= (A11*A22-A21*A12)
t= (A22*B1-A12*B2)/Delta;
u= (A11*B2-A21*B1)/Delta;

Caso Delta seja igual a zero o sistema de
equaes no tem solucao. Graficamente os
segmentos so paralelos ou um ou ambos
segmentos tem comprimento nulo (zero).

Calculamos 't' e 'u' e caso ambos estejam no
intervalo 0 e 1, ocorre interseco entre os
segmentos.

Podemos, mesmo que 't' e 'u' no estejam no 
intervalo entre 0 e 1, inclusive-inclusive,
calcular o ponto de interseco com as j
conhecidas equaes:

x1= (xb-xa)*t + xa = A11*t + xa
y1= (yb-ya)*t + ya = A21*t + ya

Um exemplo numrico do teste de interseco:

Seja um segmentos AB, com A(0;5) e B(10;4), e
outro segmento CD, com C(5;7) e D(3,-1). 
Ser que eles se cruzam?

A11= xb - xa = 10 - 0 = 10
A12= xc - xd = 5 - 3 = 2
B1= xc - xa = 5 - 0 = 5
A21= yb - ya = 4 - 5 = -1
A22= yc - yd = 7 - (-1) = 8
B2= yc - ya = 7 - 5 = 2

Delta= (A11*A22-A21*A12)
Delta= (10 * 8 - (-1) * 2)
Delta= 82

t= (A22*B1-A12*B2)/Delta;
t= (8 * 5 - 2 * 2) / 82
t= 36/82 = 18/41

u= (A11*B2-A21*B1)/Delta;
u= (10 * 2 - (-1) * 5)/82
u= 25/82

como 0 <= t <= 1
e 0 <= u <= 1

ambos os segmentos se interseccionam caso
queiramos saber as coordenadas:

x1= A11*t + xa
x1= 10 * 18/41 + 0
x1= 180/41 = 4.390243902
 
y1= A21*t + ya
y1= (-1) * 18/41 + 5
y1= 187/41 = 4.560975610

Este problema est ilustrado na figura
'2segmentos.jpg' anexa.


***********************************************
*** Um mtodo para selecionar linhas **********
*** atravs de um ponto "de seleo" **********
***********************************************

Descreveremos a seguir um mtodo que pode ser
utilizado para se selecionar linhas (segmentos
de retas) com um mouse, por exemplo.

Dado um segmento AB, representado
paramtricamente por:

x1= (xb-xa)*t + xa
y1= (yb-ya)*t + ya

e um ponto C a testar. Podemos, a partir do
ponto C, definir uma equao de uma reta
perpendicular ao segmento AB.

x2= (ya-yb)*u + xc
y2= (xb-xa)*u + yc

Podemos calcular o ponto de interseccao
fazendo:

x1=x2
y1=y2

substituindo:

(xb-xa)*t + xa = (ya-yb)*u + xc
(yb-ya)*t + ya = (xb-xa)*u + yc

rearranjando:

(xb-xa)*t + (yb-ya)*u = xc - xa
(yb-ya)*t + (xa-xb)*u = yc - ya

Otimizando:

A11= xb-xa
A12= yb-ya
A21= yb-ya= A12
A22= xa-xb
B1= xc-xa
B2= yc-ya

Obtemos:

A11*t + A12*u = B1
A12*t + A22*u = B2

Aplicando o mtodo de Cramer:

t= (B1*A22-B2*A12)/(A11*A22-A12*A12)

e assim verificar se a interseccao I(xi,yi)
ocorre entre os pontos A e B (0 <= t <= 1) e se
a distncia d entre I e C  "suficientemente
pequena":

d^2 <= quadrado-da-distncia-mxima)

onde:

d^2 = (xc-xi)^2 + (yc-yi)^2

substituindo:

d^2 = (B1 - A11*t)^2 + (B2 - A12*t)^2

Observe que podemos trabalhar diretamente com
d^2, sem precisar calcular d.

Recapitulando, para que a linha seja
selecionada:

1a. Condio
    0 <= t <= 1

2a. Condio
    d^2 <= quadrado-da-distncia-mxima


Obs.: ao invs de testar estas duas condies
podemos tambm, para todos os segmentos
"testveis", armazenar os respectivos valores
de d^2 classific-los, e selecionar a linha
com d^2 menor, ou seja, a mais prxima do
ponto de teste ou seleo.