How to find the intersection of lines?

Question

Mathematics

I write code in c++. Points x, y are entered and they are sequentially connected (a laminar line comes out). We need to find out how many times it crosses itself.

In the code, I find the equations for the line (for example) AB and then for CD (for example, the first and second are not compared, only after). I find the determinant, etc. until I find the intersection points of the lines.
The problem is that EF does not intersect CD and CB, but it kind of continues itself, and if it continues, it will intersect.
How to fix it? Maybe you need to find its length? Suggestions can be made in your own words or mathematically, no code is needed, I will write it myself. Thanks in advance.

Answer 1

Here's a pseudocode for you to determine if the segments intersect.

The code

программа пересечение двух отрезков <вх:ax,ay,bx,by,cx,cy,dx,dy:R>:Q
 дано    : | концы первого отрезка (ax, ay) и (bx, by)
           | концы второго отрезка (cx, cy) и (dx, dy)
 получить: | ответ = отрезки пересекаются да/нет
 ____________
  | A(ax, bx) B(bx, by) C(cx, cy) D(dx, dy)
  v1x := bx - ax | вектор AB
  v1y := by - ay
  v2x := cx - ax | вектор AC
  v2y := cy - ay
  v3x := dx - ax | вектор AD
  v3y := dy - ay
  v4x := dx - cx | вектор CD
  v4y := dy - cy
  v5x := bx - cx | вектор CB
  v5y := by - cy
  v6x := ax - cx | вектор CA
  v6y := ay - cy
  coord1 := v1x * v2y - v1y * v2x | [AB, AC]
  coord2 := v1x * v3y - v1y * v3x | [AB, AD]
  coord3 := v4x * v5y - v4y * v5x | [CD, CB]
  coord4 := v4x * v6y - v4y * v6x | [CD, CA]
  ответ := (coord1 * coord2 <= 0 и coord3 * coord4 <= 0)
конец программы

Answer 2

Think right. Find the points of intersection of the lines. And then check these points for belonging to the segment. Those. point coordinates must belong to the range of line segment coordinates. min(Ax, Bx) <= x <= max(Ax, Bx). Same for the ordinate.

Answer 3

There is a simpler way: e-maxx.ru/algo/segments_intersection_checking (through oriented areas of triangles), but it does not find the intersection point itself, it only says whether the segments intersect or not.