線分の交差判定と交点特定 - Qiita

はじめに 二つの折れ線グラフがある時、そのグラフの交点を探したいことがあります。こんな感じです。 典型的には異なるサイズのBinder比の交点を見つける時とかに必要です。で、そのためには「二つの線分の交差判定」をするコードと「交差する二つの線分の交点」を求めるコードが必要になるのですが、なんかこれ、必要になる度に毎回書いている気がするので、以下では交差判定と交点を求めるアルゴリズムを真面目に導出して、それをコードに落としてCC0で公開しました。 https://github.com/kaityo256/find_intersection なお、線分直上に点があったり、二つの線分が平行だったりといった条件は考慮していないので注意。また、やや冗長に書いているので、高速化が必要な場合は適宜修正してください。 二つの線分の交差判定 4つの点、$P_1$, $P_2$, $P_3$, $P_4$があ