Modeling and computing intersection between continuous intervals

Posted on

Problem

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;
}
``````

Solution

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));
``````

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`.