次の 3D キューブ選択問題の効果的なアルゴリズムを見つけようとしています。
ポイントの 2D 配列を想像して (サイズ x サイズの正方形にしましょう)、それを辺と呼びます。
計算を簡単にするために、max を size-1 として宣言します。6 面の立方体を作成し、0,0 を左下に、max,max を右上に保ちます。z を使用して、単一の立方体が配置されている側を追跡します。y は上、x は右です。
public class Point3D {
public int x,y,z;
public Point3D(){}
public Point3D(int X, int Y, int Z) {
x = X;
y = Y;
z = Z;
}
}
Point3D[,,] CreateCube(int size)
{
Point3D[,,] Cube = new Point3D[6, size, size];
for(int z=0;z<6;z++)
{
for(int y=0;y<size;y++)
{
for(int x=0;x<size;x++)
{
Cube[z,y,x] = new Point3D(x,y,z);
}
}
}
return Cube;
}
ランダムな単一点を選択するには、次のような 3 つの乱数を使用できます。
Point3D point = new Point(
Random(0,size), // 0 and max
Random(0,size), // 0 and max
Random(0,6)); // 0 and 5
プラスを選択するには、特定の方向が現在の辺の内側に収まるかどうかを検出できます。そうでなければ、立方体が中心点に接する側にあることがわかります。
次のような 4 つの関数を使用します。
private T GetUpFrom<T>(T[,,] dataSet, Point3D point) where T : class {
if(point.y < max)
return dataSet[point.z, point.y + 1, point.x];
else {
switch(point.z) {
case 0: return dataSet[1, point.x, max]; // x+
case 1: return dataSet[5, max, max - point.x];// y+
case 2: return dataSet[1, 0, point.x]; // z+
case 3: return dataSet[1, max - point.x, 0]; // x-
case 4: return dataSet[2, max, point.x]; // y-
case 5: return dataSet[1, max, max - point.x];// z-
}
}
return null;
}
ここで、ランダムな点で任意の形状 (定義済みのランダムなブロブなど) を選択する方法を見つけたいと思います。ただし、正方形またはギザギザの円のいずれかに調整することで解決します。
実際の表面積はゆがみ、コーナーでそれ自体に折り畳まれますが、これは問題なく、補正する必要はありません (ステッカーを立方体のコーナーに置くことを想像してください。コーナーがステッカーの中心と一致する場合、ステッカーの 4 分の 1 が必要になります)角に貼り付けて折りたたむために取り外します）。繰り返しますが、これは望ましい効果です。
重複選択は許可されていないため、2 回選択されるキューブは何らかの方法でフィルター処理する必要があります (または重複が発生しないように計算する必要があります)。これは、HashSet または List を使用し、ヘルパー関数を使用してエントリが一意かどうかを確認するという単純なものです (選択は常に最大 1000 キューブをはるかに下回るため、これは問題ありません)。
キューブの辺を含むクラスのこの関数のデリゲートは次のようになります。
現在、キューブの各面をチェックして、選択のどの部分がその面にあるかを確認することを考えています。
選択した Point3D の同じ側にある選択部分を計算することは、位置を変換する必要がなく、境界だけであるため、簡単です。次に 5 つの翻訳を行い、その後、他の 5 つの側面をチェックして、選択した領域の一部がその側面にあるかどうかを確認します。
私はこのような問題を解決することに慣れていないので、誰かがこの問題に対するより良い解決策を持っているかどうか疑問に思っていました.
@arghbleargh 詳細な説明をリクエストしました:
6 辺のキューブを使用し、16 のサイズを使用します。各辺は 16x16 ポイントです。配列が次のように開始されるように、サイド、y、x に z を使用した 3 次元配列として格納されます。それもいいでしょう) [z][y][x] しかし、各サブアレイの個別の初期化が必要になります。
選択した点を中心とした 5x5 の正方形を選択してみましょう。このような 5x5 の正方形を見つけるには、問題の軸に 2 を減算して加算します: x-2 を x+2 に、y-2 を y+2 にします。
側面をランダムに選択すると、選択する点は z = 0 (立方体の x+ 側面)、y = 6、x = 6 です。
6-2も6+2もサイドの16×16配列の範囲内に収まっていて選びやすいです。
ただし、選択ポイントを x=0 および y=6 にシフトすると、少し難しくなります。x - 2 では、選択した辺の左側の辺を調べる必要があります。幸いなことに、辺 0 または x+ を選択しました。これは、立方体の上辺または下辺ではなく、上辺または下辺に移動しない限り、すべての軸が x+ = 右、y+ = 上になるためです。したがって、左側の座標を取得するには、最大 (サイズ - 1) - x を減算するだけで済みます。サイズ = 16、最大 = 15、x = 0-2 = -2、最大 - x = 13 を覚えておいてください。したがって、こちら側のサブセクションは x = 13 ～ 15、y = 4 ～ 8 になります。これをパーツに追加すると、元の側で選択すると、選択全体が得られます。
選択範囲を 0,6 にシフトすると、すべての軸が簡単に整列するという安全性に隠れることができないため、より複雑になります。多少の回転が必要な場合があります。可能な翻訳は 4 つだけなので、それでも扱いやすいです。
0,0 にシフトすると、問題が実際に発生し始めます。現在、左と下の両方が反対側に回り込む必要があります。さらに、細分化された部分でも領域が外れるからです。この傷の唯一の救済策は、選択の重複部分を気にしないことです。そのため、可能な場合はそれらをスキップするか、後で結果からフィルターすることができます。
「法線軸」側から下側に移動したので、回転させて正しい座標を一致させ、点がエッジを正しく包み込むようにする必要があります。
各辺の軸は立方体に折りたたまれているため、正しい点を選択するために一部の軸を反転または回転する必要がある場合があります。
エリア内にある立方体上のすべてのポイントを選択するためのより良い解決策があるかどうかという問題が残ります。おそらく、それぞれの側に平行移動行列を与えて、ワールド空間での座標をテストできますか?