Calculate the intersection between two intervals on the same circle

Question

I want to calculate the ratio of intersection between two intervals; the length of the intersection divided by the length of the shorter interval.

If two intervals do not intersect, the ratio is 0. If one interval is fully contained in the other, the ratio is 1, otherwise it is a number between 0 and 1.

These intervals are angular intervals that lie on the same circle. So \$[-10°, 10°]\$ or \$[350°, 370°]\$ or \$[359990°, 360010°]\$ all represent the same interval.

Consequently, my method AngleIntervalIntersectionRatio() should return 1 when called with \$[-10°, 10°]\$ and \$[350°, 370°]\,ドル since both intervals are contained in one another

Some other example values:

[-10°, 10°] and [0°, 360°]: return 1; (= intersection:20° / shortest interval:20°)
[-10°, 10°] and [0°, 180°]: return 0.5; (= intersection:10° / shortest interval:20°)
[-10°, 10°] and [90°, 180°]: return 0;
[-10°, 10°] and [350°, 360°]: return 1;
[-20°, 20°] and [10°, 350°]: return 0.5; (= intersection:20° / shortest interval:40°)
[-10°, 10°] and [-3600090°, -3600000°]: return 0.5;

I have two methods for this: IntervalIntersectionRatio() just calculates the intersection ratio of two intervals on an infinite line. AngleIntervalIntersectionRatio() uses this function to calculate the intersection ratio of two intervals on a circle.

I am unhappy with my current code, mainly with two parts:

• The code I use to normalize the angles to be between \0ドル°\$ and \360ドル°\$ uses some while loops. Anything I try with modulo just becomes very hard to understand at a glance.
• Since the end of the interval can be above \360ドル°\$ after normalization, I have to call IntervalIntersectionRatio() 3 times to cover all possible cases of intersection. For example, with intervals such as \$[-20°, 20°]\$ and \$[10°, 350°]\$ (becomes \$[340°, 380°]\$ and \$[10°, 350°]\$ after normalizing, and the intersection is \20ドル°\,ドル not \10ドル°\$).

Is there anything I could to to make it more beautiful? I am not primarily concerned with performance.

I am also unsure whether I should put all this into a full-blown class hierarchy of intervals and angular-intervals, just for these two functions.

/// <summary> returns the length of the intersection between two angular intervals on the same circle, divided by the length of the shorter interval </summary>
/// <param name="i1Start">start of first interval in degrees</param>
/// <param name="i1End">end of first interval in degress</param>
/// <param name="i2Start">start of second interval in degrees</param>
/// <param name="i2End">end of second interval in degrees</param>
/// <returns>ratio between 0 and 1 (0: no intersection; 1: one interval is a subset of the other</returns>
public static double AngleIntervalIntersectionRatio(double a1start, double a1end, double a2start, double a2end)
{
 // the start angle is always smaller than the end angle
 Debug.Assert(a1start < a1end); 
 Debug.Assert(a2start < a2end);
 // the intervals can cover at most a full circle
 Debug.Assert(a1start + 360 >= a1end); 
 Debug.Assert(a2start + 360 >= a2end);
 // the angles may be larger than 360° or smaller than 0°: 
 // [-10°, 10°] or [350°, 370°] are both valid representations of the same interval
 // ugly code to normalize the angular intervals 
 //so that the start of each interval is definitely between 0° and 360°
 while (a1start >= 360)
 {
 a1start -= 360;
 a1end -= 360;
 }
 while (a1start < 0)
 {
 a1start += 360;
 a1end += 360;
 }
 while (a2start >= 360)
 {
 a2start -= 360;
 a2end -= 360;
 }
 while (a2start < 0)
 {
 a2start += 360;
 a2end += 360;
 }
 // ugly code to cover all 3 possible intersection types. 
 // (Since intervals are at most 360° big, this should cover all possibilities)
 // at most two of these ratios can be !=0 at the same time
 double ratio1 = IntervalIntersectionRatio(a1start, a1end, a2start, a2end);
 double ratio2 = IntervalIntersectionRatio(a1start, a1end, a2start + 360, a2end + 360);
 double ratio3 = IntervalIntersectionRatio(a1start + 360, a1end + 360, a2start, a2end);
 return ratio1 + ratio2 + ratio3;
}
/// <summary> returns the length of the intersection between two intervals, divided by the length of the shorther interval 
/// </summary>
/// <param name="i1Start">start of first interval</param>
/// <param name="i1End">end of first interval</param>
/// <param name="i2Start">start of second interval</param>
/// <param name="i2End">end of second interval</param>
/// <returns>ratio between 0 and 1 (0: no intersection; 1: one interval is a subset of the other</returns>
public static double IntervalIntersectionRatio(double i1Start, double i1End, double i2Start, double i2End)
{
 double intersectionStart = Math.Max(Math.Min(i1Start, i1End), Math.Min(i2Start, i2End));
 double intersectionEnd = Math.Min(Math.Max(i1Start, i1End), Math.Max(i2Start, i2End));
 double intersectionLength = intersectionEnd - intersectionStart;
 if (intersectionLength <= 0) return 0;
 double length1 = Math.Abs(i1End - i1Start);
 double length2 = Math.Abs(i2End - i2Start);
 double minLength = Math.Min(length1, length2);
 // minLength is >0 if intersectionLength is >0, so no divide by zero here
 double ratio = intersectionLength / minLength;
 ratio = Math.Max(0, ratio);
 ratio = Math.Min(1, ratio);
 return ratio;
}

