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\$
  • \$\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 '16 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 '16 at 10:01
  • \$\begingroup\$ so -10 would be within the range for 15 to 0? \$\endgroup\$ – Niels Nov 14 '16 at 12:49
  • \$\begingroup\$ @Niels Yes, you know what I mean. \$\endgroup\$ – Joshua Nov 14 '16 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 '16 at 13:00
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\$
  • 1
    \$\begingroup\$ I am looking for a elegant answer to do this though. I will check this tomorrow. \$\endgroup\$ – Joshua Nov 14 '16 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\$ – Huxellberger Nov 14 '16 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\$
  • \$\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\$ – Huxellberger Nov 15 '16 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\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.