Feature: Witness points for distance query

[JohnnyMudcrab]

First of all, thanks a lot for this piece of software. I was looking quite a while to find something like this.

Besides the minimal distance between two polytopes I am also interested in the points on the involved polytope that are the closest to each other. Referring to your publications I think those points are called witness points. Is there a possibility to determine those witness points or are they by any chance already calculated inside the library and only need to be interfaced?

[MattiaMontanari]

Thanks, I'm glad to know this library is useful :-)

You're right, the closest points are called witness points - a terminology I adopted from past publications - but the library doesn't compute them. The reason is simply to make the code simpler (and faster), but it's easy to add.

If you have two sets of points (bodies) P and Q, to compute the witness points you need: (i) barycentric coordinates, and (ii) the list of points of P and Q that form the simplex. The barycentric coordinates are computed and stored in the simplex structure (lambda). The list of points needs a bit of bookkeeping in the distance sub-algorithm and when evaluating the support functions: basically you need to keep track of which points of P and Q, at iteration k, are added to the simplex.

The math is simple (there is more in the paper in Equation 11 ):

The lambdas are computed by the distance sub-algorithm, what you need to keep track of (for each iteration k) are all points and . Then the witness point on P is:

and on Q is:

[JohnnyMudcrab]

Thanks, that helped a lot!

[MattiaMontanari]

Same as #30