チェコ工科大学BIE-PA2 課題 2D CAD system 【モートンオーダー】 WriteUp

今回はBIE-PA2という科目での宿題での自分の回答を紹介してみます。

問題

問題は、平面上に図形たちがいくつか置かれ、次に平面上の座標が与えられ、その座標に属する図形のIDを配列として列挙する。という問題です。
詳細は下記に書きます。面白かった点を先に書きます。

４分木とモートンオーダーをつかって面白かったので書きます。

４分木

https://github.com/MeditationDuck/pa2/blob/main/quad_tree.cpp

単に４分木を使ってみたコードです。思ったより早くなりませんでした。
ポイントはQuadTree クラスです。図形は長方形の外枠を作るので、基本的に長方形ないかどうかを判定します。

class Quadtree {
public:
    ~Quadtree(){}

    Rectangle bounds;
    vector<unique_ptr<Shape>> st_rects;
    bool divided;
    size_t depth;

    array<unique_ptr<Quadtree>, 4>childs;

    Quadtree(Rectangle bounds,size_t dp = 0)
            : bounds(bounds),divided(false), depth(dp) {
                if(depth>sum_depth) sum_depth = depth;
    }

    bool in_bound(const Shape& shape) const {
        if(bounds.contains(shape.left_down.m_X, shape.left_down.m_Y) && bounds.contains(shape.right_up.m_X, shape.right_up.m_Y) ){
            return true;
        }
        return false;
    }
    void subdivide() {
        int x1 = bounds.x1;
        int y1 = bounds.y1;
        int x2 = bounds.x2;
        int y2 = bounds.y2;
        int halfWidth = (x2 - x1) / 2;
        int halfHeight = (y2 - y1) / 2;

        childs[0] = unique_ptr<Quadtree>(new Quadtree(Rectangle(x1, y1, x1 + halfWidth, y1 + halfHeight), depth+1)); //northwest
        childs[1] = unique_ptr<Quadtree>(new Quadtree(Rectangle(x1 + halfWidth, y1, x2, y1 + halfHeight), depth+1)); //northeast
        childs[2] = unique_ptr<Quadtree>(new Quadtree(Rectangle(x1, y1 + halfHeight, x1 + halfWidth, y2), depth+1)); //southwest
        childs[3] = unique_ptr<Quadtree>(new Quadtree(Rectangle(x1 + halfWidth, y1 + halfHeight, x2, y2), depth+1)); //southeast
        divided = true;
    }
};

図形たちを保存するためにQuadTreeオブジェクトを使っています。
Rectangleオブジェクトにはint x1, y1, x2, y2; の座標が保存されています。
なので、in_bound メソッドで図形を入れてあげる事により、その図形が
QuadTreeオブジェクトに属するのかを判定できます。この辺が遅かったみたいです。
Subdivideメソッドで子Quadtreeオブジェクトを作っています。

モートンオーダー

https://github.com/MeditationDuck/pa2/blob/main/morton_order.cpp

そこで、モノトーンオーダーを使うことにしました。
QuadTreeクラスです。

class Quadtree {
public:
    vector<unique_ptr<Shape>> st_rects;
    vector<Shape*> pt_shapes;
    size_t depth;
    // static const size_t max_tmp = 0;
    static const size_t depth_max = 20;
    array<unique_ptr<Quadtree>, 4>childs;

    Quadtree(size_t dp = 0):depth(dp) {if(depth > max_depth){max_depth = depth;};}
    ~Quadtree(){}
    void make_child(int i){childs[i] = unique_ptr<Quadtree>(new Quadtree(depth+1));}
};

ポイントは、非常に短くなったことです。in_boundメソッドが必要なくなりました。また、Rectangle bounds; がありません。これはモートンオーダーの特徴により、図形の座標のみからどの子を選ぶかを決めることができるからです。なので、in_boundメソッドを使って図形がこのQuadTreeオブジェクトに属するかを試す必要がありません。

一般的なモートンオーダーだと、座標の作りが右に行くほどx座標の値が大きくなり、下に行くほどy座標の値が大きくなりますが、今回の場合y座標について、上に行くほど、y座標の値を大きくしていたので、少し作りが違いました。

- > - > - > 
\
    \
        \
             \ 
- > - > - >   
こういう順番で値が大きくなる２進数で１変数での座標の表現をします。モートン数ですね。

