Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am writing an application that uses GPS coordinates to gather information on nearby places based on which direction the driver is headed. I would post a picture, but being a new poster prevents me from doing so. I will attempt to describe it as best I can.

Situation: The driver is driving NE. There are possible locations all around him. I want to get the locations that are in front of him in an 80 degree span (this span can change)

Assume:

  • Standard XY coordinates as I can use latitude and longitude to get their information.
  • Driver can be driving in any direction (of course)

I am trying to figure out a formula that will confirm the locations are in the shaded area.

The degree at which it detects the location is not set right now as this will change due to testing and what will work best.

share|improve this question
add comment

1 Answer 1

up vote 0 down vote accepted

Suppose you are at $x \in \mathbb{R}^2$ headed in a direction $d \in \mathbb{R}^2$ and you wish the figure out the angle towards a point at $y \in \mathbb{R}^2$ (see picture). I am taking anti-clockwise angles to be positive.

One way of determining the angle is to use the 2D cross product which gives $$ a \times b = a_1 b_2 - a_2 b_1 = \|a\| \|b \| \sin \theta$$ or, in other words, $\theta = \arcsin \frac{a_1 b_2 - a_2 b_1}{\sqrt{a_1^2+a_2^2} \sqrt{b_1^2+b_2^2}}$. In this case here we would take $a = d$, $b = y-x$, and check if $\theta$ lies within appropriate bounds.

enter image description here

However, if there are many objects to be checked and you only care if they lie within some prescribed sector, there is a cheaper way.

The idea is to check if the points lie in the intersection of two half-planes. See the drawing below. The point $y$ lies in the desired sector iff $$ \langle n_+, y-x \rangle \leq 0, \ \ \ \langle n_-, y-x \rangle \geq 0$$

enter image description here

So, all that is needed is to compute $n_+, n_-$.

Let $h_\theta = \pmatrix{ \cos \theta & -\sin \theta \\ \sin \theta & \cos \theta} d = \pmatrix{d_1 \cos \theta - d_2 \sin \theta\\ d_1 \sin \theta + d_2 \cos \theta } $. This is an anti-clockwise rotation of $d$ by the angle $\theta$. Let $n_+ = h_{\frac{\pi}{2}+\theta_\max}$, $n_- = h_{\frac{\pi}{2}-\theta_\max}$, where $\theta_\max$ is the sector angle ($80^\circ$ in your example above).

share|improve this answer
    
In the second picture above, replace $\theta$ by $\theta_\max$. –  copper.hat Oct 10 '12 at 17:05
    
Thanks for the detailed explanation! When would I use $h_\theta$ once I solved for the first equation? I see it when solving for $n_+$ , but I'm not sure how to apply it... –  Andrew.Wells Oct 11 '12 at 14:52
    
First pick your $\theta_\max$ (80∘ above). Then use the formula for $h_\theta$ to compute the two vectors $n_+,n_-$. Then a point $y$ is in the region if and only if $\langle n_+, y-x \rangle \leq 0, \ \ \ \langle n_-, y-x \rangle \geq 0$. –  copper.hat Oct 11 '12 at 15:03
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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