Para utilizar as rotinas em seus programas eh interessante observar que o cdigo pode ser otimizado, mas isso depende do tipo de teste que o seu programa fara.

As vezes utilizar rotinas ja prontas nao eh muito divertido, aprender sim eh divertido, entao aqui esta uma tentativa de explicar alguma coisa dos programas.

Arquivo: convex.txt
rymaeda@yahoo.com julho/2000

1) A TEORIA: ALGUNS FATOS (Combinacao convexa)
-------------------------
      B
      |
      |\
      | \
      |  \
      |   \
      |    \ 
      |     \
      |   *  \
      |    E  \
      |        \
      |         \
    A ------------ C


Sejam (xa,ya), (xb,yb) e (xc,yc) as coordenadas dos vrtices de um triangulo qualquer ABC.
Um ponto E (coordenadas xe e ye) qualquer do triangulo pode ser expresso por:
      xe= A1*xa + A2*xb + A3*xc     [I]
      ye= A1*ya + A2*yb + A3*yc     [II]

Para e somente para os pontos ("interiores") do triangulo valem as seguintes propriedades
      1 = A1 + A2 + A3   [III] 
      A1 >= 0            [IV]
      A2 >= 0            [V]
      A3 >= 0            [VI]

Na verdade para todos os pontos do plano (x,y) as equaes [I] a [III] sao *sempre* validas porem somente para os pontos do triangulo as equacoes de [I] a [VI] sao validas.
Notar que as equacoes [I], [II] e [III], formam um sistema de equacoes lineares.


2) TESTANDO SE UM PONTO PERTENCE A UM TRIANGULO
-----------------------------------------------
Conhecidas as coordenadas dos vertices de um triangulo, xa, ya, xb, yb, xc e yc, uma vez que as equacoes
      xe= A1*xa + A2*xb + A3*xc     [I]
      ye= A1*ya + A2*yb + A3*yc     [II]
      1 = A1 + A2 + A3              [III] 
sao validas para qualquer ponto (xe, ye), para testar se um ponto qualquer (xe, ye) pertence ao triangulo precisamos resolver o sistema de equacoes lineares em A1, A2 e A3 e verificar se todas as inequacoes [IV] a [VI] sao validas
      A1 >= 0            [IV]
      A2 >= 0            [V]
      A3 >= 0            [VI]

Por exemplo, dado o triangulo (0,0) (10,10) (10,0) para verificarmos se o ponto (4,2) pertence ao triangulo resolvemos o sistema em A1, A2 e A3.

       4= A1*0 + A2*10 + A3*10     [I]
       2= A1*0 + A2*10 + A3*0      [II]
       1 = A1 + A2 + A3            [III]

eliminando os termos nulos:
       4= A2*10 + A3*10            [I]
       2= A2*10                    [II]
       1 = A1 + A2 + A3            [III]

       de [II] obtemos que A2= 0,2

       substituindo A2 em [I]:
       4= 0,2*10 + A3*10 -> A3= 0,2

       substituindo A2 e A3 em [III]:
       1 = A1 + 0,2 + 0,2 -> A1= 0,6

       A1= 0,2
       A2= 0,2
       A3= 0,6
       Uma vez que atendem as inequacoes [IV], [V] e [VI], concluimos que o ponto (4,2) pertence ao triangulo.


3) ALGUMAS OBSERVACOES DA IMPLEMENTAO
---------------------------------------
No programa convex ('convex.c') poderiamos resolver o sistema de equacoes lineares numericamente atraves do metodo de Gauss-Seidel, por exemplo, durante a execucao, porem *parece* vantajoso (em termos de tempo de processamento e de codigo) resolver o sistema de equacoes simbolicamente, e implementar as solues simbolicas.
Para o sistema acima obtivemos:

A1= (xb*yc-xc*yb+ye*xc-yc*xe+xe*yb-xb*ye)/(-xa*yc+xa*yb-xb*ya+xb*yc+xc*ya-xc*yb)

A2= -(-xc*ya+xe*ya+ye*xc-xa*ye+xa*yc-yc*xe)/(-xa*yc+xa*yb-xb*ya+xb*yc+xc*ya-xc*yb)

A3= (xe*ya-xe*yb+xa*yb-xa*ye+xb*ye-xb*ya)/(-xa*yc+xa*yb-xb*ya+xb*yc+xc*ya-xc*yb)

Eis porque nao eh muito saudavel tentar entender a teoria pela implementacao :)
No programa foi implementada uma versao fatorada reduzindo a metade o numero de multiplicacoes.

4) O TETRAEDRO
---------------
Para o tetraedro vale o seguinte sistema de equacoes lineares