そして、test(x, y) メソッドで与えられる座標に図形が入っているかを試します。if文の分岐が外枠の長方形では使われておらず。それぞれの図形の座標点たちから本当にそこに属するのかを試しています。

std::vector<int> test(int x, int y) const {
        vector<int> res;
        const Quadtree* curr = &qt;
        int i = 0;
        long long morton = mortonNumber(x, y);
        while(curr){
            for (const auto& e : curr->st_rects) {
                if (e->is_at(x, y)) {
                    res.push_back(e->m_id);
                }
            }
            curr = curr->childs[((morton >> (40 - i * 2)) & 0b11)].get();
            i++;
        }
        return res;
    }

困った点

実装での困った点がありました。ランダムテストが全く100%で通りません。でした。

class CCircle: public Shape{
    int m_x,m_y;
    long m_r2;
public:
    CCircle(int id, int x, int y, int z):Shape(id,CCoord(x + z, y + z), CCoord(x - z, y - z)),m_x(x),m_y(y),m_r2(static_cast<long>(z)*z){}

    bool is_at(int x, int y) const override {
        return (m_r2 - ( static_cast<long>(m_x - x) * (m_x - x) +  static_cast<long>(m_y - y) * (m_y - y)) >= 0 );
    }
    CCircle* clone()  const override { return new CCircle(*this);}
};

問題の条件では、座標が -1048576 to 1048576 で表されるので、int型で収まります。しかし、円での与えられた座標が内側にあるかの判定には、２点間距離を図るため int * int では値のオーバーフローをするので long型の変数に代入するか型変換する必要がありました。これに気づくのに結構時間がかかりました。コンストラクタの引数にしていがあるので、こういうところに気を配る必要がありました。

与えられた問題の詳細

与えられる図形は、
長方形、円、三角形、凸多角形の４種類
それぞれCRectangle、CCircle、CTriangle、CPolygon のクラスですでにひな形が作られています。それぞれのオブジェクトには整数IDがつけられます。

コンストラクタのフォーマットも決まっています。

CRectangle ( int ID, int x1, int y1, int x2, int y2 ) は長方形を表します。長方形は対角のペアによって与えられます (x1 < x2 も y1 < y2 も保証されません)。 CCircle ( int ID, int x, int y, int r) は、中心点と半径によって与えられる円を表します。 CTriangle ( int ID, CCoord a, CCoord b, CCoord c) は三角形を表します。三角形は頂点によって与えられます。構造体 CCoord はテスト環境で定義されます CPolygon ( int ID, vertices) は凸多角形を表します。多角形はその頂点のリストによって定義されます。ただし、頂点はさまざまな方法で提供できます。 CCoord の配列内の範囲を定義する 2 つのポインターによって、例: CPolygon ( 1, v, v + 5 ) コンテナ内の範囲を定義する 2 つの反復子によって、例: CPolygon ( 1, v . begin (), v . end () ) std::initializer_list を使用します。例: CPolygon ( 1, { CCoord ( 1, 2 ), CCoord ( 5, 7 ), CCoord ( 10, -3 ), ... } ) CCoord インスタンスのリストによる (リストは非常に長い場合があります)。例: CPolygon ( 1, CCoord ( 1, 2 ), CCoord ( 5, 7 ), CCoord ( 10, -3 ), ... ) オブジェクトを保存および操作するには、コンテナー CScreen を提供する必要があります。コンテナーは次のインターフェイスを提供する必要があります。

与えられたサンプルコードをもとに実装します。
https://github.com/MeditationDuck/pa2/blob/main/sample.cpp

単純にすべての図形を配列に入れた場合です。
https://github.com/MeditationDuck/pa2/blob/main/sample.cpp

上記は今回の科目がC++の文法を学ぶための科目だったのでそれらについてを聞かれている感じです。

他の木構造を使ったほうが今回は早くなったそうです。自分の実装方法も効率的じゃなさそうだなと思います。実行速度などが加味してあるスコアでは模範解答の67.37%でした。

まとめ

そもそも時間のない時期の課題にしては重かったなと思います。
50回提出できるうち36回提出しました。
もっと木構造のアルゴリズムについてよく知っておこうと思った。
The Billion Dollar Code という映画について、

Watch The Billion Dollar Code | Netflix Official Site

この映画を1年くらい前に見ていて、1年越しにブダペストとかベルリンとか４分木とかケバブとか。 映画に関する文脈が自分にめちゃめちゃ装備されていることに気づいてずっと面白かった。