Merge angle range

Question

I have AngleRange class with define range to angles to detect if a angle is inside the range.

public class AngleRange
{
    private readonly double _from;
    private readonly double _to;
    public AngleRange(double from, double to)
    {
        _from = DoubleUtils.NormalizeAngle(from); // 0 <= x < 360
        _to = DoubleUtils.NormalizeAngle(to);
    }

    public bool Inside(double target)
    {
        if (_from < _to)
            return _from <= target && target <= _to;
        return _from <= target || target <= _to;
    }
}

The angles used is 0 <= x < 360. For example,

var range1 = new AngleRange(0, 15);
range1.Inside(10); // True
var range2 = new AngleRange(15, 0);
range2.Inside(10); // False

Because range2 is from 15 to 0 which means any angles, that 0 < x < 15 should return false.

My problem is to merge two AngleRange into one. For example, AngleRange(0, 15) merge AngleRange(10, 13) should return AngleRange(0, 15) because AngleRange(0, 15) includes AngleRange(10, 13).

If AngleRange(0, 15) merge AngleRange(10, 17)should return AngleRange(0, 17).

However, AngleRange(15, 0) and AngleRange(10, 13)should not able to merge because they do not intersect.

I am having trouble to check if two AngleRange is intersect, within, or not intersect with another. This is the method I am try to make.

public bool TryMerge(AngleRange range, out AngleRange range)
{
    // if not intersect
    // return false

    // if within
    // return true, out larger one

    // return true, out a new one with merged bound
}

Edit

For someone want to know the usage of this, I use this in my shadowcasting class. The merge method is needed to merge different shadow.

Answer 1

Your method name should probably be "AngleRangesIntersect" looking at its return type. Seems like your one little function is trying to do a bit too much. It's not merging the angle ranges but checking if there's an intersection between them. First let's get this logic a function of its own, then we can build a "MergeAngleRanges" one on top of that.

Something like this should do the trick for checking if they intersect:

private bool AngleRangesIntersect(AngleRange FirstAngleRange, AngleRange SecondAngleRange)
{
  if (FirstAngleRange._from > SecondAngleRange._from 
      && FirstAngleRange._from < SecondAngleRange._to)
  {
     return true;
  }
  if (SecondAngleRange._from > FirstAngleRange._from 
      && SecondAngleRange._from < FirstAngleRange._to)
  {
     return true;
  }
  if (FirstAngleRange._to > SecondAngleRange._from 
      && FirstAngleRange._to < SecondAngleRange._to)
  {
     return true;
  }
  if (SecondAngleRange._to > FirstAngleRange._from 
      && SecondAngleRange._to < FirstAngleRange._to)
  {
     return true;
  }

  return false;
}

Obviously this is a bit of a hot mess riddled with duplication so I'd probably extract these conditionals out into their own private functions:

private bool EitherAngleStartsBetweenOthersRange(AngleRange FirstAngleRange, AngleRange SecondAngleRange)
{
  if (FirstAngleRange._from > SecondAngleRange._from 
      && FirstAngleRange._from < SecondAngleRange._to)
  {
     return true;
  }
  if (SecondAngleRange._from > FirstAngleRange._from 
      && SecondAngleRange._from < FirstAngleRange._to)
  {
     return true;
  }

  return false;
}

private bool EitherAngleEndsBetweenOthersRange(AngleRange FirstAngleRange, AngleRange SecondAngleRange)
{
  if (FirstAngleRange._to > SecondAngleRange._from 
      && FirstAngleRange._to < SecondAngleRange._to)
  {
     return true;
  }
  if (SecondAngleRange._to > FirstAngleRange._from 
      && SecondAngleRange._to < FirstAngleRange._to)
  {
     return true;
  }

  return false;
}

Then we can pop the refactor in and enjoy a much nicer Check:

public bool AngleRangesIntersect(AngleRange FirstAngleRange, AngleRange SecondAngleRange)
{
  if (EitherAngleStartsBetweenOthersRange(FirstAngleRange, SecondAngleRange))
  {
    return true;
  }
  if (EitherAngleEndsBetweenOthersRange(FirstAngleRange, SecondAngleRange))
  {
    return true;
  }

  return false;
}

