この記事の内容は非常に基本的なもので、主に私のような初心者向けなので、すべてのアルゴリズム皇帝にすぐに見てもらいます
引用
ラインセグメント1（a、b）およびラインセグメント2（c、d）は、ABCDがエンドポイントであることが知られており、ラインセグメントの交差点Pを見つけます。 （並列またはコリニアはばらばらと見なされます）
アルゴリズム1：2つの線セグメントが配置されている直線の交差点を見つけてから、交差点が2つの線セグメントにあるかどうかを判断します。
直線の交差点を見つけるとき、直線の+c = 0のax+c = 0の一般的な方程式を通してそれを見つけることができます（方程式のABCは上記のエンドポイントではなく係数です。さらに、ポイント斜め方程式と斜めのインターセプト方程式も使用できます。
次に、交差点とラインセグメントの終点間の位置関係に基づいて、交差点がラインセグメントにあるかどうかを判断できます。
式は次のとおりです。
<code>関数SegmentsIntr（a、b、c、d）{ /** 1線形方程式のシステムを解き、ラインセグメントの交点を見つけます。 **/ //分母が0の場合、それは平行またはコリニアであり、var分母=（by -ay）*（dx -cx） - （ax -bx）*（cy -dy）を交差させません。 if（denominator == 0）{return false; } //ラインセグメントが配置されている直線の交差点（x、y）var x =（（bx -ax） *（dx -cx） *（cy -ay） +（by -ay） *（dx -cx） *（dy -cy） *（bx -ax） * cx） / var y = - （（by -ay） *（dy -cy） *（cx -ax） +（bx -ax） *（dy -cy） * ay-（dx -cx） *（by -ay） * cy） / denominator; / ** 2交差点が2つのセグメントにあるかどうかを判断します//交差点に戻るp return {x：x、y：y}} //それ以外の場合、nisjoint return false} </code>アルゴリズムには最初に明確でわかりやすいアイデアがありますが、そのパフォーマンスは高くありません。交差点が（オンラインセグメントで）有効であるかどうかが不明になる前に交差点を計算するため、多くの時間がかかります。
交差点が最終的に無効であることがわかった場合、以前の計算は無駄になります。さらに、計算プロセス全体も非常に複雑です。
それで、最初に効果的な交差点があるかどうかを判断してから計算する方法はありますか？
明らかに答えはイエスです。したがって、いくつかのアルゴリズムが見つかりました。
アルゴリズム2：各ラインセグメントの2つのエンドポイントが他のラインセグメントの両側にあるかどうかを判断します。次に、2つの線セグメントが配置されている直線の交差点を見つけます。そうしないと、交差しません。
最初のステップは、特定のラインセグメントの両側に2つのポイントがあるかどうかを判断することです。通常、投影方法を使用できます。
ラインセグメントの通常のベクトルを見つけてから、ポイントを通常のラインに投影し、最後に投影位置に基づいてポイントとラインセグメントの関係を判断します。
下の写真を参照してください
ポイントAとポイントBの通常のラインセグメントCDの投影を図に示します。この時点では、通常のラインにラインセグメントCDを投影する必要があります（ポイントCまたはポイントDのいずれかを選択するだけです）。
主に参照に使用されます。
図では、ポイントAとポイントBの投影はポイントC投影の両側に投影され、ラインセグメントABのラインセグメントCDの両側を示しています。
同様に、CDが再びラインセグメントABの両側にあるかどうかを判断するだけです。
正規、投影、その他のものを見つけることは非常に複雑に聞こえますが、実際には私にとっては非常に複雑です。数ヶ月前に幾何学の知識についてあまり知りませんでした（勉強していたときに幾何学の知識をすべて忘れていました： '（）'
幸いなことに、学習と実装は複雑ではなく、従うべき式があります。
ラインセグメントabの通常を見つけます：
var nx = by -ay、ny = ax -bx; var normalline = {x：nx、y：ny};注： normalLine.xとnormalLine.yの幾何学的な意味は、座標ではなく、通常の線の方向を表します。
通常の行でポイントCの投影位置を見つけます。
var dist = normalline.x*cx + normalline.y*cy;
注：ここの「投影位置」はスカラーで、投影点の座標ではなく、通常の起源までの距離を表します。
通常、この距離を知るのに十分です。
図のポイントA（dista）、ポイントB（distb）、およびポイントC（distc）の投影を計算した後、それぞれのサイズに基づいて相対位置を簡単に判断できます。
dista == distb == distcの場合、2つのセグメントはコリネアです
dista == distb！= distcの場合、2つの線セグメントは平行です
distaとdistbがdistcの同じ側にある場合、2つの線セグメントは交差しません。
distaとdistbがdistcの反対側にある場合、2つのラインセグメントが交差するかどうかは、ポイントCとラインセグメントABの関係が再び判断する必要があります。
前の手順では、「ラインセグメントが交差するかどうかを判断する」のみを実装します。結果が真の場合、交差点をさらに見つける必要があります。
後で交差点を見つけるプロセスについて話しましょう。まず、このアルゴリズムの完全な実装を見てみましょう。
関数segmentsintr（a、b、c、d）{//通常のn1 var nx1 =（by -ay）、ny1 =（ax -bx）; //通常のn2 var nx2 =（dy -cy）、ny2 =（cx -dx）; // 2つの法線が乗算され、結果が0の場合、ラインセグメントABとセグメントCDが平行または共線であり、VAR分母= NX1*NY2 -NY1*NX2を交差させないことを意味します。 if（denominator == 0）{return false; } //通常のn2の投影var distc_n2 = nx2 * cx + ny2 * cy; var dista_n2 = nx2 * ax + ny2 * ay-distc_n2; var distb_n2 = nx2 * bx + ny2 * by-distc_n2; //ポイントaとポイントbの投影は、ポイントC投影の同じ側にあります（ラインセグメントの場合、この例はばらばらとして扱われます）。 if（dista_n2*distb_n2> = 0）{return false; } // //ポイントCポイントDとラインセグメントABの関係を判断すると、原理は上記と同じですvar distc_n1 = nx1 * cx + ny1 * cy-dista_n1; var distd_n1 = nx1 * dx + ny1 * dy-dista_n1; if（distc_n1*distd_n1> = 0）{return false; } //交差点座標を計算しますvar fraction = dista_n2 /分母。 var dx = fraction * ny1、dy = -fraction * nx1; return {x：ax + dx、y：ay + dy}; }最終的に交差点の座標を見つけるために使用される方法は、少し奇妙に見え、目立たないように感じます。
実際、それはアルゴリズム1のアルゴリズムに似ています。ただし、それの計算項の多くが事前に計算されていることを除きます。
言い換えれば、2マイルの交差点の座標を見つけるアルゴリズムの部分は、実際には直線の線形方程式でできています。
次に、アルゴリズム1とアルゴリズムをシンプルでラフで非科学的な方法で比較しましょう。
1。最良の場合、2つのアルゴリズムの複雑さは同じです
2。最悪の場合、アルゴリズム1とアルゴリズム2の計算量はほぼ同じです
3.ただし、アルゴリズム2はより多くの「初期条件」を提供するため、平均して、アルゴリズム2の方が良いはずです。
実際のテストの後、実際の状況は確かにそうです。
2つの以前のアルゴリズムは基本的に一般的であり、ほとんどの状況に対処できます。しかし、実際、より良いアルゴリズムがあります。
これは私が最近学んだことです（私は今それを学んで、今それを売った、気にしないでください...）
アルゴリズム3：各ラインセグメントの2つのエンドポイントが他のラインセグメントの両側にあるかどうかを判断します。 2つの線セグメントが配置されている直線の交差点を見つけた場合、それ以外の場合は交差しません。
（ハァッ？なぜアルゴリズム2と同じと感じられるのか？
いわゆるアルゴリズム3は、実際にはアルゴリズム2の単なる改善です。主な改善は次のとおりです。
ポイントとラインセグメント間の位置関係は、通常の投影によってはなく、ポイントとラインセグメントで構成される三角形の面積によって判断されます。
最初に三角形の領域式を確認しましょう。3つのポイントA（x、y）b（x、y）c（x、y）c（x、y）は次のとおりです。
<code> var triarea =（（ax -cx） *（by -cy） - （ay -cy） *（bx -cx）） /2; </code>
2つのベクトルフォーキング== 2つのベクトルで構成される平行四辺形の面積（2つのベクトルが隣接する側）であるため、上記の式を理解するのは難しくありません。
さらに、ベクターには方向があるため、その領域には方向もあります。通常、私たちは反時計回りを正であり、時計回りとして否定的に使用します。
改善されたアルゴリズムの重要なポイントは次のとおりです。
「ラインセグメントABおよびポイントC」によって形成された三角形の領域の正と負の兆候が、「ラインセグメントABおよびポイントD」によって形成された三角形領域と異なる場合
次に、ポイントCとポイントDは、ラインセグメントABの両側に配置されます。
下の図に示すように：
図の点線で示される三角形は、異なる巻線方向（3つの側面の定義の順序）を持っているため、領域の正と否定的なシンボルは異なります。
最初にコードを見てみましょう：
シンボルを判断する必要があるため、前の三角形領域の式で次のものを2で分割する必要はありません。
関数segmentsintr（a、b、c、d）{//三角形の領域の2倍abc var area _abc =（ax -cx） *（by -cy） - （ay -cy） *（bx -cx）; //トライアングルの領域の2倍abd var area _abd =（ax -dx） *（by -dy） - （ay -dy） *（bx -dx）; //領域のシンボルが同じ場合、2つのポイントが同じ側で交差しません（行セグメントのポイントの場合、この例は否定として扱われます）。 if（area_abc*area_abd> = 0）{return false; } //三角形の領域の2倍//三角形の領域の2倍//注：ここには小さな最適化があります。式で領域を計算する必要はありませんが、3つの既知の領域を追加および減算することで導出されます。 var area_cdb = reagy_cda + area_abc -area_abd; if（area_cda * area_cdb> = 0）{return false; } //交差点座標を計算しますvar t = area_cda /（area_abd- area_abc）; var dx = t*（bx -ax）、dy = t*（by -ay）; return {x：ax + dx、y：ay + dy}; }最後に、交差点座標を計算する部分はアルゴリズムと同じです。
アルゴリズム2に基づいて、アルゴリズム3は計算手順を大幅に簡素化し、コードがより合理化されます。 3つのアルゴリズムの中で最高であると言えます。同じことが実際のテスト結果にも当てはまります。
もちろん、私たちは正直でなければなりません。JavaScriptでは、3つのアルゴリズムの時間の複雑さは、実際には通常の計算（特にV8エンジンの下）で類似しています。
私のテストケースでは、3つのアルゴリズム間のギャップを広げるために、異常な百万レベルのラインセグメント交差点テストも実施しました。
要約します
しかし、卓越性と学習を目指して努力するという態度により、より良いアルゴリズムを追求することは常にその肯定的な重要性を持っています。上記は、JSを使用してラインセグメントの交差点を達成するいくつかのアルゴリズムです。コンテンツはそれほど深遠ではありません。 JSを学ぶことは誰にとっても役立つことを願っています。