Jump to content
  • Advertisement
Sign in to follow this  
yahastu

Intersecting two angular ranges

This topic is 2603 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Suppose that an "angular range" is specified by a starting and ending angle, proceeding clockwise.

The first angular range is (a,b) and the second is (c,d). If both angular ranges span more than 180 degrees then it is possible that there are two intersection ranges. However if they do not EACH span more than 180 degrees, then the intersection can be represented as a single angular range denoted by (e,f). What is it?

In all cases, it is clear that e = a or c, and f = b or d.

A few examples to begin with:

intersection of (a=45, b=10) with (c=350, d=30) is (e=350, f=10)
intersection of (a=45, b=10) with (c=270, d=300) is (e=270, f=300)
intersection of (a=45, b=95) with (c=55, d=80) is (e=55, f=80)

Progress:
--------

After much mucking about looking for a simple analytical solution that doesn't seem to exist, I realized that if you sort all four angles (a,b,c,d) radially, then find the index "i" such that the angle between "i" and "i-1" (using modular indices) does not belong to either of the input angular ranges, then the intersection should be given by angles at indices "i+1" and "i+2".

Finding this index requires checking whether an angle belongs within a given angular range, and that requires a more mathematical definition of the set of angles in an angular range.
My first thought was that an angular range could be defined by the cross product.

That is, the range (a,b) could be written as the set

{ p \in (0,2pi) | cross(vec(a),vec(p)) > 0 && cross(vec(p), vec(b)) > 0 }

where vec(a) is the 2D cartesian vector represented by the angle 'a', and cross is the 2D analog of the cross product (ie, the z-component of the 3D cross product).

However, then I realized that this definition only works for angular ranges spanning less than 180 degrees. I'm having difficulty coming up with a simple mathematical definition that can be used to test whether a point is inside of an arbitrary angular range which might span more than 180 degrees.

Also, if anyone can think of a simpler overall approach, I'd be happy to hear it.

Share this post


Link to post
Share on other sites
Advertisement
For the original problem have you tried something like:

pair<int, int> intersect(pair<int, int> range1, pair<int, int> range2) {
int min1 = range1.first;
int min2 = range2.first;
int max1 = range1.second;
int max2 = range2.second;

if(max1 < min1) max1 += 360;
if(max2 < min2) max2 += 360;

int min = max(min1, min2);
int max = min(max1, max2);

if(max < min) return make_pair(-1, -1); // No intersection
if(max > 360) max -= 360;
return make_pair(min, max);
}


For multiple ranges you run into problems (I think the second range is [min(min1, min2), max(max1, max)] if it exists).

As for the second problem, how about:

bool pointInRange(int min, int max, int x) {
if(max < min) max += 360;
return (x >= min && x <= max) || (x + 360 >= min && x + 360 <= max);
}

Share this post


Link to post
Share on other sites
For the original problem, your solution doesn't work as-is. Consider the intersection of (0,90) with (358, 70)...

Using your method, min1=0, min2 = 358, max1 = 90, max2 = 70 --> 430

Then min3 = max(min1,min2) = max(0,358) = 358
and max3 = min(max1,max2) = min(90,430) = 90

In this case both those numbers are wrong, it gave the union rather than intersection

For the point in range problem, your solution works :)

Share this post


Link to post
Share on other sites
Quite right -- it's a rather fiddly problem although my general view is an arithmetic moduli solution will be cleaner in the end than any hull type solution (see below). I'll try one more time, if I were writing this for work etc I may just write a brute force test for all integer 4-tuples to ensure it is probably correct and easily debug failing cases, hopefully you get the idea of how the solution *might* be constructed.


pair<int, int> intersect(pair<int, int> range1, pair<int, int> range2) {
int min1 = range1.first;
int min2 = range2.first;
int max1 = range1.second;
int max2 = range2.second;

if(max1 < min1 && max2 < min2) {
max1 += 360;
max2 += 360;
}
else if(max1 < min1) {
if(min1 > max2) min1 -= 360;
else max1 += 360;
}
else if(max2 < min2) {
if(min2 > max1) min1 -= 360;
else max1 += 360;
}

int min = max(min1, min2);
int max = min(max1, max2);

if(max < min) return make_pair(-1, -1); // No intersection
if(max > 360) max -= 360;
if(min < 0) min += 360;
return make_pair(min, max);
}



Perhaps another possibility similar to yours is to sort the four angles. Denote them [minA, maxA], [minB, maxB]. Walk the sorted angles, if you encounter the pattern "minX maxX minY maxY" then the ranges do not intersect. If you have "minX minY maxY maxX" the range is [minY maxY] and if you have "minX minY maxX maxY" the range is [minY maxX]. As a bonus "minX maxY minY maxX" corresponds to two ranges [minX maxY] + [minY maxX].

Share this post


Link to post
Share on other sites

Quite right -- it's a rather fiddly problem although my general view is an arithmetic moduli solution will be cleaner in the end than any hull type solution (see below). I'll try one more time, if I were writing this for work etc I may just write a brute force test for all integer 4-tuples to ensure it is probably correct and easily debug failing cases, hopefully you get the idea of how the solution *might* be constructed.


This one works, gives the same output as my method on my unit tests but is obviously cleaner. Thanks for your help :)

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!