問題タブ [intersection]

光線があります。光線が当たる最も近い線分を見つける必要があります。最初に線分をソートすると O(log n) 時間でこれを行うことができると思いますが、それらをソートする方法を思い出せません...ある種のツリーが最適に機能すると思いますが、どうすればソートできますか始点と終点の両方でそれらを？可能であれば、このデータ構造への高速挿入も希望します。

1 つの光線と 1 つの線分のコードはたくさんありますが、1 つの線と多数の線分のコードが必要です...どの用語を検索すればよいかわかりません。

適切な記事へのリンクは有効です。C++ コードはさらに優れています。ありがとう！:)

PS: 線分は、実際には自己交差しないポリゴンのエッジであり、反時計回りの順序で並べ替えられています...しかし、別の方法で並べ替えると、いくつかの利点があると思いますか?

これはすべて2Dです。

よく考えてみると、これが可能かどうかは完全にはわかりません。ある種の空間分割が役立つかもしれませんが、そうでなければ、任意の光線と比較できるように線を並べ替える方法が思いつきません。

ラインがポリゴンでインターセプトされているかどうかを確認する方法

オブジェクトの 2 つの配列間で共通のアイテムを表示するにはどうすればよいですか。私の交差点は何も返していません。オブジェクトは、Linq to SQL クラスから作成されます。

点と三角形の交点をテストする方法を知っています。

...しかし、マウス座標を使用してポイントの開始位置を画面平面上に正確に移動する方法がわからないため、マウスカーソルが画面上のどこにあるかに応じてポイント角度が変化する必要があります。これも機能するはずです私のOpenGLアプリケーションで使用している透視角度に関係なく完全に、異なる透視角度ではポイント角度が異なります... gluPerspective() は、私が話している関数です。

私は VB.Net を使用しており、2 つの 1 次元配列を持っています。両方に共通する要素を見つけるための組み込み関数はありますか? それとも自分で書く必要がありますか？

比較的単純なことを解決する必要があります。n個の頂点の凸型2Dポリゴンと、「y」座標を持つ水平（！）線があります。必要なのは1つだけです。ポリゴンがこの線と交差しているかどうか（つまり、2つの交差があるかどうか）を確認することです。

私が考えることができる最も速いものは、ポリゴン内の最小/最大y座標を見つけ（2つの比較と2つのストアでn回繰り返されるループ）、次に最小y <=y<最大yであるかどうかを比較することです。

どういうわけか、これはもっと「数学的に」解決できると思いますが、私は常に遅いコードで終わります（たとえば、ベクトルの方法-n[i]とn[i + 1]の差を計算してから、それらを乗算したり、追加したりする必要があります- -2 cmps +ストアよりもはるかに遅い）。

私はいくつかの数字のセットを交差させており、これを行うには、マップに数字が表示されるたびにカウントを保存します。

パフォーマンスが非常に遅いことがわかりました。

詳細：-セットの1つに150,000の数字が含まれています-そのセットと別のセットの交差には、最初は約300ミリ秒、2回目は約5000ミリ秒かかります-まだプロファイリングを行っていませんが、ブレークするたびにmalloc.cで交差を実行している間のデバッガー！

では、どうすればこのパフォーマンスを向上させることができますか？別のデータ構造に切り替えますか？マップのメモリ割り当てパフォーマンスをどのように改善しますか？

アップデート：

1. std::mapまたはboost::unordered_mapにスペースを事前に割り当てるように依頼する方法はありますか？
2. または、これらを効率的に使用するためのヒントはありますか？

Update2：

C＃HashSet<T>やDictionary<K、V>のようなFastC++コンテナを参照してください。

Update3：

set_intersectionのベンチマークを行い、ひどい結果が得られました。

コード：

STL で set_intersection を使用して 100,000 個の数字のセットと 1,000 個の数字のセットを交差させています。C# では 11ms かかりますが、21 秒かかります。

C++ コード:

C# コード:

Visual Studio 2008 SP1 を搭載した Vista x64 Business を実行しているマシン (クアッド コア、8 GB RAM) で、2 つの数値セットを非常に迅速に交差させようとしています。

C++ で 2 つのアプローチを実装し、C# で 1 つ実装しました。これまでのところ、C# のアプローチの方が高速です。C++ のアプローチを改善して、C# よりも高速にできるようにしたいと考えています。

C# の出力は次のとおりです: (リリース ビルド)

2 つの異なるアプローチ (Release x64 build) の初期 C++ 出力を次に示します。

3 つのアプローチ (x64 ビルドのリリース) の最新の C++ 出力を次に示します。

最新のベンチマーク:

そのため、set_intersection アプローチは C# よりも約 2 倍遅くなりますが、最初の C++ アプローチよりも 2 倍速くなります。

最新の C++ コード:

C# コード:

C++ コード:

わかりました、これが最新のものです。いくつかの変更があります。

• C++ セットが適切にセットアップされ、50% の共通部分が作成されました (C# のように)。
• Set1 はシャッフルされているためソートされず、set2 はすでにソートされていません
• set_intersection の実装はベクトルを使用し、それらを最初にソートするようになりました

C++ (リリース、x64) 結果:

そのため、C# よりも 2 倍遅くなります。@Jalf: かなり高速な数値を取得していますが、ここで間違っていることはありますか?

C++ コード:

バラバラの文字の束からアナグラムを見つける必要があるいくつかのゲームでは、可能なすべてのアナグラムを見つけて、必要に応じてそれらを既知の文字位置にフィルターする順列アルゴリズムを実装することになりまし-matchた (ちなみに、これは素晴らしいことです)。しかし、意味不明な単語の膨大なリストをざっと読んでも、その中に隠されていた適切な単語が実際には明らかにならないため、長い単語の場合、これは非常にエラーが発生しやすいことがわかりました。

そこで、英語の単語の大きなリスト (どこかで入手できるはずです) があれば、順列のリストと適切な単語のリストを交差させて、(できれば) 順列リストからすべての実際の単語を取得できると考えました。

PS の多くの演算子はコレクションに対して異なる働きをするので、次のようなことができると思いました。

そして交差点を戻します。残念ながら、それはそれほど簡単ではありません。私が考えた他のオプションは、1つのリストを繰り返し処理し-contains、各項目に対して実行することです:

これはおそらく機能しますが、非常に遅いと思います（特に$wordlistが a の結果である場合gc wordlist.txt）。または、巨大な正規表現を作成することもできます。

しかし、それもおそらくそれほど速くはありません。上記の巨大な正規表現でも使用できるかもしれませんfindstrが、それは間違っていると感じています。

使用できる組み込みのソリューションはありますか?これまでの試みよりも優れていますか? それ以外の場合は、おそらく単語リストをハッシュテーブルに入れて、-contains十分に高速な反復アプローチを使用します。