Now that we have that bit of the logic squared away we can mosey on to the merging of the angles. Now as far as I understand it what you're trying to do is:

If the angles intersect, create one god angle with the max upper and lower bound.

for that we'd probably stick a couple of extra functions in to return the min and max for angles.

private double GetSmallestLowerBound(AngleRange FirstAngleRange, AngleRange SecondAngleRange)
{
  // Allow for cases like (355, 10) merging with (5, 350)
  if (FirstAngleRange._from < SecondAngleRange._from ||
      FirstAngleRange._from > SecondAngleRange._to)
  {
    return FirstAngleRange._from;
  }

  return SecondAngleRange._from;
}

private double GetLargestUpperBound(AngleRange FirstAngleRange, AngleRange SecondAngleRange)
{
  // Allow for cases like (20, 10) merging with (15, 25) 
  if (FirstAngleRange._to > SecondAngleRange._to ||
      FirstAngleRange._to < SecondAngleRange._from)
  {
    return FirstAngleRange._to;
  }

  return SecondAngleRange._to;
}

Now that we have all the pieces we can put together our final merge method:

public AngleRange MergeAngleRanges(AngleRange FirstAngleRange, AngleRange SecondAngleRange)
{
  if (AngleRangesIntersect(FirstAngleRange, SecondAngleRange))
  {
    return new AngleRange(GetSmallestLowerBound(FirstAngleRange, SecondAngleRange),
                          GetLargestUpperBound(FirstAngleRange, SecondAngleRange)));
  }
  return new AngleRange(0.0f, 0.0f);
}

Any troubles give me a shout.

Answer 2

