computational-geometry - ポイント間隔から 3D ポイントを再構築する

Question

私は例えば8点のセットを持っています。各ポイント間のすべての距離を知っています。これらの点の 3D 座標を再構築するアルゴリズムはありますか。

Answer 1

あなたがやろうとしていることは、三辺測量と呼ばれています。正しく理解するのは難しいため、先に進む前に少し調査することをお勧めします。ただし、次のことから始めます。

実際の 3D 距離がある限り、以下は機能するはずです。そうしないと問題が発生する可能性があります。

1. 点 p1 を取り、それを原点 (0,0,0) に割り当てます。
2. 別の点 p2 を取り、(距離(p1,p2),0,0) に配置します。
3. 別の点 p3 を取り、p1 と p2 からの距離に基づいて (x,y,0) 平面に配置します。
4. 別の点 p4 を取り、p1、p2、p3 からの距離に基づいて 3D 空間に配置します。
5. ポイントがなくなるまで手順 4 を繰り返します。

最初の 3 つの手順で、座標を方向付けて固定することができます。

ステップ 3 と 4 を解決するには、平面三角形を使用します。平面三角形は、点が中心にあるため簡単に形成できます。

Answer 2

ポイントが一般的な位置にあると仮定しましょう。3 点が同一線上になく、4 点が同一平面上にないこと。特別な場合のチェックなしでアルゴリズムを単純にするためだけに、これは制限ではありません。

4 つの球体 (一般的な位置) の交点が存在する場合、その交点は 1 点です。2つの球の交点は円であり、3つの球の交点は2点であり、4番目の球の中心が他の3つの球の中心と平面上にない場合、その球はいずれかの交点のみを通過できることがわかります。 .

そのため、距離が有効な場合は、ポイントをインクリメンタルに追加することでシェイプを作成できます。

最初の 4 点の位置が方向を定義します。たとえば、最初の点は原点に設定され、2 番目の点は 1 番目から指定された距離の +X に設定され、3 番目の点は XY 平面で円の交点の +Y 方向に設定され、4 番目の点は 3 つの球の交点の +Z 方向に設定されます。

追加の点は、最初の 4 点を中心とする 4 つの球体の交点と、それらまでの距離で指定される半径によって配置できます。

Answer 3

もう1つの可能性は、メトリック多次元尺度構成法です。