0

3D 空間の三角形のリストと、(x,y,z) 座標で記述された点があります。その点に最も近い三角形を返すメソッドを書いています。

私が最初に書いた素朴な実装は、すべての三角形をループし、その点からの距離をチェックしてから、距離が最小のものを返すというものでした。ほとんどの場合、私が扱っている三角形のリストは数千または数万の要素で構成されているため、それを最適化する方法を検討しています。

私は octree 構造を使用してそれを機能させようとしてきたので、すべての三角形を格納する octree を作成しました。ポイントと各セルの中心との間の距離を計算し、そのセル内の三角形と比較することにより、そのポイントから最も近いオクトリーのセルを見つけることが可能なアプローチだと思いました。

octree から最も近いセルを取得する方法はわかりません (octree を使用するのは初めてです)。これは私がこれまでに書いた方法です：

public Octree getClosestCell(final Vec3D point) {
    if (children != null) {
        float minDist = Float.MAX_VALUE;
        Octree closestCell = null;
        for (int i = 0; i < 8; i++) {
            final float dist = point.distanceTo(children[i].getCentroid());
            if (dist < minDist) {
                minDist = dist;
                closestCell = children[i];
            }
        }
        return closestCell.getClosestCell(point);
    } else {
        return this;
    }
}

要約すると、2 つの質問があります。

  1. 提案されたアプローチは、この問題を最適化するための良い解決策のように思えますか?
  2. 上記の方法は正しいように見えますか、それとも最も近いセルを取得するためのより良い方法がありますか?
4

0 に答える 0