# Modeling and computing intersection between continuous intervals

I created the class ContinuousDimensionInterval, to model an interval of a continuous dimension interval, presented below.

namespace Minotaur.Math.Dimensions {
using System;

public sealed class ContinuousDimensionInterval: IDimensionInterval {

public int DimensionIndex { get; }

public ContinuousDimensionInterval(
int dimensionIndex,
DimensionBound start,
DimensionBound end
) {
if (dimensionIndex < 0)
throw new ArgumentOutOfRangeException(nameof(dimensionIndex) + " must be >= 0.");

DimensionIndex = dimensionIndex;
Start = start;
End = end;
}

public bool Contains(float value) {
if (float.IsNaN(value))
throw new ArgumentOutOfRangeException(nameof(value));

if (value > Start.Value && value < End.Value)
return true;
if (Start.IsInclusive && value == Start.Value)
return true;
if (End.IsInclusive && value == End.Value)
return true;

return false;
}
}
}


I felt the need to create a struct, DimensionBound, to represent the bounds of an interval, since they may be inclusive or exclusive.

namespace Minotaur.Math.Dimensions {
using System;

public DimensionBound(float value, bool isInclusive) {
if (float.IsNaN(value))
throw new ArgumentOutOfRangeException(nameof(value) + " can't be NaN.");

Value = value;
IsInclusive = isInclusive;
}
}
}


I'd like to receive some feedback on the implementation of both classes.

1. Should I disallow the construction of DimensionBound with value=infinity and inclusive=true?
2. Is my decision to make DimensionBound a struct reasonable? It feels struct-like to me...
3. Should DimensionBound implement IEquatable<DimensionBound>?
4. Am I over-engineering the whole thing by creating a class to represent the bounds of an interval?

Here an example of how the class is used:

private static bool IntersectsContinuous(ContinuousDimensionInterval lhs, ContinuousDimensionInterval rhs) {
// @Improve performance?
// @Verify correctness
var aStart= lhs.Start;
var aEnd = lhs.End;

var bStart = rhs.Start;
var bEnd = rhs.End;

if (aStart.Value > bEnd.Value)
return false;
if (aStart.Value == bEnd.Value)
return aStart.IsInclusive && bEnd.IsInclusive;

if (bStart.Value > aEnd.Value)
return false;
if (bStart.Value == aEnd.Value)
return bStart.IsInclusive && aEnd.IsInclusive;

return true;
}

• What's the use of DimensionIndex? – IEatBagels Aug 23 at 17:40
• It is used to identify a dimension. It could be a string "DimensionIdentifier", but in my case a int suffices. – Trauer Aug 23 at 20:43

## Review

• You are constrained to float which makes your class only usable for a limited number of scenarios. I would like to be able to work with int, double, DateTime, MyCustomEntity, ..
• You should not need to care about special cases as unbounded or NaN. NaN should be filtered out beforehand, since it is unusable for comparison. Unbounded and bounded values should be compared by using the built-in interface IComparable.
• Intersection of continuous data when 2 edges match requires both edges to be IsInclusive in your specification. I would argue that only one of them should require this flag. Adjacent items that meet each other form an intersection ( [source required] ).
• Your struct is immutable, which is proper design. Whether or not to make a class instead, depends on how you would like to use this. I tend to prefer class more than struct. Note that a struct has an inherent default value, while a reference type is null by default. How would you distinguish a default value from a value that happens to have the same value? This is one reason to go with a class, unless you cope with this issue by using a Nullable<T> and accepting the overhead it provides.
• It is good practice to override GetHashCode() and Equals().

## Suggestions

1201ProgramAlarm's answer suggests to use IComparable on DimensionBound, but I would use it on the generic type parameter.

public class DimensionBound<T> where T : IComparable<T>
{

public DimensionBound(T value, bool isInclusive)
{
Value = value;
IsInclusive = isInclusive;
}
}


