Floating Point Interval

Floating Point Interval for Swift

When working on code where I'm doing a lot of calculation in geometric spaces such as layout, animation, or color, I often find myself using the concept of a floating point interval: a closed range on the floating point number line. However, the existing ClosedRange requires its bounds to be ordered, which makes it less than useful for geometric calculations where a coordinates can travel or be interpolated in either direction.

I have developed a pure Swift type, Interval along with an operator to construct such intervals that I have found very useful, and think others might find it useful too. It might be worth considering including in the Standard Library.

The Swift package including unit tests is available here.

Definition

The basic type is defined as follows:

public struct Interval<T: FloatingPoint> : Equatable, Hashable {
    public typealias Bound = T

    public let a: Bound
    public let b: Bound

    public init(_ a: Bound, _ b: Bound) {
        self.a = a
        self.b = b
    }
}

Interval Formation Operator

In addition, a new interval formation operator is introduced:

infix operator .. : RangeFormationPrecedence

public func .. <T>(left: T, right: T) -> Interval<T> {
    Interval(left, right)
}

This operator, like the range formation operators, makes it easy to create Intervals in code:

let i = 0..100
let j = 100..3.14

In practice I have not found any trouble keeping the new operator .. and the existing range formation operators ... and ..< distinct in my mind.

Geometric Queries

Unlike ClosedRange, a and b can be in any order. This means this type has to deal with the various cases that entails, and thus it also provides computed attributes like:

isAscending is a < b?
isDescending is a > b?
isEmpty is a == b? This is different from ClosedRange, which always returns true.
reversed Interval(b, a)
normalized returns Interval with values ordered so isAscending is true
min min(a, b)
max max(a, b)

Because Interval is designed to be used with geometric calculations, it contains a number of geometric operators:

extent b - a
contains Does self contain a particular coordinate?
contains Does self fully contain another Interval?
intersects Does self intersect (overlap) another Interval?
intersection Returns an Interval which is the overlapping part of self and another Interval, or nil if they don't intersect.
union Returns an Interval subtending the greatest extents of self and another interval.

Linear Interpolation

One place Interval shines is when you need to do linear interpolation. An extension on FloatingPoint makes every one of these types interpolable into and out of normalized unit spaces and between spaces.

Interpolation is not clamped, so interpolating a value outside the interval 0..1 to another interval results in extrapolation.

extension FloatingPoint {
    /// The value linearly interpolated from the unit interval `0..1` to the interval `a..b`.
    public func interpolated(to i: Interval<Self>) -> Self

    /// The value linearly interpolated from the interval `a..b` into the unit interval `0..1`.
    public func interpolated(from i: Interval<Self>) -> Self

    /// The value linearly interpolated from the interval `i1` to the interval `i2`.
    public func interpolated(from i1: Interval<Self>, to i2: Interval<Self>) -> Self
}

Here is an example of using Interval to interpolate between two colors:

import Interval

struct Color : CustomStringConvertible {
    let r, g, b: Double

    private func f(_ n: Double) -> String { return String(format: "%.2f", n) }

    var description: String { "(r: \(f(r)), g: \(f(g)), b: \(f(b)))" }

    func interpolated(to other: Color, at t: Double) -> Color {
        Color(
            r: t.interpolated(to: r..other.r),
            g: t.interpolated(to: g..other.g),
            b: t.interpolated(to: b..other.b)
        )
    }
}

let darkTurquoise = Color(r: 0, g: 0.8, b: 0.81)
let salmon = Color(r: 0.98, g: 0.5, b: 0.45)

for t in stride(from: 0.0, to: 1.1, by: 0.1) {
    let c = darkTurquoise.interpolated(to: salmon, at: t)
    print(String(format: "%.1f", t) + ": " + c.description)
}

When run, the output below is produced. Notice that the r value is increasing while g and b are decreasing.

0.0: (r: 0.00, g: 0.80, b: 0.81)
0.1: (r: 0.10, g: 0.77, b: 0.77)
0.2: (r: 0.20, g: 0.74, b: 0.74)
0.3: (r: 0.29, g: 0.71, b: 0.70)
0.4: (r: 0.39, g: 0.68, b: 0.67)
0.5: (r: 0.49, g: 0.65, b: 0.63)
0.6: (r: 0.59, g: 0.62, b: 0.59)
0.7: (r: 0.69, g: 0.59, b: 0.56)
0.8: (r: 0.78, g: 0.56, b: 0.52)
0.9: (r: 0.88, g: 0.53, b: 0.49)
1.0: (r: 0.98, g: 0.50, b: 0.45)

Interoperability with ClosedRange

To provide interoperability with ClosedRange, conversion constructors are provided. When converting from Interval to ClosedRange, the bounds are normalized so a <= b.

extension Interval {
    public init(_ r: ClosedRange<Bound>)
}

extension ClosedRange where Bound: FloatingPoint {
    public init(_ i: Interval<Bound>)
}

Interoperability with Random Number Generation

Extensions on Float, Double, and CGFloat provide the ability to produce random numbers in an interval.

extension Double {
    public static func random(in interval: Interval<Self>) -> Self
    public static func random<T: RandomNumberGenerator>(in interval: Interval<Self>, using generator: inout T) -> Self
}
5 Likes

Any reason the bound is restricted to BinaryFloatingPoint instead of the more general FloatingPoint?

1 Like

Good catch! Yes, the Bound should be FloatingPoint. I've fixed that in the proposal and the repo.

Interval and Range were merged together earlier in Swift’s evolution. Is there functionality here that isn’t served by extensions on StrideThrough and/or ClosedRange?

