Given a 2D point + Bearing and a 2Dpolygon, how to find intersection point

Question

I have a polygon of 2D points. I can test if a point is in/on the polygon. I need to solve the problem of, given a 2D point and a bearing (0 to 360 where 0 is positive y axis going clockwise), find the intersection point, if any.

For example, if my polygon is a square, of [(0,0), (4, 4), (4, 0), (0, 4)], and my point (inside the polygon) is (2, 2) with a bearing of 90 degrees, the intersection point would be (4, 2). If my point is (6, 2), bearing of 270 I would get the same point. Now, if my point (6, 2) and a bearing of 90, I would never intersect the polygon.

I need to program this, so is there any formula, logic that I can use?

I started with the formula for the bearing = atan2(Ix - Px, Iy - Px) where I is unknown intersection, P is known point. But I need one more equation to solve for the 2 unknowns.

Point in polygon

Point outside but intersects

Point outside but no intersection

These pictures outline a very simple example, my polygon may be irregular and my bearing may be anywhere between 0 and 360.

Answer 1

The initial starting point and heading define a ray.

The polygon is made of a bunch of line segments. So what you can do is check if each line segment intersects with your ray.

(To check if a line segment intersects with your ray, extend the line segment and ray into infinite lines and find their intersection.

(Finding the intersection is fairly simple with infinite lines, though you will have some edge cases to handle if the two lines are parallel: you will have either zero points of intersection, or infinitely many.)

To check if the intersection lies on the line segment, use your function that tells you whether or not it lies on the boundary of the polygon. To check whether the intersection lies on the ray, do the following:

Let $P$ be the starting point, let $I$ be the proposed intersection point. Let $\vec{v}$ be the vector pointing from $P$ to $I$. And let $\hat{h}$ be the unit vector pointing in the direction of the heading. Then we want to make sure that $\vec{v}\cdot\hat{h} \geq 0$.)

This will give us a list of points where the ray intersects with the polygon. Either the list is empty, in which case we are done, or the first point of intersection can be found by choosing the point that is nearest to the starting point, $P$.

Answer 2

Essentially, you have to compute the intersections of the ray with all of the polygon edges, for which there are well-publicized algorithms and code snippets, but you can do a bit better.

Let’s assume that the vertices $V_i$ are sorted so that the polygon is traversed in a single direction, either clockwise or counterclockwise. Thus, if you have $n$ vertices, each edge has endpoints $V_i$ and $V_{(i+1)\,\text{mod}\,n}$. It might be convenient to append a second copy of the first vertex to the end of this list to avoid having to treat the last edge as a special case. If the bearing of the ray is $\theta$, its direction vector is $D=(\sin\theta,\cos\theta)$. Set $N = (\cos\theta,-\sin\theta)$. An equation of the line containing this ray is then $$N\cdot(x,y) = N\cdot P.$$ Compute $d_i = N\cdot(V_i-P)$ for each vertex. These values are proportional to the signed distance of the vertices to the line that contains the ray. If the signs of these quantities for neighboring vertices differ, or if either is zero, then you have a potential edge crossing. Using similar triangles, the intersection point can be found by interpolation: $$I = {d_i V_{(i+1)\,\text{mod}\,n} - d_{(i+1)\,\text{mod}\,n} V_i \over d_i-d_{(i+1)\,\text{mod}\,n}}.$$ Since we’ve computed the intersections of a line with the edges, we still have to reject intersections that are “behind” $P$, but that’s a simple matter of comparing the signs of the coordinates of $I-P$ to the ray’s direction vector. Should neighboring $d$-values both be zero, this means that the edge coincides with the line, and you’ll have to deal with that as a special case.

From your example of $P=(6,2)$ and $\theta=270°$, it appears that you might be looking for the first edge crossing. If so, compute $D\cdot(I-P)$ for each potential crossing. The first corresponds to the least nonnegative value.

Applying this method to your examples, the sorted and augmented vertex list is $[(0,0),(4,0),(4,4),(0,4),(0,0)]$. For $\theta = 90°$, $N=(0,-1)$ and the resulting list of $d$-values for $P=(2,2)$ is $[2,2,-2,-2,2]$, indicating potential edge crossings with the second and fourth edges. The first potential crossing point is then $${2(4,4)-(-2)(4,0) \over 2-(-2)} = (4,2)$$ and similarly the second is $(0,2)$. Subtracting $P$ from both of these results in $(2,0)$ and $(-2,0)$, respectively, while the ray’s direction vector is $(1,0)$, so only the first represents an intersection with the ray. With $P=(6,2)$ you get the same potential edge crossings, but now $I-P$ gives $(-2,0)$ and $(-6,0)$, neither of which is in the same direction as $D$. With $P=(6,2)$ and $\theta=270°$, the $d$-value list is $(-2,-2,2,2,-2)$, indicating potential crossings of the second and fourth edges, producing $(4,2)$ and $(0,2)$ again. Computing $D\cdot(I-P)$ for these two points produces $2$ and $6$, respectively, so they are both intersections of the ray with an edge, but $(4,2)$ is the first one.