How to tell WHETHER two line segments intersect from the coordinates of both line segments only? I have to write a function that calculates which of the lines of the polygon (shown in the picture), if any, will be intersected by a user-drawn line.
Given the polygon below...
I. polygon with line
These are the coordinates for the Polygon: const polygonPoints = [ {x: 100, y: 100}, {x: 200, y: 50}, {x: 300, y: 50}, {x: 400, y: 200}, {x: 350, y: 250}, {x: 200, y: 300}, {x: 150, y: 300}, ]
And for example sake, here are the coordinates for the user-drawn line: [{"x":13,"y":276},{"x":480,"y":84}]
II. polygon with user drawn line coordinates
How would one determine which of the lines of the Polygon would be intersected based on only the coordinates alone? i.e without drawing the polygon and the user drawn line out on a graph
Additional context: Background and motivation - the background is that computers need to be able to check whether lines intersect without the freedom to draw it out oon a graph, by hand, making it relevant to motion tracking and 2d/3d space detection. Your current progress - my current progress is trying to take the x and y coordinates of both lines and seeing whether there is a pattern between the ones that do appear to intersect and the ones that don't. However I am sure there is a mathematical solution to this that I do not know which is much easier.
 A: Plug the coordinates of every vertex in turn in the implicit line equation, to get $n$ numbers
$$ax_i+by_i+c$$
If all these numbers have the same sign, there is no intersection. There is no shortcut, in general you have to try all vertices. (More precisely, the number of changes of sign tells you the number of intersection points. Intersections occur along the edges with a change of sign.)

If the polygon is known in advance to be convex, you can solve this faster, as the angle between the sides and the line varies periodically and makes only two changes of sign. You can find one by dichotomic search, and this allows you to test for intersection by looking at just $O(\log n)$ vertices instead of $O(n)$. This is only worth for large $n$.

Addendum:
If the line is given by two points, you can solve this easily with complex arithmetic. Consider the transformation
$$T(z)=\frac{z-z_0}{z_1-z_0}$$ which applies $z_0$ to the origin and $z_1$ to $(0,1)$, hence the line to the axis $x$.
Now for every vertex you consider $\Im(T(v_i))=\Im(w_i)$ and detect the changes of sign between two consecutive transformed vertices. When one occurs, the coordinates of the intersection point are
$$w_i-\Im(w_i)\frac{w_{i+1}-w_i}{\Im(w_{i+1}-w_i)}$$ (as you can check, the imaginary part is zero). That point belongs to the segment iff its abscissa lies in $[0,1]$.
The inverse transformation is easy:
$$T^{-1}(z)=(z_1-z_0)z+z_0.$$
A: If you have a line in the form $ax+by+c=0$ it can be easily verified if two points lie on the same side of the line or on the opposite sides:
say points are $P_1(x_1,y_1)$ and $P_2(x_2,y_2)$ -- if $ax_1+by_1+c$ and $ax_2+by_2+c$ have the same sign, the points lie on the same side (and segment $P_1P_2$ do not intersect the line), if different signs, then $P_1$ and $P_2$ are on the different sides of the line.
How to build the normal equation $\mathbf{n}.(\mathbf{x}-\mathbf{a})=0$ passing through points $\mathbf{a}(a,b)$ and $\mathbf{b}(c,d)$:
the directing vector of the line will be $\mathbf{b}-\mathbf{a}=(c-a,d-b)$ and a normal vector will be then $\mathbf{n}=(-(d-b),c-a)$.
Then the equation of the line will be $\mathbf{n}.(\mathbf{x}-\mathbf{a})=0$ $\Leftrightarrow$
$$-(d-b)(x-a)+(c-a)(y-b)=0$$
However, if we need to know if a segment intersect with another, then we need to parametric form $\mathbf{x}=\mathbf{a}+t\mathbf{l}$ of both too and ensure that $t$ are within some margins (usually $0\le t\le 1$).
A: Here is how I would do it.
We have two lines: the user's line $AB$ between points $(A_x,A_y)$ and $(B_x,B_y)$, and an edge $PQ$ of the polygon between points $(P_x,P_y)$ and $(Q_x,Q_y)$.
We want to transform $AB$ into $A'B'$, where $A'$ and $B'$ have a simple form: specifically, $A'=(0,0)$ and $B'=(\beta,0)$ for some $\beta$. We then transform $PQ$ into $P'Q'$ using the same transformation. And now, because of the simple forms of $A'$ and $B'$, it is a simple matter to check whether $A'B'$ and $P'Q'$ intersect.
So: first we translate all points by subtracting $(A_x,A_y)$ from them. This sends $A$ to $(0,0)$, which is what we want:
$$A''=(0,0)$$
$$B''=(B_x-A_x,B_y-A_y)$$
$$P''=(P_x-A_x,P_y-A_y)$$
$$Q''=(Q_x-A_x,Q_y-A_y)$$
Now we could rotate $A''B''$ to bring $B_y''$ onto the $x$-axis, but it is computationally simpler to perform a vertical shear transformation to achieve the same thing. This transforms the point $(v,w)$ to the point $(v,w-\lambda v)$ for some $\lambda$; to bring $B''$ down onto the $x$-axis we choose
$$\lambda=\frac{B_y''}{B_x''}$$
so that $B'=(B_x'',B_y''-\lambda B_x'')$ has a $y$-coordinate of $0$.
At this point, it simplifies the exposition if we assume that $B_x'$ is positive; so if not, we add a reflection about the $y$-axis to the list of transformations, replacing $B_x'$ with $-B_x'$. (If $B_x'$ is zero, or close to it, we can use a horizintal shear instead $-$ see below.)
Now we compute $P'$ and $Q'$ using the same translation, shear, and reflection. All our transformations preserve the crossedness or not of the two line segments, so finally we just need to check whether the transformed line $P'Q'$ cuts the $x$-axis between $0$ and $B_x'$. For this, we need:

*

*$P_y'$ and $Q_y'$ have different signs; and

*$0<\dfrac{P_x'Q_y'-P_y'Q_x'}{Q_y'-P_y'}< B_x'$.

You only need to compute $\lambda$ once, for the user's line, and you can use it to transform every point on the polygon. This will be very fast, and not too taxing to program.
There are a couple of issues that you will need to address, to do with rounding and overflow.
Firstly, if $B_x''$ is too small, then $\lambda$ might become too big. The solution here is to use a horizontal shear transformation when the line $AB$ is closer to the vertical than the horizontal (i.e. when the absolute value of the slope of $AB$ is greater than $1$).
Secondly, computing $\dfrac{P_x'Q_y'-P_y'Q_x'}{Q_y'-P_y'}$ might lead to overflow issues if $Q_y'-P_y'$ is small. To avoid this, instead of checking whether $\dfrac{P_x'Q_y'-P_y'Q_x'}{Q_y'-P_y'}< B_x'$, you can check whether $P_x'Q_y'-P_y'Q_x' < (Q_y'-P_y')B_x'$ (except that you have to swap the sense of the comparison if $Q_y'-P_y'$ is negative).