The interval could then be refactored to compare the values. Note that I would provide a convenience constructor accepting an inclusive start and exclusive end (which is considered common practice when dealing with continuous data).

I would also favour instance methods over the static comparison. Furthermore, I would argue the purpose of the dimension in this class. I would remove it and call the class Interval. You can always create an additional class or use a tuple (int, Interval) to include the dimension.

public sealed class Interval<T> where T : IComparable<T>
{

public Interval(T start, T end)
: this(ew DimensionBound<T>(start, true), new DimensionBound<T>(end, false))
{
}

public Interval(DimensionBound<T> start, DimensionBound<T> end)
{
Start = start;
End = end;
}

public bool Contains(T value)
{
// method body ..
}

public bool Intersects(Interval<T> other)
{
// method body ..
}
}


If we don't change your specification and require both edges to be inclusive when 2 intervals meet, we could implement Intersects (Contains is similar) as follows (comments added for code review purposes only):

public bool Intersects(Interval<T> other)
{
// compare start to other end
var compareToStart = Start.Value.CompareTo(other.End.Value);

// no intersection possible; instance starts after other is finished
if (compareToStart == 1) return false;

// both intervals meet but at least one of the bounds is exclusive, so no intersection
if (compareToStart == 0 && !(Start.IsInclusive && other.End.IsInclusive)) return false;

// compare end to other start
var compareToEnd = End.Value.CompareTo(other.Start.Value);

// no intersection possible; instance finishes before other is started
if (compareToEnd == -1) return false;

// both intervals meet but at least one of the bounds is exclusive, so no intersection
if (compareToEnd == 0 && !(End.IsInclusive && other.Start.IsInclusive)) return false;

return true;
}


This works with float, or any other IComparable<T>.

Assert.IsTrue(new Interval<float>(0, 1).Intersects(new Interval<float>(0.5f, 1.5f));

• oh, you actually get the question... – t3chb0t Aug 23 at 5:40
• @t3chb0t Interval logic is fun: en.wikipedia.org/wiki/Allen%27s_interval_algebra. Or with 3 intervals: ics.uci.edu/~alspaugh/cls/shr/allen.html. – dfhwze Aug 23 at 5:43
• CR is more demanding than school... I'm not done studying your last question about sudoku yet and here's the next topic already... this is cool ;-] – t3chb0t Aug 23 at 5:47
• I'm not convinced by bullet 3: maybe I don't know the pure maths underneath, but unless there exists a value that both intervals contain, I don't think that would be considered an intersection. – VisualMelon Aug 23 at 7:21
• ... I'm also not convinced it would be of any real use: I think it would be better to leave deciding how to compare these things to whoever is using them, because they will (hopefully) have a meaningful interpretation. (argh, chat button went away; I'm happy to move if you are) – VisualMelon Aug 23 at 7:50

The ContinuousDimensionInterval constructor should validate that it has valid bounds, i.e. Start <= End (and if they are equal, at least one of them should be inclusive). This is more likely to be a programming or logic error than an attempt to create an empty interval (which may be something you want to more explicitly support by providing a SetEmpty member).

DimensionBound should have some sort of comparison operations defined for it. The full IComparable interface, not just IEquatable. This would also make validating the Start and End bounds of ContinuousDimensionInterval easier.

2. A struct in C# is a value type, not a reference type, so it will always be copied when being passed around. There are other restrictions as well. Only you can decide if they are acceptable for you. (My personal preference would be to lean towards making it a class.)
3. As I mentioned above, you should implement the full IComparable interface for DimensionBound.
• I'm not sure making DimensionBound implemented IComparable would make sense: can you elaborate on how you'd propose it be done? I would only want to implement IComparable if there was a natural and meaningful ordering (if you need to order them otherwise, use an IComparer), and I'm not convinced there is one here. – VisualMelon Aug 22 at 22:43
• Having SetEmpty in a readonly struct sounds strange. – Roland Illig Aug 23 at 5:46