質問: 多面体間(出来れば非凸多面体)の距離計測を行う際に有効な策として、 外積(ベクトル積)以外の方法で最短距離を求めることが出来る策があれば教えて下さい。 C++&OpenGLで計算を行い描写するプログラムを作成したいと考えています。 よろしくお願いします。
回答: 二線分間の最短距離となる線分がどちらかの端点を含むとは限らないので、二多面体間の最短距離となる線分がいずれかの頂点を含むという仮定はよろしくありません。辺と辺とが最短距離になる位置関係の場合、拾えなくなります。 相互に十分に離れているのなら、両者の中心を結ぶ直線を使って全頂点をソートするとか、URLで主張されているようにボロノイ領域を利用するとかによって、「近い方」からシラミツブシ的&分枝限定法的に探す方法が思い浮かびます。