MattiaMontanari
commented
4 years ago 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
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?