3

これに対する最善の解決策は何だろうと思っています。マウスがクリックされたときに、Web ページ上の最も近いハイパーリンクを返して表示します。

この例には 3 つDIVの があります。それぞれにハイパーリンクが含まれています。.のない別のハイパーリンク (ハイパーリンク D) もありDIVます。そして、赤い点がマウスクリックだとしましょう。

例えば

私が考えることができる解決策は、次のようにしてすべてのリンクを反復処理することです

    var a_list = document.getElementsByTagName("a");

次に、距離方程式 を使用して距離を計算しc^2 = a^2 + b^2ます。

    var a_list = Array.prototype.slice.call(document.getElementsByTagName("a"))
    for( var i = 0 ; i < a_list.length; i++){
          Math.sqrt(Math.pow(mouseX - a_list[i].getBoundingClientRect().left,2) + 
                    Math.pow(mouseY - a_list[i].getBoundingClientRect().top,2))

    }

このアプローチは確かに O(N) 時間の複雑さを要します。ここで、N は私たちが持っているリンクの数です。もっとうまくやれるか？

4

4 に答える 4

2

各リンクをチェックする必要があるため、O(N) よりも高速にこれを行うことはできません。

このチェックを何度も行う場合 (たとえば、マウスを動かすたびに最も近いリンクを強調表示する場合)、より高速なアルゴリズムを思いつくことができます。しかし、それらには単純なチェックよりも悪い1回限りの起動コストがあります.

それが O(N) アルゴリズムであることは本当に重要ですか? それは十分に速くありませんか？

アルゴリズムに関する注意事項:

  • 高価な平方根計算を省略できます。代わりに「距離の二乗」値を比較できますが、どちらが近いかがわかります。何かのために本当に距離が必要な場合は、最も近いリンクを見つけた後、最後に一度平方根を取ります
  • リンクのどのコーナーがマウスに最も近いかを確認する必要があります。盲目的に左コーナーを使用しないでください。つまり、X 方向の場合:
    • mouseX < link.left の場合、(mouseX - link.left)^2 を使用します
    • mouseX > link.right の場合、(mouseX - link.right)^2 を使用します
    • それ以外の場合は 0 を使用
    • ...そして同様に Y 方向についても。
  • 最初に delta_y^2 を計算し、それを「これまでの最良の距離^2」の値と比較できます。それより大きい場合、delta_x^2 を計算する必要はありません。ブラウザ、CPU、および残りのコードによっては、これにより高速になる場合とそうでない場合があります。
于 2012-09-01T19:26:23.540 に答える
2

これはnearest neighbor、2 次元の n ポイントのセット S とクエリ ポイント q があるような質問のように見えます。S のどの点が q に最も近いか。

それほど多くのリンクを扱っていない場合（100リンク未満）、単純なアプローチが最適だと思います（今持っているものです。それぞれをスキャンして距離を計算し、最小のものを取ります）。数千または数百万のリンクがある場合 (めったに起こりません)、後でクエリを実行するために必ずキャッシュする必要があります。これにより、クエリの時間が確実に短縮されます。

  • 1 つの方法 (あなたのやり方) は、すべてのリンクを取得し、それらを X 座標で並べ替えることです。Y 座標は今のところ気にしません。次に、X でバイナリ検索を実行すると、次のいずれかになります。リンクしますが、それは最も近いものではない可能性があります。それでも、前のものと次のものを距離で比較する必要があります (Y 座標を使用します)。たとえば、あなたの例から、その赤い点の X 座標 (マウスがクリックされた位置) がハイパーリンク D よりも大きいため、X でバイナリ検索を実行すると、その後すべてが検索されますが、ハイパーリンク D が最も近い可能性があります。したがって、考慮する必要があります。このアプローチでは、ソートに O(N log N)、O(N) のスペース、およびクエリに O(log N) が必要です。

  • Kd Treeも使用できます。少数の次元 (この場合は x と y の 2 つの次元のみ) でうまく機能し、クエリ ポイント p (マウスでクリックした位置) を含むセルを効率的に検索できます。
    構築時間 O(N log N)、スペース O(N)、クエリ時間: O(n^1/2 + k)

  • 私が考えることができる別の方法は、ボロノイ図を作成することです。これは、最近傍クエリに効率的なデータ構造を提供し、2 次元に最適です。
    構築時間 O(N log N)、スペース O(N)、クエリ時間: O(log n)

したがって、ほとんどすべてのアプローチは同じです。

于 2012-09-02T16:09:46.407 に答える
1

事前にリンク リストを作成できる場合 (つまり、スクロールしないか、スクロール時に再構築する)、タイリングを検討することをお勧めします。

たとえば、タイリング係数が 0.5 の場合、リンクを次のように分類します。

  • 画面左 0.25
  • 画面左 0.5
  • 画面の左 0.25 ～ 0.75 インチ
  • 画面の左 0.5 ～ 1.0 (= 右 0.5)
  • 画面の左 0.75 ～ 1.0 (= 右 0.25)

垂直方向も同様です。

クリックすると、クリックした場所と重なるタイル内のリンクを確認するだけで済みます。最も近いリンクから非常に離れている場合、これは明らかに「何も」与えませんが、これはあなたが望むものかもしれません.

于 2012-09-01T19:13:45.180 に答える
1

それで、あなたはその1ページを持っていて、さまざまなマウス位置の計算をしていると思いますか?

その場合、最初のセットアップaで、x でソートされた s を保持する 2 つのリストを作成できます。左のy方向、それぞれ。トップ値。次に、マウスイベントの x resp を使用します。y座標これらのリストで次のように検索を開始できます-x座標について説明します：

s の完全なリストから始めて、リストのa中央にある要素の left-value と mouse-x を比較します。x が小さい場合は、最初から中央の要素までリストを使用して繰り返します。x == 左の値の場合は完了です。x が大きい場合は、リストを中央から最後まで繰り返します。x == left-value または検索するリストの長さが 1 つまたは 2 つの要素しかない場合は、2 つのうち近い方を使用します。

y座標についても同じことを行う必要があります（一種の平行）。

これは完全に考え抜かれたわけではありませんが、そのようなもので、a毎回すべてのタグと比較することを避けることができると確信しています.

于 2012-09-01T19:18:27.530 に答える