xe=A1*xa+A2*xb+A3*xc+A4*xd
ye=A1*ya+A2*yb+A3*yc+A4*yd
ze=A1*za+A2*zb+A3*zc+A4*zd
1=A1+A2+A3+A4
com as seguintes restricoes:
A1 >= 0
A2 >= 0
A3 >= 0
A4 >= 0

Resolvendo simbolicamente:
A1= (xd*yc*zb-xb*zc*ye-yd*xb*ze+yb*ze*xd+ye*xb*zd-xd*yb*zc-xc*yb*ze-xc*yd*zb+xc*yb*zd+zb*yd*xe-yb*zd*xe-yd*xe*zc+xe*yb*zc+xb*ze*yc-xb*zd*yc+xb*zc*yd-zb*ye*xd-ze*xd*yc+zd*xe*yc+ze*xc*yd-zd*xc*ye-xe*yc*zb+ye*xd*zc+xc*ye*zb)/(xd*za*yb-xc*za*yb-za*xd*yc+za*xc*yd+xb*yc*za-xb*yd*za+xd*yc*zb-xd*zb*ya+xa*yd*zb-xd*yb*zc+xd*ya*zc-xc*yd*zb-xc*ya*zd+xc*yb*zd+xa*zc*yb+xa*zd*yc-xa*zd*yb-xa*zc*yd-xb*ya*zc-xb*zd*yc+xb*zc*yd+xb*ya*zd+xc*zb*ya-xa*yc*zb)
A2= -(za*xd*yc-za*xc*yd+yd*za*xe-ye*za*xd-za*xe*yc+za*xc*ye-yd*xa*ze+xe*ya*zc-xd*ya*zc+xc*ya*zd+xa*ze*yc-xa*zd*yc+xa*zc*yd-ya*zd*xe+ye*xa*zd-yd*xe*zc-xc*ya*ze+ya*ze*xd-ze*xd*yc+zd*xe*yc+ze*xc*yd-zd*xc*ye+ye*xd*zc-xa*zc*ye)/(xd*za*yb-xc*za*yb-za*xd*yc+za*xc*yd+xb*yc*za-xb*yd*za+xd*yc*zb-xd*zb*ya+xa*yd*zb-xd*yb*zc+xd*ya*zc-xc*yd*zb-xc*ya*zd+xc*yb*zd+xa*zc*yb+xa*zd*yc-xa*zd*yb-xa*zc*yd-xb*ya*zc-xb*zd*yc+xb*zc*yd+xb*ya*zd+xc*zb*ya-xa*yc*zb)
A3= (xe*zb*ya-xd*zb*ya+xb*ya*zd-ya*zd*xe+ya*ze*xd-xb*ya*ze+zb*ye*xd-zb*yd*xe-xa*ye*zb+xa*yd*zb+yb*zd*xe-yb*ze*xd+xd*za*yb-xa*zd*yb+yd*xb*ze-xb*yd*za+yd*za*xe-ye*xb*zd+ye*xa*zd-ye*za*xd+xb*ye*za-xe*za*yb+xa*ze*yb-yd*xa*ze)/(xd*za*yb-xc*za*yb-za*xd*yc+za*xc*yd+xb*yc*za-xb*yd*za+xd*yc*zb-xd*zb*ya+xa*yd*zb-xd*yb*zc+xd*ya*zc-xc*yd*zb-xc*ya*zd+xc*yb*zd+xa*zc*yb+xa*zd*yc-xa*zd*yb-xa*zc*yd-xb*ya*zc-xb*zd*yc+xb*zc*yd+xb*ya*zd+xc*zb*ya-xa*yc*zb)
A4= -(za*xe*yc+xc*za*yb-xb*yc*za-za*xc*ye-xe*za*yb+xb*ye*za-xb*zc*ye-xe*ya*zc-xc*yb*ze-xa*zc*yb+xa*ze*yb-xa*ze*yc+xe*yb*zc-xb*ya*ze+xb*ze*yc+xb*ya*zc+xc*ya*ze-xc*zb*ya+xa*yc*zb-xa*ye*zb+xe*zb*ya-xe*yc*zb+xc*ye*zb+xa*zc*ye)/(xd*za*yb-xc*za*yb-za*xd*yc+za*xc*yd+xb*yc*za-xb*yd*za+xd*yc*zb-xd*zb*ya+xa*yd*zb-xd*yb*zc+xd*ya*zc-xc*yd*zb-xc*ya*zd+xc*yb*zd+xa*zc*yb+xa*zd*yc-xa*zd*yb-xa*zc*yd-xb*ya*zc-xb*zd*yc+xb*zc*yd+xb*ya*zd+xc*zb*ya-xa*yc*zb)

No programa foi implementada uma versao fatorada reduzindo a um terco o numero de multiplicacoes.
