File: convex.txt
rymaeda@yahoo.com July/2000
<<<I apologize my very bad english (corrections are welcome, e-mail me!)>>>

1) THE THEORY: SOME FACTS (Convex combination)
-------------------------
      B
      |
      |\
      | \
      |  \
      |   \
      |    \ 
      |     \
      |   *  \
      |    E  \
      |        \
      |         \
    A ------------ C

Let (xa,ya), (xb,yb) and (xc,yc) be the vertices coordinates of one generic triangle ABC.
One point E (coordinates xe and ye) of the plane can be expressed by:
      xe= A1*xa + A2*xb + A3*xc     [I]
      ye= A1*ya + A2*yb + A3*yc     [II]

If and only if to inners (triangle) points, the follow equalities are verifiable:
      1 = A1 + A2 + A3   [III] 
      A1 >= 0            [IV]
      A2 >= 0            [V]
      A3 >= 0            [VI]

In truth all the points of the (x, y) plane the equations [I] to [III] are *always* valids, but only to inner triangle points, equations from [I] to [IV] are always valids.
Note that the equations [I], [II] and [III] form one linear equations system.


2) TESTING IF ONE POINT IS IN TRIANGLE
------------------------------------------------
Give one triangle with knowled coordinates xa, ya, xb, yb, xc and yc, once that the equations
      xe= A1*xa + A2*xb + A3*xc     [I]
      ye= A1*ya + A2*yb + A3*yc     [II]
      1 = A1 + A2 + A3              [III] 
are verified for any point (xe, ye), to test if one point is in triangle [(xa,ya),(xb,yb),(xc,yc)], we need solve the system of linear equations in A1, A2 and A3, and verify if all inequations, from [IV] to [VI] are valids too.
      A1 >= 0            [IV]
      A2 >= 0            [V]
      A3 >= 0            [VI]

For example, let the triangle (0,0) (10,10) (10,0), to verify if the point (4,2) is in we need initialy solve in 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]

elimining null terms:
       4= A2*10 + A3*10            [I]
       2= A2*10                    [II]
       1 = A1 + A2 + A3            [III]

       of [II] we obtain that A2= 0.2

       substituting A2 in [I]:
       4= 0,2*10 + A3*10 -> A3= 0.2

       substituting A2 and A3 in [III]:
       1 = A1 + 0,2 + 0,2 -> A1= 0.6

       A1= 0.2
       A2= 0.2
       A3= 0.6
       So, how [IV], [V] and [VI] are verified, the point (4,2) is in triagle (inner point).


3) ALGUMAS OBSERVACOES DA IMPLEMENTAO
---------------------------------------
In convex program ('convex.c') I pre-solved the linear equations system (with Maple V), which results was:

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)

This equation was factored before be implemented in convex.c.

4) THE TETRAHEDRON
------------------
For the tetrahedron:

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
with the folowing restrictions:
A1 >= 0
A2 >= 0
A3 >= 0
A4 >= 0

Simbolicaly solving:
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)

The factored version, that was implemented in convex3d, has only one third of the numbers of multiplications.

<<<I apologize my very bad english (corrections are welcome, e-mail me!)>>>