🔒 Locked

Intersecting two angular ranges

Started by yahastu Oct 20, 2011 at 11:34 PM 3 replies 1.1k views

Original Post

Oct 20, 2011 at 11:34 PM

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.

pantaloons

Oct 21, 2011 at 5:08 AM

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);
 }

yahastu

Oct 21, 2011 at 4:49 PM

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

pantaloons

Oct 22, 2011 at 2:30 AM

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

yahastu

Oct 24, 2011 at 5:17 PM

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

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.