How to determine if a ray intersects a wedge in 2d space

Question

Assume that I have a ray in 2d space

Assume that I am given a point in this 2d space $P = (p_x, p_y)$

Assume that I have an area $A$ defined as follows:

1. The area is bounded by a minimum distance $r_{min}$ and maximum distance $r_{max}$ from point $P$
2. The area is bounded by a minimum angle $\theta_{min}$ and maximum angle $\theta_{max}$ around the point $P$

How do I find if the ray intersects the area $A$?

EDIT: After a quick google, the shape that the area $A$ forms is similar to python's matplotlib wedge shape, which looks like some of these examples:

EDIT: This is not required to answer the question, but my work requires me also to find the section of the ray that is inside of $A$, if there is an intersection. Finding this will net you brownie points.

Answer 1

I'd proceed as follows. Say your line is of the form: $$ f(x) = ax +b. $$ Call $\tilde{p} = p - b$. What we're doing is 'shifting' the problem (i.e. both your line and $p$) down by $b$ so that your line goes through the origin. Once that's done, we're going to orthogonally project $\tilde{p}$ onto the line (which now runs through the origin), $l = \{c\cdot(1,a) : c \in \mathbb{R}\}$: $$ \textrm{proj}_{l}(\tilde{p}) = \bigg[\frac{\tilde{p} \cdot (1,a)}{(1,a) \cdot (1,a)} \bigg](1,a) $$ The 'residual' vector $u = \tilde{p}-\textrm{proj}_{l}(\tilde{p})$ is the distance-minimizing vector from $\tilde{p}$ to $l$ (rescaled to the origin). If $\|u\| \not \in [r_{min}, r_{max}]$, we immediately know there can be no intersection.

Now, in terms of angles, we again just look at the angle between $u$ and the $x$-axis. We must have $\theta_{u} \in [\theta_{min}, \theta_{max}]$. Thus there is an intersection if: $$ \big(\|u\|, \theta_u\big) \in [r_{min}, r_{max}]\times[\theta_{min}, \theta_{max}]. $$

To find out if there is any intersection though, consider now the line in the plane orthogonal to $u$. This is given by $\tilde{l} = \{\tilde{c}\cdot (1,a) + u : \tilde{c} \in \mathbb{R}\}$. It may be the case that $u$ does not intersect the wedge but some point on $\tilde{l}$ does. Thus the line intersects the wedge if and only if there exists some $\tilde{c} \in \mathbb{R}$ such that the norm and angle of $\tilde{c}\cdot(1,a) + u$ are in $[r_{min}, r_{max}]\times[\theta_{min}, \theta_{max}].$

Moreover, the endpoints of the interval(s) of $\tilde{c}$'s satisfying the above will give you the bounds from your edit.

Answer 2

Translate the line and the wedge simultaneously to bring the wedge center at the origin, and write the equation of the ray in the implicit form

$$ax+by+c=0.$$

Then switch to polar coordinates. The line becomes

$$r(a\cos\theta+b\sin\theta)+c=0$$ a secant curve, while the wedge turns to a rectangle.

The intersection with the constant-$r$ sides are given by

$$R(a\cos\theta+b\sin\theta)+c=0,$$ a classical linear trigonometric equation, and with the constant-$\theta$ sides by

$$r=-\frac c{a\cos\Theta+b\sin\Theta}.$$

You will need to discuss the relevant intervals, but in the polar domain this shouldn't be a big deal.

Answer 3

How much (length) of a straight line is enclosed within the boundaries of a 2-D domain of interest? The answer is: $$ \oint H\left[\cos(\phi)(x-p)+\sin(\phi)(y-q)\right]\left[-\sin(\phi).dx+\cos(\phi).dy\,\right] $$ Here $\oint$ is the contour integral around the domain of interest; $H[\cdots]$ is the Heaviside step function; $\phi$ is the angle of the normal of the straight line with the $x$-axis; $(p,q)$ is just a point on the line.
A picture says more than a thousand words:

