限界を究めるブログでした。最近はいろんな分野を幅広めに書いてます。2016-10-31bentley-ottmannアルゴリズムアルゴリズム約1ヶ月ぶりの更新です。n)で求めるbentley-ottmannアルゴリズムを紹介します。平面上を左端から右端へと移動していく、y軸と並行な直線です。本記事では掃引線である直線SLが登場します。algorithmでは二種類のデータ構造を扱います。ひとつはプライオリティーキューです。これは「イベント」を管理します。イベントというのは、「線分の左端点pとSLが交わる」「線分sと線分tの交点pとSLが交わる」「線分の右端点pとSLが交わる」の3種類があります。これらのイベントは点pのx座標により優先度がつけられます。ひとつは二分探索木です。掃引線Lと交わっている線分を管理します。これらの線分は、Lとの交点のy座標で優先度がつけられます。アルゴリズムプライオリティーキューQを初期化します。初期のQは入力された線分の左端点、右端点に関するイベントを含んだ状態となります。二分探索木Tを初期化します。Qが空になるまで、優先度が最小のイベントを取り出します。取り出したイベントの種類に応じて以下のとおりに処理します。イベントに関連付けられた点pが線分sの左端点ならば、線分sをTへ挿入します。Tの中で、線分sのすぐ下の線分rとすぐ上の線分tを取り出し、rとtの交点があるなら、この交点に関連付けられたイベントをQから削除します。sがrかtと交差するなら、交点をQにイベントとして追加します。点pが線分sの右端点ならば、sのすぐ下の線分rとすぐ上の線分tを探し、sをTから削除します。rとtが交差するなら交点をQにイベントとして追加します。点pが線分sと線分t(sは交点より左ではtの下である)の交点ならば、Tの中でのsとtの位置を交換します(掃引線Lとの交点を考えると、次から優先度が逆転するため)。交換後のsとtそれぞれのすぐ下の線分rs,rtとすぐ上の線分us,utを探します。rsかrtとsの交点、tとusまたはutの交点をイベントQから削除します。rsかrtとt、またはsとus、utが交差するなら、これらの交点をイベントとしてQに追加します。おおすじはwikiの和訳ですが、一部表現を削ったり足したりしてわかりやすくしてあります。アルゴリズム解説このアルゴリズムでは、「掃引線Lを左端から走らせ、Lと交差した線分のみを見ることで、効率よく交点を探す」という戦略が基本となっています。Lは左端からスムーズに途切れなく動かす必要はありません。効率よく探すことが大切なので、「線分の左端にたどり着いた」「線分と線分の交点にたどり着いた」「線分の右端にたどり着いた」この3つのいずれかが起こるところへジャンプしながら進むだけでOKです。「線分の左(右)端にたどり着いた」イベントは、現在Lと交差している線分を把握するため必要です。「線分と線分の交点にたどり着いた」こちらはなぜ必要なのでしょうか?これは、線分とLの交点を扱いやすくするためです。線分はLとの交点のy座標順にソートされ、二分探索木にて管理されます。Lを動かせば、線分とLの交点は変化します。大小関係は線分が交差しないかぎり変わりません*1。大小関係が前後してしまう交点でのイベントを扱わねばなりません。備考アルゴリズム中で、Tの中でsのすぐ上、すぐ下の線分を求める必要が出てきます。上の線分というのは、sと掃引線Lの交点のy座標より、掃引線Lとの交点のy座標が大きいものの中で最小となる線分、のことです。...ややこしいですね。要するに図的にみたとき、Lと交わっている線分のうちsのすぐ上にあるもののことです。根ノードを最初の着目ノードとします。着目ノードがsより大きいなら、これを暫定的にすぐ上の線分として、このノードの左の子を次の着目ノードとします。着目ノードがsより小さいか等しいなら、右の子を次の着目ノードとします。着目ノードがないならば、暫定的に定めていた線分をすぐ上の線分として返します。根ノードを最初の着目ノードとします。着目ノードがsより大きいか等しいなら、このノードの左の子を次の着目ノードとします。着目ノードがsより小さいなら、これを暫定的にすぐ下の線分として、右の子を次の着目ノードとします。着目ノードがないならば、暫定的に定めていた線分をすぐ下の線分として返します。知りませんね、そんなこ...2016-04-05JavaScript製HTMLパーサー改(この記事はQiitaで僕が書いたものを移行した記事です。この記事のパーサは使いづらいです。限界を究めるブログです。までSNSTwitterGitHubHomepageBlog連載リストプライバシーポリシースターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。