3
$\begingroup$

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: wedge example

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.

$\endgroup$
4
  • $\begingroup$ Converting to polar coordinates with origin at the common center and polar axis perpendicular to the line is worth a try. $\endgroup$
    – amd
    Feb 23, 2018 at 22:05
  • $\begingroup$ The outline of the "wedge" shape consists of two line segments, and two circular arcs. Intersection between a line and a line segment is well discussed (you can find solutions all over the web). Intersection(s) between a line and a circular arc are easy to solve, if you first find the intersection between that line and that circle, and check whether the angle from the center of the circle to the intersection(s) is/are within the arc. As a line can intersect a line segment once, and a circle/arc twice, you have at most 6 intersections. Sort them along distance (line parameter). $\endgroup$ Mar 15, 2018 at 3:06
  • $\begingroup$ Would an example Python implementation help? (I do understand this is a math question and not a programming question, but Python is pretty close to typical pseudocode, so it might be useful to see what an implementation would look like in practice.) $\endgroup$ Mar 17, 2018 at 15:02
  • $\begingroup$ These shapes are sometimes called annular sectors. math.stackexchange.com/questions/39601/… $\endgroup$ Mar 21, 2018 at 14:46

4 Answers 4

3
+25
$\begingroup$

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.

enter image description here

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ One of the things that makes this tricky, is that $\|u\| \not \in [r_{min}, r_{max}]$ doesn't imply that there is no intersection. Assume that the line $f$ intersects $p$ such that $\|u\|=0$, and also assume that $\theta_{min} = 0$ and $\theta_{max} = 2\pi$ (radians). Then there is an obvious intersection of $f$, regardless of what $r_{min}$ and $r_{max}$ are $\endgroup$ Mar 14, 2018 at 15:45
  • $\begingroup$ @PaulTerwilliger You're right and I suspect you wrote this before I made an edit. But just to check if we agree, there you'll get the set of $\tilde{c}$ that make $\tilde{c}\cdot (1,a) + u$ lie in the relevant square just equal to $\pm [r_{min}, r_{max}]$, so there is indeed (clearly, as you said) an intersection. $\endgroup$ Mar 14, 2018 at 16:04
  • $\begingroup$ Okay, thanks. Not sure I understand the notation, but what is $c$ and $\tilde{c}$. I understand orthogonal projection, but the last paragraph I can't follow how to find $\tilde{c}$ or the intervals of $\tilde{c}$ $\endgroup$ Mar 14, 2018 at 16:12
  • $\begingroup$ @PaulTerwilliger Once I have $u$, I know the line orthogonal to $u$ has slope $a$ (or is the linear subspace generated by the vector $(1,a)$). So the line in the plane that is orthogonal at the 'tip' of $u$ is the set $\{\tilde{c} \cdot (1,a) : \tilde{c} \in \mathbb{R}\} + u$. As I vary $\tilde{c}$, I trace out this line. Let $v(\tilde{c}) = \tilde{c} \cdot (1,a) + u$. Then the pair $\big(\|v(\tilde{c})\|, \theta_{v(\tilde{c})}\big)$ varies with $\tilde{c}$ (in the special case above, $u =0$ implies the angle term is constant in $\tilde{c}$) and has the usual formulas (norm and angle). $\endgroup$ Mar 14, 2018 at 16:17
  • $\begingroup$ Right, I just understood what you wrote. Thanks! However, there still remains the problem of solving for $\tilde{c}$ values, and also converting the problem into a solution for a ray instead of a line. $\endgroup$ Mar 14, 2018 at 16:22
1
$\begingroup$

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:

enter image description here

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

$\endgroup$
1
$\begingroup$

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).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .