3
\$\begingroup\$

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.

\$\endgroup\$
7
  • \$\begingroup\$ I dont understand why 15 to 0 would not be a valid range? As in why does the direction matter? If any range from high to low is invalid why not disallow them or make them point in the positive direction? \$\endgroup\$
    – Niels
    Nov 14, 2016 at 9:55
  • \$\begingroup\$ @Niels It is because the angle is start from 15 degree to 0 degree. The range is count clockwise. The order matters. Therefore, 0 to 15 is not in range. \$\endgroup\$
    – Joshua
    Nov 14, 2016 at 10:01
  • \$\begingroup\$ so -10 would be within the range for 15 to 0? \$\endgroup\$
    – Niels
    Nov 14, 2016 at 12:49
  • \$\begingroup\$ @Niels Yes, you know what I mean. \$\endgroup\$
    – Joshua
    Nov 14, 2016 at 12:53
  • \$\begingroup\$ Your current code leaves all numbers to be within the range whenever from is larger than to (f.e.. -150 as well as 150 with range 20 - 0). I think you can make this easier on yourself by supporting the same ranges in both the angles and the angleranges. Just support negative angles in both of them and sort them on creation to have from always be smaller than to. Unless I'm misunderstanding you \$\endgroup\$
    – Niels
    Nov 14, 2016 at 13:00

4 Answers 4

1
\$\begingroup\$

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.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ I am looking for a elegant answer to do this though. I will check this tomorrow. \$\endgroup\$
    – Joshua
    Nov 14, 2016 at 12:51
  • \$\begingroup\$ What do you mean by elegance? This captures the behaviour in a way that's easy to understand and maintain. Tends to be more important than efficiency. And even in the efficiency case it's only a few conditionals. \$\endgroup\$ Nov 14, 2016 at 13:09
0
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ The TryMerge method is incredibly difficult to follow. It might be faster than mine but it's going to be a tough one to maintain in its current state. You should definitely consider refactoring it. \$\endgroup\$ Nov 15, 2016 at 9:23
0
\$\begingroup\$

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;
}
\$\endgroup\$
0
\$\begingroup\$

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;
}
\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .