可能な限り最小数の「子である」比較操作を使用して、アイテムの順序付けられていないリストをツリー構造にソートするアルゴリズムを探しています。
私の特定のケースに関する少しの背景ですが、私が見つけられなかった種類の一般的な並べ替えアルゴリズムを探しているだけだと思います (絞り込むのが難しい検索用語です)。
輪郭の順序付けられていないリストがあります。これは、閉じたポリゴンを表す座標のリストにすぎません。これらの輪郭間の関係を表すツリーを作成したいと考えています。たとえば、最も外側の輪郭がルートであり、次のレベルの各輪郭が子などになります。したがって、ノードごとにゼロから多数の子を持つツリー構造。
アルゴリズムの重要な要件は、輪郭が別の輪郭の子であるかどうかを判断するテストを最小限に抑えることです。この操作は非常にコストがかかるためです。輪郭は多くの頂点を共有できますが (多くの場合共有します)、交差してはなりません。これらの共有頂点は、通常、マップの境界に達した場所で発生します。マップの直線エッジに対する一連の同心円の半円を想像してください。最終的な答えにたどり着く前に多数のポイント オン ラインを実行する必要がある場合、ポイント イン ポリ テストは遅くなります。
これが私がこれまでに思いついたアルゴリズムです。それは間違いなくかなり素朴ですが、うまくいきます。おそらく、役立つヒューリスティックがいくつかあります-たとえば、輪郭は特定の範囲内の深さを持つ別の輪郭の子である可能性が高いだけです-しかし、最初に基本的なアルゴリズムを釘付けにしたいと思います。最初の危険信号は、それが指数関数的であるということです。
for each candidate_contour in all_contours
for each contour in all_contours
// note already contains means "is direct or indirect child of"
if contour == candidate_contour or contour already contains(candidate_contour)
continue
else
list contours_to_check
contours_to_check.add(candidate_contour)
contour parent_contour = candidate_contour.parent
while (parent_contour != null)
contours_to_check.add(parent_contour)
parent_contour = parent_contour.parent
for each possible_move_candidate in contours_to_check (REVERSE ITERATION)
if possible_move_candidate is within contour
// moving a contour moves the contour and all of its children
move possible_move_candidate to direct child of contour
break
それでうまくいきます-または少なくともそう見える-しかし、自明ではない数の輪郭(数百、おそらく数千までと考えてください)では非常に遅くなります。
これを行うための根本的により良い方法はありますか、または実際に-これを正確に処理する既知のアルゴリズムはありますか? 前に述べたように、私の場合の鍵は、「内にある輪郭」の比較を最小限に抑えることです。
以下のジムの回答に基づいてソリューションを追加するように編集します-ジムに感謝します!
これは最初の反復であり、優れた (10 倍) の改善が得られます。反復 2 については以下を参照してください。 このコードと私の元のアルゴリズムは、輪郭セットが非常に大きくなると 10 倍以上高速になります。下の画像は、数秒 (v の 30 奇数秒前) で並べ替えられ、順番にレンダリングされています。いくつかのヒューリスティックを追加して、さらに改善する余地があると思います。たとえば、元のリストが領域に従ってソートされた場合、新しい候補はそれぞれツリー内のどこかの葉ノードでなければなりません。問題は、既存のリーフをテストするためにトラバースするブランチを決定することです。多くのブランチ/リーフがある場合は、上部のブランチを調べて検索スペースを削減する方がおそらく迅速です..さらに考えるべきことがあります!
public static iso_area sort_iso_areas(List<iso_area> areas, iso_area root)
{
if (areas.Count == 0)
return null;
areas.Sort(new iso_comparer_descending());
foreach (iso_area area in areas)
{
if (root.children.Count == 0)
root.children.Add(area);
else
{
bool found_child = false;
foreach (iso_area child in root.children)
{
// check if this iso_area is within the child
// if it is, follow the children down to find the insertion position
if (child.try_add_child(area))
{
found_child = true;
break;
}
}
if (!found_child)
root.children.Add(area);
}
}
return root;
}
// try and add the provided child to this area
// if it fits, try adding to a subsequent child
// keep trying until failure - then add to the previous child in which it fitted
bool try_add_child(iso_area area)
{
if (within(area))
{
// do a recursive search through all children
foreach (iso_area child in children)
{
if (child.try_add_child(area))
return true;
}
area.move_to(this);
return true;
}
else
return false;
}
反復 2 - 既存のリーフのみと比較
新しい輪郭は既存の葉にしか収まらないという私の以前の考えに続いて、実際には、ターゲットの葉以外のすべての葉の最初の境界チェックで poly in poly テストが失敗するため、これははるかに高速であることに気づきました。最初の解決策は、ブランチをたどってターゲットを見つけることでした。定義により、途中のすべてのポリゴンが境界チェックに合格し、それ以上リーフが見つからなくなるまで完全なポリインポリ テストが行われました。
Jim のコメントとコードの再検討に続いて、残念ながら 2 番目の解決策は機能しませんでした。poly-in-poly テストはすぐに失敗するはずであり、候補を受け入れる葉を見つけた場合、そこに調べる必要のあるポリゴンはもうありません..
反復 2 の再検討
輪郭だけができるわけではありませんが葉に収まる、それはほとんどの場合そうです - また、それらは通常、順序付けられた輪郭のリストの最近の先行者に収まります。この最終的に更新されたコードはこれまでで最速であり、ツリー トラバーサルを完全に廃止しています。最近のより大きなポリゴンを逆方向に歩いて、それぞれを試行するだけです。他のブランチからのポリゴンは、境界チェックでポリインポリテストに失敗する可能性が高く、候補ポリを囲む最初のポリが直接の親でなければなりません。リストの前の並べ替えに。このコードは、ソートを再びミリ秒の範囲に落とし込み、ツリー トラバーサルよりも約 5 倍高速です (残りの高速化を説明する poly-in-poly テストにも大幅な速度の改善が行われました)。ルートは、ソートされたエリアのリストから取得されます。knowはすべての輪郭 (すべての境界ボックス) を包含します。
この問題について考えるのを手伝ってくれて、特にジムに感謝します。重要なのは、リスト内の後の輪郭の子になることができない輪郭が保証されているリストへの輪郭の元のソートでした。
public static iso_area sort_iso_areas(List<iso_area> areas)
{
if (areas.Count == 0)
return null;
areas.Sort(new iso_comparer_descending());
for (int i = 0; i < areas.Count; ++i)
{
for (int j = i - 1; j >= 0; --j)
{
if (areas[j].try_add_child(areas[i]))
break;
}
}
return areas[0];
}
私の最初の試み: 133 s 反復 1 (リーフを見つけるためにブランチをトラバースする): 9 秒 反復 2 (サイズの昇順で輪郭を逆方向に歩く): 25ms (他の pt-in-poly の改善も)。