5

円のリストを取得し、完全に重なっている円のリストのみを返す関数を実行しようとしています (別の円の内側)。問題は、アルゴリズムが少なくともO(n²)であることです。これは、getConcentricCircles 関数のネストされた for と、大規模なデータセットの時間がかかるためです。それを最適化する方法はありますか？

編集:これが役立つかどうかはわかりませんが、アルゴリズムを使用して、虹彩と瞳孔の検出で誤検知を検出します。円が完全に別の円の内側にある場合、それが瞳孔で、外側が虹彩である可能性があります。それらは同心である必要があり、非常に単純化されますが、人間の目の瞳孔は虹彩の中心に正確にないことがあります。これが私がこれを行う理由です。

編集 2: isCircleInCircle を Peter Lawrey のソリューションに置き換えました。一部のケースでは正しくありませんでした

円が円の内側にあるかどうかをチェックする関数:

private static boolean isCircleInCircle(Circle a, Circle b) {
    // the circle is inside if the distance between the centre is less than the difference in the radius
    double dx = a.getX() - b.getX();
    double dy = a.getY() - b.getY();
    double radiusDifference = a.getRadius() - b.getRadius();
    double centreDistanceSquared = dx*dx + dy*dy; // edited
    return radiusDifference * radiusDifference > centreDistanceSquared;
}

次に、リストのすべての要素を相互にチェックし、重なっている円 (および重なっている円) のみを保存します。

public HashSet<Circle> getConcentricCircles(List<Circle> circleList) {
    HashSet<Circle> toReturn = new HashSet<Circle>();

    for (Circle circle : circleList) {
        for (Circle toCheck : circleList) {
            // if the circles are not the same and one is inside another,
            if (!toCheck.equals(circle) && isCircleInCircle(circle, toCheck)) {
                // add both to the hashset
                toReturn.add(circle);
                toReturn.add(toCheck);
            }
        }
    }
    return toReturn;
}
4

6 に答える 6

2

円が別の円の中にあるかどうかを確認する私の第一印象は、知ることです

  1. 2 つの円の中心点。
  2. 円の 2 つの半径。
  3. C1 から C2 + R2 > R1 の場合は外側、そうでない場合は内側です。

これにより、ロジックが大幅に簡素化されます。

編集：複雑さを改善するために、

  1. 半径順 (大から小)
  2. 最初の for ループは大きいものから小さいものへ
  3. 2 番目の for ループは大から小へ
  4. 外側のループ内に内側の円が見つかったら、この円を外側のループから削除できます
  5. 理由は、最初の外側の円がこの内側の円をカプセル化しているためです。この円に他のものが含まれていても気にしません。後で大きな円の外側にある場合のみです。

これにより、大きな円で囲まれた円のリストが取得されます。

于 2012-10-18T09:44:55.890 に答える
1

データセットはどのようなものですか? 他のすべての円に対してすべての円をチェックすることは、本質的に O(n^2) です。複雑さを軽減するために、各円を互いにチェックする必要がないように何らかのメトリックが必要です。

円の分布に応じて、役立つさまざまなブロードフェーズ アルゴリズムがあります。たとえば、円が占める空間が通常の半径よりもはるかに大きく、円がその空間全体に比較的均等に分布している場合、四分木を使用した空間分割は、互いに離れたオブジェクト間の封じ込めのチェックを最小限に抑えるのに役立ちます。

于 2012-10-18T10:06:20.190 に答える
1

このアルゴリズムの複雑さは、以下に減らすことはできませんO(n^2)。点が円の中心で、円の半径が で1、隣接するグリッド点間の距離が である規則的なグリッドを想像してください2。円は他の円に含まれません。これを証明するには、すべての円を互いにチェックする必要があります。すべての組み合わせを証明しない場合、相互にテストされていない円aとが存在します。bでは、行列を少しだけ変えてみましょう。円aは円よりも少し小さくb、同じ中心を共有しています。aに含まれていることが見つからなかったbため、アルゴリズムは正しくありません。複雑さの証明は以上です。

プログラムを高速化するには、平均的なケースに集中する必要があります。つまり、小さな円が大きな円に含まれているということです。ノードが円を表し、エッジがソース円にターゲット円が含まれていることを示す有向グラフを作成します。半径が最大の円から始めます。深さ優先検索を使用してグラフを作成します。a円が別の円に含まれていることがわかっている場合。b次に、 に含まれる円を見つけてみてくださいa。存在する場合bは、まず に進みbます。含まれるものがなくなったらb、一歩下がって、見つかった別の円に含まれていないすべての円を処理します。これにより、次の複雑さが得られますO(nlog(n))最良の場合。これは、含まれるノードの検索中の残りのノードの管理と、半径によるソートによるものです。ここでの最良のケースは、すべての円の中心が同じで半径が異なる場合です。