After some others help and Google, I come up with this solution (written in C#).

AngleRange

public class AngleRange 
{
    private readonly double _from, _to;
    private readonly bool _full;

    public AngleRange (double from, double to)
    {
        _from = DoubleUtils.NormalizeAngle(from);
        _to = DoubleUtils.NormalizeAngle(to);
        _full = false;
    }

    public AngleRange (bool full)
    {
        _from = 0;
        _to = 0;
        _full = full;
    }

    public bool Inside(double target)
    {
        if (_full)
            return true;
        if (_from < _to)
            return _from.AboutLesserThanOrEqual(target) && target.AboutLesserThanOrEqual(_to);
        return _from.AboutLesserThanOrEqual(target) || target.AboutLesserThanOrEqual(_to);
    }

    public bool TryMerge(AngleRange newAngleRange, out AngleRange resultAngleRange)
    {
        if (newAngleRange._full)
        {
            resultAngleRange = newAngleRange;
            return true;
        }

        if (_full || Equals(newAngleRange))
        {
            resultAngleRange = this;
            return true;
        }

        var aStart = _from;
        var aEnd = aStart > _to ? _to + 360 : _to;
        var bStart = newAngleRange._from;
        var bEnd = bStart > newAngleRange._to 
                   ? newAngleRange._to + 360 : newAngleRange._to;

        var diffA = (aEnd - aStart)/2;
        var diffB = (bEnd - bStart)/2;
        var avgA = (aStart + aEnd)/2;
        var avgB = (bStart + bEnd)/2;
        var cosDiffA = Math.Cos(diffA.ToRadians());
        var cosDiffB = Math.Cos(diffB.ToRadians());

        var resultFlag = MergeFlag.None;

        if (Math.Cos((avgA - bStart).ToRadians()).AboutGreaterThanOrEqual(cosDiffA))
            resultFlag |= MergeFlag.BStartInsideA;
        if (Math.Cos((avgA - bEnd).ToRadians()).AboutGreaterThanOrEqual(cosDiffA))
            resultFlag |= MergeFlag.BEndInsideA;
        if (Math.Cos((avgB - aStart).ToRadians()).AboutGreaterThanOrEqual(cosDiffB))
            resultFlag |= MergeFlag.AStartInsideB;
        if (Math.Cos((avgB - aEnd).ToRadians()).AboutGreaterThanOrEqual(cosDiffB))
            resultFlag |= MergeFlag.AEndInsideB;

        if (NotHasFlags(resultFlag, MergeFlag.BStartInsideA, MergeFlag.BEndInsideA,
            MergeFlag.AEndInsideB, MergeFlag.AStartInsideB))
        {
            resultAngleRange = null;
            return false;
        }

        if (HasFlags(resultFlag, MergeFlag.BStartInsideA, MergeFlag.BEndInsideA,
            MergeFlag.AEndInsideB, MergeFlag.AStartInsideB))
        {
            resultAngleRange = new Shadow(true);
            return true;
        }

        if (HasFlags(resultFlag, MergeFlag.BStartInsideA, MergeFlag.BEndInsideA))
        {
            resultAngleRange = this;
            return true;
        }

        if (HasFlags(resultFlag, MergeFlag.AEndInsideB, MergeFlag.AStartInsideB))
        {
            resultAngleRange = newAngleRange;
            return true;
        }

        if (HasFlags(resultFlag, MergeFlag.AEndInsideB, MergeFlag.BStartInsideA))
        {
            resultAngleRange = new Shadow(aStart, bEnd);
            return true;
        }

        if (!HasFlags(resultFlag, MergeFlag.AStartInsideB, MergeFlag.BEndInsideA))
        {
            resultAngleRange = new Shadow(bStart, aEnd);
            return true;
        }
        throw new InvalidOperationException("This should never happen.");
    }

    private static bool HasFlags(MergeFlag resultFlag, params MergeFlag[] flags)
    {
        return flags.All(flag => (resultFlag & flag) == flag);
    }

    private static bool NotHasFlags(MergeFlag resultFlag, params MergeFlag[] flags)
    {
        return flags.All(flag => (resultFlag & flag) != flag);
    }
}

MergeFlag

[Flags]
private enum MergeFlag : short
{
    None = 0,
    BStartInsideA = 1 << 0,
    BEndInsideA = 1 << 1,
    AStartInsideB = 1 << 2,
    AEndInsideB = 1 << 3
}

Using AboutGreaterThanOrEqual() and AboutLesserThanOrEqual() instead of >= and <= because of rounding error on edge cases. It is a method combine thin AboutEqual() from here and > or <.

_full represents AngleRange is a full circle. ToRadians() is a method that coverts degree into Radians.

Answer 3

Let me know if I missed something

public bool TryMerge(out AngleRange range)
{
    bool toInside = Inside(range.to);
    bool fromInside = Inside(range.from);

    // if not intersect
    // return false
    if (!toInside && !fromInside)
        return false;


    // if within
    // return true, out larger one
    if (toInside && fromInside)
    {
        //pick one
        range = new AngleRange(from, to);
        //range.to = to; //range.from = from;
        //range = this;
        return true;
    }


    //by default, should be here
    // return true, out a new one with merged bound
    range = new AngleRange(Math.Min(range.from, from),
                           Math.Max(range.to, to));
    return true;
}

Answer 4

Here is a much simpler and performant version which works fine also when start angle is higher then end angle (e.g. 350 - 10 degrees)

static bool GetMergedAngleRange(double start1, double end1, 
  double start2, double end2, 
  out double start, out double end)
{
  start1 = DoubleUtils.NormalizeAngle(start1);
  end1 = DoubleUtils.NormalizeAngle(end1);
  start2 = DoubleUtils.NormalizeAngle(start2);
  end2 = DoubleUtils.NormalizeAngle(end2);
  start = double.NaN;
  end = double.NaN;

  if (start1 > end1)
  {
    end1 += 360;
    start2 += 360;
    end2 += 360;
  }

  if (start2 > end2)
  {
    end2 += 360;
    start1 += 360;
    end1 += 360;
  }

  if (!(start1 < end2 && start2 < end1))
    return false;

  start = DoubleUtils.NormalizeAngle(Math.Min(start1, start2));
  end = DoubleUtils.NormalizeAngle(Math.Max(end1, end2));
  return true;
}