1
$\begingroup$

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.

image

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – David K Apr 3 at 13:45
  • $\begingroup$ 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? $\endgroup$ – RazorAlliance192 Apr 3 at 15:27
  • $\begingroup$ Have you tried an internet search for “line-polygon intersection?” $\endgroup$ – amd Apr 3 at 20:52
  • $\begingroup$ Do you have the equations for the lines? All the vertices defined? $\endgroup$ – Moti Apr 4 at 2:11
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.