More details are found in the section" Sharpened Lines and Contours" at page 10-11 near the end of this PDF document:

• About Inside/Outside Problems

Answer 4

I'm going to answer this question with an algorithm since it sounds as if it is going to be used in a computer program. So I'll treat all variables as if they were variables in a computer program stored in memory.

I assume that $\theta_{min} \leq \theta_{max}$ and that $0 \leq \theta_{max} - \theta_{min} \leq 2 \pi$.

If $\theta_{min} = \theta_{max}$ then this is the question of whether the ray intersects a line segment (if $r_{min} < r_{max}$) or whether it intersects a point (if $r_{min} = r_{max}$) where both of these questions have well known solutions. So we will henceforth that this is not the case and therefore assume that $\theta_{min} < \theta_{max}$.

Suppose that the equation of the (bidirectional) line formed by the ray is $a x + b y + c = 0$ with $a \geq 0$ and that the ray starts at $(x_0, y_0)$.

(1) Shift everything by $-P$: Replace $(x_0, y_0)$ with $(x_0 - p_x, y_0 - p_y)$ and replace $c$ with $c + a p_x + b p_y$. We may now assume that $P$ is the origin $P = (0, 0).$

(2a) If the ray is horizontal (i.e. if $a = 0$) then replace $c$ with $\frac{c}{b}$ and replace $b$ with $1$ (i.e. divide the equation $a x + b y + c = 0$ by $b$).

(2b) If the ray is not horizontal (i.e. if $a \neq 0$) then rotate everything so that it is horizontal: let $\theta_0 = \arctan\left( - \frac{b}{a} \right)$ and $\theta_1 = \frac{\pi}{2} - \theta_0$. Add $\theta_1$ to $\theta_{min}$ and to $\theta_{max}$ (i.e. replace $\theta_{min}$ by $\theta_{min} + \theta_1$ and replace $\theta_{max}$ by $\theta_{max} + \theta_1$). Replace $(x_0, y_0)$ with its rotation about the origin $\left( x_0 \cos \theta_1 - y_0 \sin \theta_1, x_0 \sin \theta_1 + y_0 \cos \theta_1 \right)$. Let $d = \frac{\left| c \right|}{\sqrt{a^2 + b^2}}$, which is the distance from the line to the origin. Replace $a$ with $0$, $b$ with $1$, and $c$ with $d$.

At this point, $a = 0,$ $b = 1,$ and $P = (0, 0)$.

(3) Let $h$ be the smallest $y$-value of the wedge and let $H$ be the largest, which we find as follows:

(3a) Case $\theta_{max} = \theta_{min} + 2 \pi$: Let $h = -r_{max}$ and $H = r_{max}$.

(3b) Case $\theta_{max} \neq \theta_{min} + 2 \pi$: Let $$S = \{ r_{min} \sin\left( \theta_{min} \right),\; r_{max} \sin\left( \theta_{min} \right),\; r_{min} \sin\left( \theta_{max} \right),\; r_{max} \sin\left( \theta_{max} \right) \}$$ be the $y$-values of the four extreme points (i.e. "corners") of the wedge. If $\theta_{min} \leq \frac{\pi}{2} \leq \theta_{max}$ then let $H = r_{max}$ and otherwise let $H = \max S$. If $\theta_{min} \leq \frac{3 \pi}{2} \leq \theta_{max}$ then let $h = -r_{max}$ and otherwise let $h = \min S$.

(4) The (bidirectional) line formed by the ray intersects the wedge if and only if $h \leq c \leq H$. If this is false then the ray doesn't intersect the wedge and we're done. So assume otherwise. Given that the ray is horizontal, it is now straightforward to determine whether or not the ray intersects the wedge based on the ray's starting point and its direction (if the horizontal ray "points away from the wedge" then it doesn't intersect the wedge, otherwise it does intersect the wedge).