# Find intersection point of line with 2D polygon

I am scratching my head in order to find the formula of the following problem.

As shown in the following image, I have the coördinates of 2 points to draw a straight line (green dots + line). Next, I have a 2D Polygon of which I have multiple coördinates (red dots).

I would like to find the formula to determine whether or not the green line intersects with the polygon. Preferably at the yellow dot.

• If you don't have the coordinates of the vertex just below the yellow dot you will not have a formula for the position of the yellow dot, though you can still show that the line intersects the polygon. – David K Apr 3 at 13:45
• Assume that I have, what would the formula be? Also, how to show that the line intersects the polygon with the information provided in my original question? – RazorAlliance192 Apr 3 at 15:27
• Have you tried an internet search for “line-polygon intersection?” – amd Apr 3 at 20:52
• Do you have the equations for the lines? All the vertices defined? – Moti Apr 4 at 2:11

## 1 Answer

I am not sure if there is a "formula", but there are algorithms.

Here is one (I do not guarantee it is the most efficient). Let the two green points be $$A = (x_A, \, y_A)$$ and $$B = (x_B, \, y_B)$$. Let the polygon be presented as an ordered sequence of its vertices $$\big(\,P_1, \,\, P_2, \,\, P_3, \,\, ...,\,\, P_n, \,\, P_1\, \big)$$ where $$P_i = (x_i, \, y_i)$$ for $$i=1,...,n$$.

Step 1: With the help of the points $$A$$ and $$B$$ construct a vector perpendicular to the green line $$AB$$: $$\vec{n} = (a ,\, b) = \big(\,y_A - y_B,\,\, x_B - x_A\,\big)$$ where $$\, a = y_A - y_B\,$$ and $$\, b = x_B - x_A\,$$. Then, for any point $$P = (x, \, y)$$ from the plane, define the dot product \begin{align} \vec{n} \, \cdot\, \vec{AP} &= {(y_A - y_B)(x - x_A) \, + \, (x_B - x_A)(y - y_A)}\\ \end{align} We use this dot product because the line $$AB$$ splits the plane into two half-planes and if $$P$$ is in the half in which the vector $$\vec{n}$$ points, $$\vec{n} \, \cdot\, \vec{AP} > 0$$. If $$P$$ is in the other half-plane, $$\vec{n} \, \cdot\, \vec{AP} < 0$$. Finally, $$P$$ lies on the line $$AB$$ if and only if $$\vec{n} \, \cdot\, \vec{AP} = 0$$

Step 2: For a given index $$i \in \{1, ..., n\}$$: Calculate $$\vec{n} \cdot \vec{AP}_i$$ and $$\vec{n} \cdot \vec{AP}_{i+1}$$.

Step 3: If the product $$\big(\,\vec{n} \cdot \vec{AP}_i\,\big) \big(\,\vec{n} \cdot \vec{AP}_{i+1} \, \big) \, < \, 0$$, then the two vertices $$P_i$$ and $$P_{i+1}$$ are on opposite sides of the line $$AB$$ and therefore the side $$P_iP_{i+1}$$ of the polygon intersects the line $$AB$$. Procede to Step 4.

Step 4: In the case of $$AB$$ intersect $$P_{i}P_{i+1}$$, in order to find the intersection point $$Q \, = AB \, \cap \,P_iP_{i+1} \,$$ of the lines $$AB$$ and $$P_iP_{i+1}$$, you have to solve the system of linear equations \begin{align} & (y_A - y_B\,)\, x \, + \, (x_B - x_A)\, y = x_B \, y_A - y_B\,x_A \,\,\, (\text{ equation of line AB })\\ & (y_i - y_{i+1})\, x + (x_{i+1} - x_i)\, y = x_{i+1}\,y_{i} - y_{i+1}\,x_i \,\,\, (\text{ equation of line P_{i}P_{i+1} }) \end{align} The solution to this system gives you the intersection point $$Q = (x_Q, \, y_Q)$$, where by Cramer's rule: \begin{align*} &x_Q = \frac{\begin{vmatrix} (x_B \, y_A - y_B\,x_A) & (x_B - x_A) \\ (x_{i+1}\,y_{i} - y_{i+1}\,x_i) & (x_{i+1} - x_i) \end{vmatrix}}{\begin{vmatrix} (y_A - y_B\,) & (x_B - x_A) \\ (y_i - y_{i+1}) & (x_{i+1} - x_i)\end{vmatrix}} \\ &\\ &y_Q = \frac{\begin{vmatrix} (y_A - y_B\,) & (x_B \, y_A - y_B\,x_A) \\ (y_i - y_{i+1}) & (x_{i+1}\,y_{i} - y_{i+1}\,x_i) \end{vmatrix}}{\begin{vmatrix} (y_A - y_B\,) & (x_B - x_A) \\ (y_i - y_{i+1}) & (x_{i+1} - x_i)\end{vmatrix}} \end{align*}

Step 5: Calculate the square distance between point $$A$$ and $$Q$$: $$\,|AQ|^2 = (x_Q - x_A)^2 + (y_Q - y_A)^2$$.

Step 6: If the newly calculated $$|AQ|^2$$ is less than the one between $$A$$ and the point $$\tilde{Q}$$ already recorded from the previous steps, then record $$Q$$ as the new point in place of $$\tilde{Q}$$, together with $$|AQ|^2$$. Then Increase the index $$i$$ by $$1$$, i.e. $$i \mapsto i+1$$ and go back to Step 2.

Step 7: Else if the product $$\big(\,\vec{n} \cdot \vec{AP}_i\,\big) \big(\,\vec{n} \cdot \vec{AP}_{i+1} \, \big) \, > \, 0$$, simply increase the index $$i$$ by $$1$$, i.e. $$i \mapsto i+1$$ and go back to Step 2.

Step 8: Else if $$\vec{n} \cdot \vec{AP}_i = 0$$ and $$\vec{n} \cdot \vec{AP}_{i+1} \neq 0$$, then the line $$AB$$ passes through the vertex $$P_i$$, so $$Q = P_i$$. Return to Step 6.

Step 9: Else if $$\vec{n} \cdot \vec{AP}_i = 0$$ and $$\vec{n} \cdot \vec{AP}_{i+1} = 0$$, then the edge $$P_{i}P_{i+1}$$ is aligned with the line $$AB$$ i.e. the latter passes through both vertexes $$P_i$$ and $$P_{i+1}$$, so check which is closer to point $$A$$ and do as in Step 6, i.e. determine if you need to set any of $$P_i$$ or $$P_{i+1}$$ as the new point $$Q$$. Then increase the index by $$2$$, , i.e. $$i \mapsto i+2$$ and go back to Step 2.

After the index $$i$$ has reached value $$n$$, you should have the yellow point you want.