編集：アキ
の答えは、これをスピードアップする別の方法を思い出させました。平均的なケースでは、円はクラスターを形成し、1 つの円が他のいくつかの円と部分的に重なっています。したがって、最初に依存セットの分割を計算できます (いいえ、これは難しいので、独立したセットを意味するわけではありません)。これにより、上記のアルゴリズムで使用する必要があるデータ サイズが減少します。NP

次に、完全に重複する可能性のある候補を見つけることに関しては、別の改善が可能です。円は平面に含まれているため、R ツリーや四分木などの空間データ構造を使用して、完全に重複している可能性のある候補をより効率的に見つけることができます。

ただし、これで最悪の場合の複雑さが軽減されるとは思いません。これらの提案でさえ、上記の最悪の場合のパフォーマンスが向上します。新しい最悪のケースは、中心が通常のグリッドのポイントであるが、通常のグリッド内のポイント間の距離と比較すると半径が非常に大きい円である可能性があります。

于 2012-10-18T11:13:54.543 に答える
0

2つのポイント：

  1. 現状では、アルゴリズムが正しくありません。この図の円について考えてみます。

    小さな円は重なっていますが、大きな円には含まれていません

    小さな円の4つのコンパスポイントは大きな円の中にありますが、含まれていません。この問題は、AlanとPeterによって説明されたより優れたサークルインサークルテストで解決できます。

  2. 問題の説明は完全には明確ではありません。出力は次のようになります。

    1. 最初の円が2番目の円に含まれている円のすべてのペアのリスト。
    2. 少なくとも1つの円が完全に重なっているすべての円のリスト。
    3. 他の円の組み合わせによって完全に重なっているすべての円のリスト。

    これらの最初の円は、すべての円が同心円状に配置されている可能性があるため、O（N ^ 2）よりも明らかに最悪の場合の実行時間はありません。したがって、最初の円には互いに含まれ、2番目の円には最初の円を除くすべてが含まれます。 。そして出力は（N ^ 2）なので、実行時間はこれ以上良くなることはありません。

    2つ目は、最悪の場合の実行時間がより良いかもしれませんが、私はそれについてあまり自信がありません。

    3番目は解決するのが悪夢のように聞こえます。

オーバーラップの量が少ないことを保証できる場合は、各円の最小（左端）と最大（右端）のx位置のリストを作成して並べ替えることで、実行時間を短縮できます。リストを操作し、左端に遭遇したときに作業セットに円を追加し、右端に遭遇したときに円を削除します。各円がセットに追加されるので、現在セットにある他の円だけと比較します。

円の分布とサイズについて十分な保証ができない限り、これは依然として最悪の場合のO（n ^ 2）ですが、これは大きなステップになるはずです。

于 2012-10-18T10:23:47.757 に答える
0

円の分布が許せば、円をその位置に基づいていくつかまたはそれ以上のスロットに分割し、テストを同じまたは近くのスロットに制限することができます。

問題は目の数が十分に少ないリアルタイムの目検出であることが判明したため、複雑さは問題になりません。RT では、フレームごとに 10M の浮動小数点操作を簡単に費やすことができます。これは、1000 未満の円のデータセットを示唆します (最適化されたインナーループを使用)。

最適化されたインナーループは次のように計算します:

(x0-x1)^2 + (y0-y1)^2 < (r0-r1)^2

円のペアごとに、どちらかがもう一方を完全に囲んでいるかどうかを確認します。この式は並列処理に非常に適しています。また、上記のテストに合格した円ごとにカウンターを増やすことで、奇妙なケースを除外することもできます。最終的には 1 になるはずです。

于 2012-10-18T10:21:03.313 に答える
0

あなたの質問に対する答えではありませんが、以下を使用してチェックをより速くすることができます。

private static boolean isCircleInCircle(Circle a, Circle b) {
    // the circle is inside if the distance between the centre is less than the difference in the radius
    double dx = a.getX() - b.getX();
    double dy = a.getY() - b.getY();
    double radiusDifference = a.getRadius() - b.getRadius();
    // double centreDistance = Math.sqrt(dx*dx + dy+dy);
    // return radiusDifference > centreDistance;
    double centreDistanceSquared = dx*dx + dy+dy;
    return radiusDifference * radiusDifference > centreDistanceSquared;
}

private static boolean isPointInCircle(Point center, int outsideRadius, Point toCheck) {
    // distance between two points is sqrt((x1-x2)²+(y1-y2)²)
    double dx = center.getX() - toCheck.getX();
    double dy = center.getX() - toCheck.getY();
    double distSquared = dx * dx + dy * dy;
    // if the distance is less than the radius, then the point is inside
    return distSquared < outsideRadius * outsideRadius;
}

注: 最初のメソッドは 2 番目のメソッドを必要としなくなりました。

于 2012-10-18T09:54:44.130 に答える