0

形状エンティティのコンテナがあります。円、楕円、直線、円弧があるとします。エンティティごとに、エンティティのエンドポイントとエンティティの開始点を取得できます。

エンティティを接続できるため、エンティティのエンドポイントを別のエンティティのエンドポイントにすることもできます。

エンティティがあります: 開始点、終了点、ID

接続されたエンティティごとに同じIDを割り当てたい。

接続されたエンティティとして 3 つのエンティティが 1 つの共通点を持つ場合、より長いパスを処理する必要があります。

そうするための最も効率的な方法は何ですか？これまでの私の唯一のアイデアは、コンテナ全体を反復処理し、各エンティティを他のエンティティと一緒にループにチェックインすることです。

問題が明確に定義され、タグが適切であることを願っています。そうでない場合は、コメントまたは編集してください。私はさらに詳細を提供しようとします。

4

2 に答える 2

1

少数のエンティティの場合：

for ( u32 i = 0; i < numEntities; i++ )
{
   for ( u32 j = i+1; j < numEntities; j++ )
   {
       if ( hasCommonEndpoint( entity[i], entity[j] ))
          setSameId( entity[i], entity[j] ) 
   }
}

これはO（n ^ 2）としてスケーリングされるため、エンティティの数が多い場合は爆発します。また、エンドポイントで一致するエンティティが他のエンドポイントで一致しないことも前提としています。その場合は、エンティティが複数のIDを持つことを許可する必要があります。

内側のループはj>iで始まるため、同じエンティティを2回以上比較しないことに注意してください。これにより、時間が半分になります。

エンティティの数が多い場合は、次のようなことを行います。

HashTable<endpointHash, entity> dict; 
for ( u32 i = 0; i < numEntities; i++ )
{
   dict.insert( entity[i].endpointHash(), entity[i] );
}

ここで、HashTableは、同じエンドポイントハッシュを持つエンドポイントを持つすべてのエンティティのリストをホストします。次に、リストごとに、最初のループと同じ方法で、エンドポイントに一致するリストの要素を反復処理します。これにより、おおよそO（n）+ O（m ^ 2）のスケーリングが大幅に向上します。ここで、Nは大きく、Mは小さくなります。実際のパフォーマンスは、ハッシュ関数の品質とハッシュビンの数によって異なります。

于 2012-06-22T15:32:21.750 に答える
1

@RafaelBaptista のエンドポイント ハッシュの提案に加えて、効率的な一般的なソリューションには、接続されたエンティティのグループに単一の ID を割り当てる問題を解決する、ばらばらなデータ構造が必要です。

リンクで述べたように、効率的な素集合アルゴリズムは「実質的に線形」です。正式には、線形よりも少し遅くなる可能性がありますが、実際の問題サイズでは、差は 5 倍以内です。

于 2012-06-22T23:33:56.813 に答える