2

原点を中心とし、一辺の長さ 2 の軸に沿った立方体の表面上のユークリッド 3空間内(x1, y1, z1)の2 点を とし、 とする。(x2, y2, z2)

立方体の表面上のポイント間の距離 (または二乗距離) を効率的に計算するにはどうすればよいですか?

内部的には、私はポイントを次のように表現しています(offset1, offset2, faceNumber)が、(x,y,z)フォーマット (上記参照) はすぐに利用できます。

私は C か Python のコードを好みますが、疑似コードでもなんでも喜んで受け入れます。

編集：

いくつかの事実：

  1. 最短経路は、x、y、および z で常に単調です。
  2. ポイントが同じ面にある場合、それは自明なユークリッド距離です。
  3. ポイントが同じ面にない場合、最短パスには 2 つまたは 3 つの面が含まれる可能性があります。
4

1 に答える 1

1

編集: 私がすることは、3D 立方体を 2D 平面に変えることです。ポイントが立方体の反対側にある場合、クロスのすべての端に最終サーフェスを配置する必要があることに注意してください。

立方体にこのような面がある場合、4 が面 1 に触れるように折りたたむことができます。

5
1 2 3 4 
6

最終的にはこのような 2D 平面になります。

         3
    4/5  5   5/2
3   4    1   2   3
    4/6  6   2/6
         3

というわけで、これを改造しました。これで、各コーナー パネルは、両方のパネル間で発生する接続を表します。この配列を最初にレイアウトすると、パネル 2、4、5、および 6 の各点が 3 つの点にマッピングされます。ソリューションは、複数のポイントにマップする必要がある場合に、ポイント 2 を表す特定のポイントのいずれかへの最短ラインです。

3D 立方体から 2D グラフの最初の 1 ～ 6 個のペインにポイントをマッピングするのは、非常に簡単です。残された唯一の困難は、2 平面から「2/6」平面などにポイントをマッピングする方法を理解することです。これは、それぞれの状況を考えることの問題です。例: 2 -> 2/6 は 5 -> 5/2 とは異なります。私の直感では、立方体の幅を適切な方向にシフトする前に、90 度または -90 度の回転になると思います。

たとえば、レイアウトした状況を適切に処理するには、平面 1 の左下隅と平面 2 の右下隅に値を設定します。

points in plane 2/6 = rot90(points in plane 2) - width of the cube.

平面 2/6 の左下隅に点があります。これは適切に最短経路となり、適切にはこの経路は平面 6 の面を横切ります。

于 2013-05-06T15:49:24.273 に答える