2
$\begingroup$

Setup

Consider the following diagram:

enter image description here

The "2D cone" with origin A separates the 2D plane into 2 regions, inside and outside.

Consider the 4 representative edges $c, d, e, f$ that encompass all intersection cases (assume that an edge aligned with the cone's boudary is equivalent to $e$).

An edge is either fully inside the cone, has one end point inside and one outside, has both end points outside but a subset of its interior is inside, is fully outside.

We are looking for the points of intersection of the cone $A$ with each edge. For $c$ it would be the rightmost end point and the point of intersection of the cone's edge with the segment, for $e$ it would be the 2 endpoints of the segment, for $f$ no intersection point exists, for $d$ it's the 2 points where the boundary of the cone intersects the interior of $d$.

Problem

With this setup here is the practical problem:

The cone $A$ is defined by an origin $A$ and 2 directions $d_1, d_2$. Each segment is defined by its 2 end points $p_1, p_2$.

Given an arbitrary cone, with inner angle less than $\pi$ and an arbitrary segment, use nothing but vector algebra to find the 2 intersection points. If no intersection is possible, identify it somehow, encoded numerically in the 2 points. You can assume the directions $d_1, d_2$ are always given to you in clockwise order.

Current approach

My current approach is to, grab the 2 end points of the segment, check their angled sign relative to the window (which is done through the dot product of 2 cross products). With the signed angles of each end point I identify whether the point is inside or outside the window. A point is in the interior iff $0 < \sigma < w$ where $\sigma, w$ are the signed angle of the point with respect to the rightmost edge of the cone and $w$ is the angle of the cone.

With that information I can decide which of the 4 cases I am actually in, then make the decisions with that assumption.

e.g If only one of the 2 endpoints is in the interior I know for a fact there is a unique point of intersection with one of the 2 boundaries, so figure out which one it is and then I know the 2 intersection points.

This is overly convoluted. I am curious if there is a more unified way that can find both intersection points without having to create a big tree of if else's

$\endgroup$
1
$\begingroup$

Here is an approach that avoids dividing into cases as well as any trigonometry. Suppose that the directions $d^1 = (d^1_1,d^1_2)$ and $d^2 = (d^2_1,d^2_2)$ are given in clockwise order. Rotate these vectors by $90^\circ$ clockwise and counterclockwise respectively to product $$ l = (d_2^1,-d^1_1), \quad r = (-d^2_2, d^2_1). $$ A point $x = (x_1,x_2)$ will lie within the cone if and only if it satisfies $x \cdot l \geq 0$ and $x \cdot r \geq 0$, where $v \cdot w$ denotes the dot-product of vectors $v$ and $w$. More specifically, we have $x \cdot l \geq 0$ iff $x$ lies to the "right" of the "left-side" boundary, and $x \cdot r \geq 0$ iff $x$ lies to the "left" of the "right-side" boundary.

We are given two endpoints $p^1 = (p^1_1,p^1_2)$ and $p^2 = (p^2_1,p^2_2)$. The line connecting these points is the set of all points $$ p(t) = (1-t)p^1 + tp^2 $$ with $t \in \Bbb R$. Note that $p(t)$ is on the line segment connecting the two points when $0 \leq t \leq 1$. Moreover, $p(0) = p^1$ and $p(1) = p^2$.

We now find the "times" $t$ at which this line crosses either of the boundaries. That is, we solve $$ l \cdot p(t_l) = 0 \implies (1-t_l)(l \cdot p^1) + t_l(l \cdot p^2) = 0 \implies t_l = \frac{l \cdot p^1}{(l \cdot p^1) - (l \cdot p^2)},\\ l \cdot p(t_r) = 0 \implies (1-t_r)(l \cdot p^1) + t_r(l \cdot p^2) = 0 \implies t_r = \frac{r \cdot p^1}{(r \cdot p^1) - (r \cdot p^2)}. $$ If either of these numbers satisfy $0 \leq t \leq 1$, plug into $p(t)$ to produce the associated point.

The only case not accounted for here is division by zero, which occurs when the line segment is parallel to one of the boundaries.

$\endgroup$
2
  • $\begingroup$ There's at least one point where I am confused. "A point $x=(x1,x2)$ will lie within the cone if and only if it satisfies $x⋅l≥0$ and $x⋅r≥0$, where $v⋅w$ denotes the dot-product of vectors $v$ and $w$."" I am not being able to understand how this helps but that seems to be the main thing in your method that solves this problem. Is it possible to ask you to explain that a little bit more? $\endgroup$
    – Makogan
    Jul 27 '20 at 15:40
  • $\begingroup$ @Makogan As $t$ increases from $0$ to $1$, $p(t)$ gives the coordinates to a point on a line segment such that we "move" from $p^1$ to $p^2$. If we cross one of the lines, then we cross from one region to the other when we switch between $p(t) \cdot l \leq 0$ to $p(t) \cdot l \geq 0$ or between $p(t) \cdot \leq 0$ to $p(t) \cdot l \geq 0$. In other words, we can see that we cross the line at the points where $p(t) \cdot l = 0$ or $p(t) \cdot r =0$. $\endgroup$ Jul 27 '20 at 16:18

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.