Re: [Algorithms] GJK

[Pierre T. <p.t...@wa...>]

> I agree... I'd definitely need to understand an algorithm before I can
> debug it, but precision in algorithms is important (of course), and I find
> it easier to be precise in C++ than in the univeral language of
> mathematics (obscure movie reference).

Ok, why not. I'd have said the opposite anyway :)
The code version is easier to understand IMHO, but I don't see it more
precise. Well, whatever.


> I think even with comments and indenting kept in there it wouldn't be that
> readable.  I'm a big fan of variables that mean something.

:)


> I'll send you the article offline (it's like I walked to the library to
> make a copy for you, and then walked over to France to hand it to you,
> right?)

Yeah! Great! Many thanks! (...a 40 Mo download, whoops! No pb, I get a fast
connexion)

As a matter of facts, there's some fresh meat inside. Rabbitz is the only
one for example to relate the As matrix to Lagrange multipliers. Not really
useful I guess, but worth writing. And he tells things in a clearer way than
Gilbert for sure. Now I think I probably got it, by "brute-forcely" writing
down all the possible matrices, determinants and cofactors: I must admit
that formula works :) But I'm still very upset about it. I must find some
more time to work on it, but I think for the moment I'll just go ahead.


> using your notation:
>
> Delta(j)(X + yj) = Sigma(i in IX) (Delta(i)(X) * ((yi | yk) - (yi | yj)))
>
> Delta(j)(X + yj) = Sigma(i in IX) (Delta(i)(X) * (yi | (yk - yj)))
>
> I don't think you can do that last step.

Ok, let's fix that, because it may be important. Either it works and nobody
noticed it before (hence, I'm very happy), either it does not work and it
probably means I'm not using the right delta formula, which would explain
why I can't re-derive it (hence, I'm very happy as well because I found my
bug :)

Let's get rid of the Sigma, painful to write in ASCII. Am I wrong, or do we
have the following pattern :

    D(j) = d(0) * y0|(yk - yj)   +   d(1) * y1|(yk - yj)   +   d(2) *
y2|(yk - yj)  + ......

with d(i) = scalar values, yi = vectors.

The dot-product is associative: (rX)|Y = r(X|Y)

Hence
    D(j) = (d(0)*y0)|(yk - yj)   +   (d(1)*y1)|(yk - yj)   +
  (d(2)*y2)|(yk - yj)  + ......

The dot-product is commutative: X|Y = Y|X

Hence
    D(j) = (yk - yj)|(d(0)*y0)   +   (yk - yj)|(d(1)*y1)   +   (yk -
yj)|(d(2)*y2)  + ......

The dot-product is distributive: X|(Y+Z) = X|Y + X|Z
And since yk and yj are fixed (they don't depend on i in the Sigma
expression):

    D(j) = (yk - yj)| [ (d(0)*y0)   +  (d(1)*y1)   +   (d(2)*y2)  + ...... ]


Unless I'm blind and totally missing a key point somewhere, here it is. What
do you think ?


Pierre