• David Harkness: One case missing from your examples is an interval that loops around and passes the lower bound. Is (-10, 370) equivalent to (-10, 10) or will it force a ratio of 1 for all other non-empty intervals?
• HugoRune: An interval larger than 360° should never occur in my program, but if it were possible, I guess the second alternative, forcing a ratio of 1, would be the correct one.
• 200_success: Could you clarify why AIIR([-10°, 10°], [350°, 360°]) should return 1?
• svick: Where are these numbers coming from? Are they some kind of measurement, or are they entered by humans? If it's the latter, then you should probably use decimal instead of double.

Answer 1

Algorithm wise it looks quite good but I feel you could benefit from the single responsibility principle.

First thing that would get on my nerves would be passing the intervals in "non atomic form" e.g.:

double IntervalIntersectionRatio(double i1Start, double i1End, double i2Start, double i2End)

Instead I would want to have an interval class that has a start and an end member.

Now that you have got that class you could implement a "stupid" Interval intersection(Interval, Interval) function that works on plain intervals (without the circular logic).

Next thing to go about would be the normalization. That code duplication you have there is really a strong smell. Instead have a function to normalize a single number into interval [0, 360) and maybe one that does that for the start and end of an Interval returning the normalized Interval.

Now the only thing you must take care of is the case where one Interval wraps around the 360|0 border which would not be handled correctly by the "stupid" intersection function. So you would have another function that "unwraps" such an Interval by adding 360 to the end of it before passing the Interval to the intersection function.

Giving a length function for Intervals will make the code a bit more readable and most of your problems should be gone.

Disclaimer I did not think too deeply about this and there might be some edge cases that I missed here but the overall design improvement should make them easier to catch.

• HugoRune: I guess classes for Interval and AngleInterval are the cleanest solution here. One complication for the "unwrap" part are intersections between intervals like [-20°, 20°] and [10°, 350°]. These intervals intersect at both ends, an I do not see a way to resolve that without calling the linear intersection function multiple times with different offsets.
• Nobody moving away from SE: @HugoRune: The fundemantal problem is, that the intersection of these two intervals results in two disjoint intervals which the linear intersection function cannot produce. The way to go would be to linearize such intervals to the two intervals [lower, 360] and [0, upper] which can be handled by the linear intersection function.

Answer 2

To simplify your normalization code...

First, calculate the intervals for each pair on the unnormalized data. For example, the length of the interval between [0, 360] is calculated via 360 - 0.

Second, calculate the normalized start position by using modulus. In C, calculate n mod M with ((n % M) + M) % M. (See discussion at SO). This could be a function.

Now, you have your data represented as (start1, interval1) and (start2, interval2). I think that's a better representation for what you want to do.

If you disagree, calculate endN via startN + intervalN to get (start1, end1) and (start2, end2).

Edit: Added info from comments.

• HugoRune: The idea to express each interval as start+length is interesting, this could really simplify the normalization. One thing that annoys me is that even with just one angle, the normalization is not simply (angle % 360). To deal with negative values, I think I need something like ((angle % 360) + 360) % 360, which looks horrible.
• David Z: @HugoRune I dunno... yes it's subjective, but (angle % 360 + 360) % 360 doesn't look too bad to me. (You should see some of the formulas I've implemented!) Anyway that'd be a perfect thing to put into a function, normalizeAngle(double).