-1

stackoverflow を含め、このアルゴリズムを検索しましたが、見つかりませんでした。既知の 3D 図形の最小境界四角形を見つけるのとは異なり、任意のソリッドで連続した 3D 図形の軸に沿ったものを見つけようとしています...唯一の制約は、この図が 3D マトリックスに完全に収まることです。のサイズ、たとえば 800X800X800 を指定します。誰かがこれのための効率的なアルゴリズムを教えてもらえますか?

4

1 に答える 1

0

3D 図形は、一連の境界ポリゴンなどとしてどのように表現されますか?

外面上にあるかどうかに関係なく、3D フィギュア上に頂点のセットを取得できると思います。

「最小境界長方形」とは、最小体積の境界直線状の立体（レンガのような）を意味すると思います。

「軸合わせ」とは、ブリックの端が既存の x、y、および z 軸に合わせられていることを意味すると思います。つまり、レンガを回転させて小さくすることはできません。

次に、説明から、各座標軸に沿って最小値と最大値が必要なように聞こえます。それには、ポイント数に比例して時間がかかります。

私が質問を誤解しない限り。

編集:わかりました、ブール値の 800^3 配列から始めているというあなたの説明から、私が考えることができる最高のものは次のとおりです:

// a lot depends on how you index array a
// this assumes it is one big block of bools
#define A(i,j,k) a[(i)*800*800 + (j)*800 + (k)]
// to get the minimum X value
for (ix = 0; ix < 800; ix++){
    // search over the entire plane at x == ix
    // this can probably be improved by stepping pointers
    for (iy = 0; iy < 800; iy++){
        for (iz = 0; iz < 800; iz++){
            // nobody likes goto, but it's probably the quickest way out
            // of the 3 nested loops
            if (A(ix, iy, iz)) goto L100;
        }
    }
}
L100:;
// here, ix is minimum x value

// do similar code for max x, min and max y, min and max z

多少は改善できそうです。最悪の場合、ボリュームが空の場合、これは 3^800^3 テストを実行します。最良のケースでは、ボリュームがいっぱいの場合、6*800^2 テストを実行します。

于 2012-12-02T01:34:36.940 に答える