Javaの範囲検索アルゴリズム

投稿日: 2022-10-26 2022-10-26
タグ: Algorithms, Java, Java Search

1. 概要

このチュートリアルでは、2次元空間での近傍の検索の概念について説明します。次に、Javaでの実装について説明します。

2. 1次元検索と2次元検索

二分探索は、分割統治法を使用してアイテムのリストから完全に一致するものを見つけるための効率的なアルゴリズムであることがわかっています。

ここで、各アイテムが平面内のXY座標（点）で表される2次元領域について考えてみましょう。

ただし、完全に一致するのではなく、平面内の特定の点の近傍を検索するとします。 最も近いn個の一致が必要な場合、二分探索は機能しないことは明らかです。これは、二分探索では1つの軸で2つのアイテムしか比較できないのに対し、2つの軸でそれらを比較できる必要があるためです。

次のセクションでは、バイナリツリーデータ構造の代替案を見ていきます。

3. 四分木

クワッドツリーは、各ノードに正確に4つの子がある空間ツリーデータ構造です。各子は、ポイントまたは4つのサブ四分木を含むリストのいずれかになります。

ポイントは、XY座標などのデータを格納します。領域は、ポイントを格納できる閉じた境界を表します。四分木の到達範囲を定義するために使用されます。

任意の順序で10の座標の例を使用して、これをさらに理解しましょう。

(21,25), (55,53), (70,318), (98,302), (49,229), (135,229), (224,292), (206,321), (197,258), (245,238)

最初の3つの値は、左端の図に示すように、ルートノードの下にポイントとして保存されます。

ルートノードは、3ポイントの容量に達したため、新しいポイントに対応できなくなりました。したがって、ルートノードの領域を4つの等しい象限に分割します。

これらの各象限は3つのポイントを格納でき、さらにその境界内に4つの象限を含めることができます。これは再帰的に実行できるため、象限のツリーが作成されます。このツリーで、quadtreeデータ構造に名前が付けられます。

上の中央の画像では、ルートノードから作成された象限と、次の4つのポイントがこれらの象限にどのように格納されているかを確認できます。

最後に、右端の図は、他の象限が新しいポイントを受け入れることができる一方で、1つの象限がその領域内のより多くのポイントに対応するために再び細分化される方法を示しています。

Javaでこのアルゴリズムを実装する方法を見ていきます。

4. データ構造

四分木データ構造を作成しましょう。 3つのドメインクラスが必要です。

まず、XY座標を格納するPointクラスを作成します。

public class Point {
    private float x;
    private float y;

    public Point(float x, float y) {
        this.x = x;
        this.y = y;
    }

    // getters & toString()
}

次に、象限の境界を定義するRegionクラスを作成しましょう。

public class Region {
    private float x1;
    private float y1;
    private float x2;
    private float y2;

    public Region(float x1, float y1, float x2, float y2) {
        this.x1 = x1;
        this.y1 = y1;
        this.x2 = x2;
        this.y2 = y2;
    }

    // getters & toString()
}

最後に、 QuadTreeクラスを作成して、データをPointインスタンスとして保存し、子をQuadTreeクラスとして保存します。

public class QuadTree {
    private static final int MAX_POINTS = 3;
    private Region area;
    private List<Point> points = new ArrayList<>();
    private List<QuadTree> quadTrees = new ArrayList<>();

    public QuadTree(Region area) {
        this.area = area;
    }
}

QuadTree オブジェクトをインスタンス化するには、コンストラクターを介してRegionクラスを使用してそのareaを指定します。

5. アルゴリズム

データを格納するコアロジックを作成する前に、いくつかのヘルパーメソッドを追加しましょう。これらは後で役立つことがわかります。

5.1. ヘルパーメソッド

Regionクラスを変更してみましょう。

まず、 containsPoint からまでのメソッドを使用して、特定のポイントが領域の領域の内側にあるか外側にあるかを示します。

public boolean containsPoint(Point point) {
    return point.getX() >= this.x1 
        && point.getX() < this.x2 
        && point.getY() >= this.y1 
        && point.getY() < this.y2;
}

次に、 doesOverlap からまでのメソッドを使用して、特定の領域が別の領域とオーバーラップするかどうかを示します。

public boolean doesOverlap(Region testRegion) {
    if (testRegion.getX2() < this.getX1()) {
        return false;
    }
    if (testRegion.getX1() > this.getX2()) {
        return false;
    }
    if (testRegion.getY1() > this.getY2()) {
        return false;
    }
    if (testRegion.getY2() < this.getY1()) {
        return false;
    }
    return true;
}

最後に、 getQuadrant からまでの範囲を4つの等しい象限に分割し、指定されたものを返すメソッドgetQuadrantを作成しましょう。

public Region getQuadrant(int quadrantIndex) {
    float quadrantWidth = (this.x2 - this.x1) / 2;
    float quadrantHeight = (this.y2 - this.y1) / 2;

    // 0=SW, 1=NW, 2=NE, 3=SE
    switch (quadrantIndex) {
    case 0:
        return new Region(x1, y1, x1 + quadrantWidth, y1 + quadrantHeight);
    case 1:
        return new Region(x1, y1 + quadrantHeight, x1 + quadrantWidth, y2);
    case 2:
        return new Region(x1 + quadrantWidth, y1 + quadrantHeight, x2, y2);
    case 3:
        return new Region(x1 + quadrantWidth, y1, x2, y1 + quadrantHeight);
    }
    return null;
}

5.2. データの保存

これで、データを格納するロジックを記述できます。 QuadTreeクラスで新しいメソッドaddPointを定義して、新しいポイントを追加することから始めましょう。このメソッドは、ポイントの場合、trueを返します。正常に追加されました：

