Calculate overlap of two angle intervals

Question

Let's say I have two intervals,

[a1, a2] and [b1, b2]

Where a1,a2,b1,b2 are all in the range [0, 2 pi]. Now, given these two intervals, I want to find their overlapping interval. This is quite tricky. Since an example of two intervals is

[5, 1] and [0, 6]

Which are sketched below (the red areas are the intervals).

Notice that these two intervals return an overlapping interval that consists of two intervals:

[0,1] and [5,6]

There are multiple different cases that must be treated, is there any known algorithm that does this?

Alfilaria

Answer 1

I do not know of an existing algorithm (which doesn't mean there isn't one), but here's one I've come up with.

As already mentioned by @Michael Kenzel, numbers don't increase monotonically, which makes everything very complicated.

But we can observe that we can unroll the circle onto the number line. Then each interval then appears infinitely many times with a period of 2π.

Let's first define a normalize operation as following:

normalize([a, b]):
    if (a > b):
        a -= 2π

Using this operation we unroll both our intervals onto a [-2π, 2π] part of the number line.

Example intervals:

[2, 5] -> [2, 5]

[4, π] -> [-2, π]

Two intervals on a circle can overlap at most 2 times.

(I don't have a proper proof of this, but intuitively: an overlap starts where one interval started and another one has not ended. This can happen only once on a number line and twice in our case.)

By just looking at normalized intervals, we can miss one of the overlaps. In the example above we would detect [2, π] overlap and miss [4, 5]. This happens because we have unrolled the original intervals not onto [0, 2π], but a twice longer part of the number line, [-2π, 2π].

To correct for that, we can, for example, take the part that falls onto the negative line and shift it by 2π to the right, this way having all pieces in the original [0, 2π]. But it is computationally ineffective, as we will, in the worst case, have to test 2 pieces on one interval against 2 pieces of another interval - total of 4 operations.

Here is an illustration of such an unlucky example that will require 4 comparisons:

If we want to be a bit more efficient, we will try to do only 2 interval-vs-interval operations. We won't need more as there will be at most 2 overlaps. As the intervals repeat infinitely on the number line with the period of 2π, we can just take 2 neighboring duplicates of the first interval and compare them against the second one. To make sure that the second interval will be, so to say, in between those duplicates, we can take the one that starts earlier and add 2π to its both ends. Or subtract 2π from the one that starts later.

There will be not more than two overlaps, which can be then brought back to the [0, 2π] interval by addition/subtraction of 2π.

In our original example it would look like that:

To sum it up:

given [a, b], [c, d]
[A, B] = normalize([a, b])
[C, D] = normalize([c, d])
if (A < C):
    [E, F] = [A + 2π, B + 2π]
else:
    [E, F] = [A - 2π, B - 2π]
I_1 = intersect([A, B], [C, D])
I_2 = intersect([E, F], [C, D])
bring I_1 and I_2 back to the [0, 2π]

I think I didn't miss any corner cases, but feel free to point to any mistake in my logic.

Rechabite

Answer 2

The first thing to note is that no new angle is created when you discover the intersection sector of two sectors 'A' and 'B'. Sector 'A' is defined by two limits, Acw and Acc, and sector 'B' is defined by two limits, Bcw and Bcc. Here 'cw' and 'cc' denote 'ClockWise' and 'CounterClockwise'.

The boundaries of the intersection sector will be made from at most two out of these four angles. The problem is entirely concerned with selecting two out of these four angles to be the limits of the intersection sector, let's call them Icw and Icc.

It is important to distinguish between "cw" and "cc" and keep them straight throughout the problem, because any pair of angles actually defines two sectors, right? This is as you have shown in your picture at the top of this answer. The issue of "angle wraparound" will arise naturally as the problem is solved.

Some Helper Functions

OK, so we have our four angles, and we have to select two of the four to be the limits of our intersection sector. In order to do this, we need an operator that determines whether an angle dAngle falls between two limits, let's call them dLimitCW and dLimitCC.

It is in this operator that the issue of "angle wraparound" arises. I did mine by constraining all angles to the range of -π to π. To determine whether dAngle falls between dLimitCW and dLimitCC, we subtract dAngle from dLimitCW and dLimitCC, and then constrain the result to fall within the [-π, π] range by adding or subtracting 2π. This is just like rotating the polar coordinate system by the angle dAngle , so that what was dAngle is now zero; what was dLimitCW is now dLimitCWRot, and what was dLimitCC is now dLimitCCRot.

The code looks like this:

bool AngleLiesBetween(double dAngle, double dLimitCW, double dLimitCC)
{
    double dLimitCWRot, dLimitCCRot;

    // Rotate everything so that dAngle is on zero axis.

    dLimitCWRot = constrainAnglePlusMinusPi(dLimitCW - dAngle);
    dLimitCCRot = constrainAnglePlusMinusPi(dLimitCC - dAngle);

    if (dLimitCWRot > dLimitCCRot)
        return (signbit(dLimitCWRot * dLimitCCRot));
    else 
        return (!signbit(dLimitCWRot * dLimitCCRot));
}

where the function constrainAnglePlusMinusPi is

double constrainAnglePlusMinusPi(double x)
{
    x = fmod(x + pi, 2*pi);
    if (x < 0)
        x += 2*pi;
    return x - pi;
}

Once we have our "angle lies between" function, we use it to select which of the four angles that made up the limit angles of the two sectors make up the intersection sector.

The Nitty Gritty

To do this, we must first detect the case in which the two angular ranges do not overlap; we do this by calling our AngleLiesBetween() function four times; if it returns a "false" all four times, there is no overlap and the intersection is undefined:

    if (
        (AngleLiesBetween(Acw, Bcw, Bcc) == false) && 
        (AngleLiesBetween(Acc, Bcw, Bcc) == false) &&
        (AngleLiesBetween(Bcw, Acw, Acc) == false) &&
        (AngleLiesBetween(Bcc, Acw, Acc) == false)
        )
    {
        // Ranges have no overlap, result is undefined.

        *this = CAngleRange(0.0f, 0.0f);
        return;
    }

Here I'm returning a CAngleRange object containing (0.0, 0.0) to indicate "no overlap," but you can do it some other way if you like, like by having your "intersection" function return a value of "false."

Once you've handled the "no overlap" case, the rest is easy. You check each of the six remaining combinations one at a time and determine which two limits are the limits of I by their outcomes:

if ((AngleLiesBetween(Acw, Bcw, Bcc) == true) && (AngleLiesBetween(Acc, Bcw, Bcc) == false)) then Icw = Acw and Icc = Bcc;

if ((AngleLiesBetween(Acw, Bcw, Bcc) == false) && (AngleLiesBetween(Acc, Bcw, Bcc) == true)) then Icw = Bcw and Icc = Acc;

if ((AngleLiesBetween(Acw, Bcw, Bcc) == true) && (AngleLiesBetween(Acc, Bcw, Bcc) == true)) then Icw = Acw and Icc = Acc;

if ((AngleLiesBetween(Bcw, Acw, Acc) == true) && (AngleLiesBetween(Bcc, Acw, Acc) == false)) then Icw = Bcw and Icc = Acc;

if ((AngleLiesBetween(Bcw, Acw, Acc) == false) && (AngleLiesBetween(Bcc, Acw, Acc) == true)) then Icw = Acw and Icc = Bcc;

and finally

if ((AngleLiesBetween(Bcw, Acw, Acc) == true) && (AngleLiesBetween(Bcc, Acw, Acc) == true)) then Icw = Bcw and Icc = Bcc.

You don't have to constrain the results to [-π, π] or [0, 2π] because you haven't changed them; each of the result angles is just one of the angles you presented as input to the function in the first place.

Of course you can optimize and streamline the code I've given in various ways that take advantage of the symmetries inherent in the problem, but I think when all is said and done you have to compare eight separate angle combinations for "between-ness" no matter how you optimize things. I like to keep things simple and straightforward in my code, in case I have made an error and have to come back and debug it in a few years when I've forgotten all my clever optimizations and streamlining efforts.

About Angle Wraparound

Notice that the issue of "angle wraparound" got handled in function AngleLiesBetween(); we rotated the coordinate system to put the angle we are checking (which we called dAngle) for "between-ness" at zero degrees. This naturally puts the two angle limits (dLimitCW and dLimitCC) on either side of the polar origin in the case in which dAngle is between those limits. Thus, the wrap-around issue disappears; we've "rotated it out of the way," so to speak.

About the Polar Coordinate System

It may be worth noting that in the polar coordinate system I'm using, CW angles are more positive than CC angles (unless the wrap-around is between them). This is the opposite of the polar coordinates we learn in calculus class, where angles increase in the CC (counterclockwise) direction.

This is because of the quandary that results from the decision — made long, long ago — that computer devices (like display surfaces, originally implemented on cathode ray tubes) would count the vertical direction as increasing downward, instead of upward, as we learn when we study analytic geometry and calculus.

The people who made this decision did so because they wanted to display text on the screen, with the "first" line at the top, the "second" line (line 2) below the "first" line (line 1), and so forth. To make this easier to keep track of this in their early machine code, they had the +y direction go "down," as in "toward the bottom of the screen." This decision has far-reaching and annoying consequences for people who do image geometry in code.

One of the consequences is that by flipping the direction of +y, the "sense of rotation" also flipped from the conventional "angle increases counterclockwise" sense we're used to from high-school math. This issue is mostly invisible at the coding level; it only comes out when you look at your results on the screen.

This is why it is very important to write code to visualize your results on the screen before you trust them. Here "trust them" is certainly necessary before you let your customer see them.

Abundance

Answer 3

As long as you have intervals where the numbers just increase monotonically, it's simple; you just take the max() of the minimums and the min() of the maximums and done. It would seem that the major source of complication here is the fact that you can have intervals that wrap around at 0, i.e., the numbers that are part of the interval are not monotonically-increasing. It would seem to me that one way around this problem is to simply treat intervals that wrap around as not one interval but the union of two intervals. For example, think of [5, 1] as [5, 2 pi] ∪ [0, 1]. Then the problem of finding the intersection of [5, 1] and [0, 6] turns into the problem of finding the intersection of [5, 2 pi] and [0, 6] as well as the intersection of [0, 1] and [0, 6]. Mathematically, you'd be taking advantage of the distributive law of set intersection, i.e., (A ∪ B) ∩ C = (A ∩ C) ∪ (B ∩ C). So given two intervals A and B, we would start by splitting each into two intervals, A1 and A2, and B1 and B2, where A1 and B1 each start after 0 and end before 2 pi, and A2 and B2 start before 2 pi and end before 2 pi. Slitting like this, we can compute our intersections like

(A1 ∪ A2) ∩ (B1 ∪ B2) = (A1 ∩ (B1 ∪ B2)) ∪ (A2 ∩ (B1 ∪ B2) = (A1 ∩ B1) ∪ (A1 ∩ B2) ∪ (A2 ∩ B1) ∪ (A2 ∩ B2)

i.e., compute the intersection of all combinations of A1, A2, B1, and B2…

Cesaria