Always returns false, surely?

According to your post, Interval(a,b).isEmpty == (Interval(a,b).extent == 0), but presumably Interval(a,b).contains(a) and Interval(a,b).contains(b) are both true — otherwise you wouldn't have described Interval as closed.

In Swift semantics, isEmpty typically means "doesn't contain anything", but clearly it does in this case.

I'm not sure isEmpty should be there at all. Explicitly testing for a zero extent seems clearer (and slightly fewer characters to type).

Trivially, yes. The (finite) number of distinct Interval values is twice the number of distinct ClosedRange values.

I agree with @QuinceyMorris that this should be false. In a closed real interval, if both endpoints are the same, then the interval contains the endpoint as its only element. For example, [π, π] contains a single element π.

Given that (or, if) an interval isn't empty when a == b, is it ascending or descending?

Also given that (or, if) an interval isn't empty when a == b, how do you construct an empty interval? Is an empty interval ascending or descending?

I didn’t find any custom Equatable conformance in your source, so I assume that in your current implementation, Interval(a, b) != Interval(b, a)? I feel that intervals should be equal if they differ only in direction.

I think the type might be better named as ClosedRealInterval, since it doesn't seem to be able to model anything other than closed real intervals.

FloatingPoint has .infinity for positive infinity, but you might need to ban it for both a and b for 2 reasons: The intervals are all closed, so the endpoints can't be infinity unless you want to model intervals of extended real numbers. FloatingPoint doesn't have a value for negative infinity, so you can only model right-unbounded intervals but not left unbounded.


semi-related:

A few months ago, I pitched a different Interval type that intends to model all kinds of intervals (open, closed, bounded, unbounded, empty, degenerate, proper, ascending, descending) generic over almost all Comparable types.

However, it has some significant disadvantages when it comes to type-checked correctness and performance of iteration. So, RangeExpression types and UnboundedRange are preferred. I've since spun it off into its own library, but haven't updated it much recently.

I don't think your Interval has any of the disadvantages that mine does, so long as you avoid .infinity.

Right. And what do those additional values allow users to do that can’t be accomplished with extensions to ClosedRange and/or StrideThrough?

The order of the bounds affects the results of interpolation, for example:

(0.2).interpolated(to: 1..6) == 2.0
(0.2).interpolated(to: 6..1) == 5.0

This behavior—if it is even desirable (which I would argue against, as it is likely to be surprising with any values that aren’t constants)—does not require a new type. Precisely because there is no check requiring any ordering of the two bounds, they can be given as separate parameters, or as a tuple.

I ask this question because, besides the interpolation function just discussed, the APIs presented here appear to be implemented on range types already or are ways of spelling binary operations on two values—a < b, a > b, a == b, a - b, max(a, b), min(a, b), swap(&a, &b)—and in the latter case, we would rather want to encourage people not to encapsulate the two numbers into another type for such functionality.

As I designed Interval with predominantly geometric purposes in mind, Interval.isEmpty here is analagous to CGRect.isEmpty: It returns true if any geometric space is subtended, and false otherwise. From the set theoretic perspective, the set of all points in a closed range is never empty, and this is the definition that ClosedRange uses. However, having an attribute that always returns true seems rather less than utilitarian unless there was a conformance to a protocol where some conformers return all possibilities. This is true for ClosedRange, which inherits its isEmpty attribute from its conformance to the Range protocol, but not true for Interval, which does not conform to Range.

As stated by @bjhomer, the ordering of bounds a and b in Interval is a non-trivial piece of data that is not encoded in any way by ClosedRange. To do something similar with ClosedRange you must separately add this data by using stride(), StrideThrough or something similar, which means you need to keep the direction of stride separate somewhere. This is not an issue with Interval, which implicitly encodes this information. For geometric purposes at least, this is a huge win.

In my experience this behavior is highly desirable. See the example above of interpolating between two colors using Interval. How would you code that using ClosedRange?

I did find any custom Equatable conformance in your source, so I assume that in your current implementation, Interval(a, b) != Interval(b, a) ? I feel that intervals should be equal if they differ only in direction.

Perhaps Interval should be renamed DirectedInterval or something similar because the direction from a to b is integral to its function and purpose. So Interval(a, b) != Interval(b, a) when a != b is always true. To perform an undirected comparison you would do i1.normalized == i2.normalized, where i1 and i2 are Intervals.

And yes, I am using Swift's default synthesized conformance to Equatable and Hashable, which seem suitable to the purpose of the type.

I don't think your Interval has any of the disadvantages that mine does, so long as you avoid .infinity .

I don't check for .infinity or .nan at construction time, but I do provide an .isFinite check attribute, and my linear interpolation implementations do contain asserts that catch intervals with infinite bounds and possible divide by zero conditions.

In that case, your Interval shares a similar weakness as mine, where its correctness in some operations can not be guaranteed at compile time.

This is a tradeoff between correctness and performance. I expect Interval to be used in a lot of situations where guaranteed correctness is less important than performance.

What’s your gain in performance?

I understand this, but to rephrase my question: when do you need this piece of data? Among the APIs demonstrated, it is used for interpolate, for which situation see below:

As I noted above, I would use a tuple, or two separate parameters. What is gained by creating a type for this, given that it enforces no invariants about the two values (which, after all, is what distinguishes this type from range types to begin with)?

If there is sufficient demand, such asserts could be placed in the constructors. Currently Interval is also immutable, so whether a and b should be let or var is somewhat of an open issue, but if they are changed to var then such checks would also have to be done at assignment time.

Terms of Service

Privacy Policy

Cookie Policy