public boolean addPoint(Point point) {
    // ...
}

次に、ポイントを処理するロジックを記述しましょう。まず、ポイントがQuadTreeインスタンスの境界内に含まれているかどうかを確認する必要があります。また、QuadTreeインスタンスがMAX_POINTSポイントの容量に達していないことを確認する必要があります。

両方の条件が満たされた場合、新しいポイントを追加できます。

if (this.area.containsPoint(point)) {
    if (this.points.size() < MAX_POINTS) {
        this.points.add(point);
        return true;
    }
}

一方、 MAX_POINTS値に達した場合は、サブ象限の1つに新しいポイントを追加する必要があります。このために、子 quadTrees リストをループし、同じ addPoint メソッドを呼び出して、追加が成功するとtrue値を返します。次に、ポイントを1つの象限に正確に追加する必要があるため、すぐにループを終了します。

このすべてのロジックをヘルパーメソッド内にカプセル化できます。

private boolean addPointToOneQuadrant(Point point) {
    boolean isPointAdded;
    for (int i = 0; i < 4; i++) {
        isPointAdded = this.quadTrees.get(i)
            .addPoint(point);
        if (isPointAdded)
            return true;
    }
    return false;
}

さらに、現在のクワッドツリーを4つの象限に細分化するための便利なメソッドcreateQuadrantsを用意しましょう。

private void createQuadrants() {
    Region region;
    for (int i = 0; i < 4; i++) {
        region = this.area.getQuadrant(i);
        quadTrees.add(new QuadTree(region));
    }
}

新しいポイントを追加できなくなった場合にのみ、このメソッドを呼び出して象限を作成します。これにより、データ構造が最適なメモリスペースを使用することが保証されます。

すべてをまとめると、更新されたaddPointメソッドがあります。

public boolean addPoint(Point point) {
    if (this.area.containsPoint(point)) {
        if (this.points.size() < MAX_POINTS) {
            this.points.add(point);
            return true;
        } else {
            if (this.quadTrees.size() == 0) {
                createQuadrants();
            }
            return addPointToOneQuadrant(point);
        }
    }
    return false;
}

5.3. データの検索

データを格納するために四分木構造を定義したので、検索を実行するためのロジックを考えることができます。

隣接するアイテムを探しているので、開始点としてsearchRegionを指定できます。次に、ルート領域と重複しているかどうかを確認します。含まれている場合は、searchRegion内にあるすべての子ポイントを追加します。

ルート領域の後、各象限に入り、プロセスを繰り返します。これは、ツリーの終わりに到達するまで続きます。

上記のロジックをQuadTreeクラスの再帰メソッドとして記述してみましょう。

public List<Point> search(Region searchRegion, List<Point> matches) {
    if (matches == null) {
        matches = new ArrayList<Point>();
    }
    if (!this.area.doesOverlap(searchRegion)) {
        return matches;
    } else {
        for (Point point : points) {
            if (searchRegion.containsPoint(point)) {
                matches.add(point);
            }
        }
        if (this.quadTrees.size() > 0) {
            for (int i = 0; i < 4; i++) {
                quadTrees.get(i)
                    .search(searchRegion, matches);
            }
        }
    }
    return matches;
}

6. テスト

アルゴリズムが整ったので、テストしてみましょう。

6.1. データの入力

まず、前に使用したのと同じ10の座標を四分木に入力しましょう。

Region area = new Region(0, 0, 400, 400);
QuadTree quadTree = new QuadTree(area);

float[][] points = new float[][] { { 21, 25 }, { 55, 53 }, { 70, 318 }, { 98, 302 }, 
    { 49, 229 }, { 135, 229 }, { 224, 292 }, { 206, 321 }, { 197, 258 }, { 245, 238 } };

for (int i = 0; i < points.length; i++) {
    Point point = new Point(points[i][0], points[i][1]);
        quadTree.addPoint(point);
}

6.2. 範囲検索

次に、下限座標（200、200）と上限座標（250、250）で囲まれた領域で範囲検索を実行してみましょう。

Region searchArea = new Region(200, 200, 250, 250);
List<Point> result = quadTree.search(searchArea, null);

コードを実行すると、検索領域内に含まれる1つの近くの座標が得られます。

[[245.0 , 238.0]]

座標（0、0）と（100、100）の間で別の検索領域を試してみましょう。

Region searchArea = new Region(0, 0, 100, 100);
List<Point> result = quadTree.search(searchArea, null);

コードを実行すると、指定した検索領域の2つの近くの座標が得られます。

[[21.0 , 25.0], [55.0 , 53.0]]

検索領域のサイズに応じて、0、1、または多くのポイントが得られることがわかります。したがって、ポイントが与えられ、最も近いn個の近傍を見つけるように求められた場合、与えられたポイントが中心にある適切な検索領域を定義できます。

次に、検索操作の結果のすべてのポイントから、指定されたポイント間のユークリッド距離を計算し、それらを並べ替えて最も近いネイバーを取得できます。

7. 時間計算量

範囲クエリの時間計算量は、単純に O（n）です。その理由は、最悪のシナリオでは、指定された検索領域が入力領域以上の場合、各アイテムをトラバースする必要があるためです。

8. 結論

この記事では、最初に二分木と比較することで四分木の概念を理解しました。次に、2次元空間に分散したデータを保存するためにどのように効率的に使用できるかを見ました。

次に、データを保存して範囲検索を実行する方法を確認しました。

いつものように、テスト付きのソースコードはGitHubで利用できます。

getdocs

13036