JavaScript幾何学アルゴリズム

JavaScript は広く使用されているプログラミング言語であり、さまざまな用途に使用できます。その 1 つは幾何学的アルゴリズムの処理です。この記事では、いくつかのJavaScript幾何アルゴリズムの基本的な内容と実装方法を紹介します。

1. 点とベクトル

ジオメトリでは、点とベクトルは最も基本的なプリミティブです。 JavaScript では、配列を使用して点とベクトルを表すことができます。点は 2 つの要素を含む配列で表され、最初の要素は x 座標を表し、2 番目の要素は y 座標を表します。たとえば、[1,2] は (1,2) にある点を表します。ベクトルも 2 つの要素を含む配列ですが、座標ではなく長さと方向を表します。たとえば、[3,-4] は長さ 3 で第 2 象限を向いたベクトルを表します。ベクトル減算により、点 A (1,2) と点 B (4,6) 間のベクトルは [3,4] のように、2 点間のベクトルを計算できます。

2. 内積と外積

内積と外積は、2 次元ジオメトリで最も一般的に使用される 2 つの演算です。ドット積は、2 つのベクトルの対応する要素の積の合計です。たとえば、ベクトル A[2,3] と B[4,5] のドット積は 24 35= です。 23.ドット積を使用してベクトル間の角度のコサイン値を計算できます。これはコサイン公式で取得できます:

cosθ = A·B / |A||B|

ここで、 |A| と |B | はそれぞれベクトルのモジュール長を表し、 |A||B| はそれらの積を表します。外積は 2 つのベクトルによって形成される平行四辺形の面積です。計算式は次のとおりです:

A × B = |A||B| sinθ

ここで θ は夾角を表します。外積の結果はスカラーであり、その方向はベクトルの次数に依存し、右手の法則で方向を決定できます。

JavaScript では、内積と外積の計算は比較的単純で、配列の乗算、加算、および剰余メソッドを使用するだけで実行できます。

3. 線分と線分

線分と線分は一般的な幾何学オブジェクトであり、JavaScript では配列で表すこともできます。直線は点とベクトルで表現する必要があります。たとえば、直線 L: y=2x 1 は [1,1],[2,4] と表現できます。最初の点は上の任意の点です。 2 番目の A ベクトルは直線の方向ベクトルです。線分は 2 つの点で表す必要があります。唯一の違いは、始点と終点があることです。たとえば、線分 AB は [1,2],[4,6] と表すことができます。

JavaScriptでは、点が直線上にあるかどうかを判断することで、点と直線の間の距離を計算できます。点が線分上にあるかどうかを判断するには、その点が線分の延長線上にあるか、線分の 2 つの端点の間にあるかどうかを判断する必要があります。

4. 円と長方形

円と長方形は一般的な 2 次元の幾何学オブジェクトであり、配列で表すこともできます。円は円の中心の座標と半径で定義でき、例えば半径3の円O(1,2)は[1,2,3]と表現できます。長方形は左上隅と右下隅の座標で定義できます。たとえば、長方形ABCDの左上隅の座標は(1,2)、右下隅の座標は(3,4)です。 )、[1,2,3,4] として表すことができます。

JavaScript では、点が円内にあるかどうかを判断するために、円の中心からの距離が半径より小さいかどうかを計算できます。点が長方形内にあるかどうかを判断するには、その点が長方形の 4 つの辺で囲まれた領域内にあるかどうかを判断できます。

5. 最近接点ペア問題

最近接点ペア問題とは、一連の点の中から最も近い 2 つの点を見つけることを指します。この問題は、計算幾何学、コンピューター ビジョン、機械学習に応用できます。 JavaScript では、ブルート フォース アルゴリズムと分割統治アルゴリズムを使用して最近点ペア問題を解決できます。ブルート フォース アルゴリズムの時間計算量は O(n^2) であり、大規模データには適していませんが、分割統治アルゴリズムの時間計算量は O(n log n) であり、大規模データには適しています。さまざまなサイズのデータ​​。

分割統治アルゴリズムの基本的な考え方は、すべての点を x 座標に従って並べ替え、次にそれらを 2 つの部分に分割し、左右の最近接点ペアの問題を処理することです。それぞれのパーツ。次に、左側と右側の部分の最近接点のペアの中から最小の距離 d を選択し、距離が d である近傍点の中で最短距離を見つけます。

JavaScript では、並べ替えアルゴリズムを使用してすべての点を並べ替えてから、左部分と右部分の最近接点ペアの問題を再帰的に処理できます。具体的な実装については、コード ベースの例を参照してください。

まとめ

この記事では、JavaScript で幾何学的アルゴリズムを処理するための基本と実装方法を紹介しました。これらには、点とベクトルの表現、ドット積と外積の計算、線分と線分の表現、円と長方形の表現、最近接点ペア問題の解決法が含まれます。これらの基本を学ぶことで、幾何学的アルゴリズムをよりよく理解し、適用できるようになります。

以上がJavaScript幾何学アルゴリズムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。