CGRect intersection gives surprising result due to floating point arithmetic

Development Core Libraries
1

Due to FP rounding, we have the following result:

let rect = CGRect(x: 100.33333333333333333333333, y: 0, width: 100, height: 100) let infinite = CGRect.infinite 
let intersection = infinite.intersection(rect) 
print(infinite.contains(rect)) // true 
print(intersection == rect) // false

I've filed a bug here but wanted to solicit input from the community about whether this is actually a bug. It seems inherent to me that if rect1.contains(rect2) == true, then rect1.intersection(rect2) == rect2.

More generally, this appears to be the behavior on macOS and iOS as well, and I'm curious about what the view is on feature parity vs. bug fixes. If there's a buggy implementation, do we value consistency with Apple platforms over fully correct implementations?

1 Like
2

I'm seeing the same issue. In my case,
the intersection of (0.0, 0.0, 375.0, 728.0) and (187.66666666666669, 50.0, 187.66666666666666, 135.66666666666666)
returns (187.66666666666669, 50.0, 187.33333333333331, 135.66666666666666)
where the width is off by one pixel (0.33333333...)
my bad, this is a legit case. :sweat_smile:

3

The width is correct. It is not off by one pixel.

The big rectangle's x range is 0 … 375.

The small rectangle's x range is 187 ⅔ … 375 ⅓.

Therefore the x range of the intersection is 187 ⅔ … 375.

The size of the intersection's x range is 375 - 187 ⅔ = 187 ⅓.

1 Like
4

Thanks yeah, you are correct. I crossed out my original wrong calculation.

5

The cause of this bug is the same as the cause of inequality in this short sample:

let a = 100.33333333333333333333333
let b = a + 100
let c = b - 100
print(b) // 200.33333333333331
print(a, c) // 100.33333333333333 100.33333333333331
assert(a == c) // Assertion failed
6

The following replicates the bug in a custom implementation and provides a fixed implementation:

extension CGRect {

    func intersection2(_ v: CGRect) -> CGRect {
        let left = max(minX, v.minX)
        let right = min(maxX, v.maxX)
        let top = max(minY, v.minY)
        let bottom = min(maxY, v.maxY)
        return CGRect(x: left, y: top, width: right - left, height: bottom - top)
    }

    func intersection3(_ v: CGRect) -> CGRect {
        let left = max(minX, v.minX)
        let right = min(maxX, v.maxX)
        let top = max(minY, v.minY)
        let bottom = min(maxY, v.maxY)

        let w: CGFloat
        if left == minX && right == maxX {
            w = width
        } else if left == v.minX && right == v.maxX {
            w = v.width
        } else {
            w = right - left
        }
        let h: CGFloat
        if top == minY && bottom == maxY {
            h = height
        } else if top == v.minY && bottom == v.maxY {
            h = v.height
        } else {
            h = bottom - top
        }
        return CGRect(x: left, y: top, width: w, height: h)
    }
}
7

Regarding the rect intersection problem in OP's post, here is my implementation:

public extension CGRect {

  func myIntersection(_ rect2: CGRect) -> CGRect {
    // if any is empty, return .zero
    guard !isEmpty, !rect2.isEmpty else {
      return .zero
    }

    // if any is null, return null
    guard !isNull, !rect2.isNull else {
      return .null
    }

    if isInfinite {
      return rect2
    } else if rect2.isInfinite {
      return self
    }

    // both rects are valid rects

    /**

       min(rect1.maxX, rect2.maxX)

                     │
                     │
                     │
                     ▼

         ■───────────●

                   ■───────────●

                   ▲
                   │
                   │
                   │
                   │

     max(rect1.minX, rect2.minX)

    */
    let x = max(minX, rect2.minX)
    let y = max(minY, rect2.minY)
    return CGRect(x: x, y: y, width: min(maxX, rect2.maxX) - x, height: min(maxY, rect2.maxY) - y)
  }
}
8
Note that your implementation still won't pass this test. 
        let rect = CGRect(x: 100.33333333333333333333333, y: 0, width: 100, height: 100)
        let otherRect = CGRect(x: 0, y: 0, width: 400, height: 400)
        let intersection = otherRect.intersection3(rect)
        print(rect)
        print(otherRect)
        print(intersection)
        assert(otherRect.contains(rect))
        assert(intersection == rect)
9
Arguably a better and more symmetric implementation of CGRect would be if it stored right/bottom instead of width/height. 
struct MyRect: Equatable {
    var left, top, right, bottom: CGFloat
    // TODO: corner cases 
    func intersection(_ v: MyRect) -> MyRect {
        let left = max(minX, v.minX)
        let right = min(maxX, v.maxX)
        let top = max(minY, v.minY)
        let bottom = min(maxY, v.maxY)
        return MyRect(left: left, top: top, right: right, bottom: bottom)
    }
    // TODO: corner cases 
    func contains(_ v: MyRect) -> Bool {
        left <= v.left && right >= v.right && top <= v.top && bottom >= v.bottom
    }
    var width: CGFloat { right - left }
    var height: CGFloat { bottom - top }
    var minX: CGFloat { left }
    var minY: CGFloat { top }
    var maxX: CGFloat { right }
    var maxY: CGFloat { bottom }
}

extension MyRect {
    init(x: CGFloat, y: CGFloat, width: CGFloat, height: CGFloat) {
        left = x
        top = y
        right = x + width
        bottom = y + height
    }
}

with "convenience" initialiser:

`init (x: CGFloat, y: CGFloat, width: CGFloat, height: CGFloat)`

in addition to the "main" one:

`init (left: CGFloat, top: CGFloat, right: CGFloat, bottom: CGFloat)`

Then intersect would be simpler and more reliable....

... and the following simple test would now fail:

    let rect = MyRect(x: 100.33333333333333333333333, y: 0, width: 100, height: 100)
    assert(rect.width == 100) // 99.99999999999999 != 100

I see these options to "handle all cases correctly":

  • "denial". ignore the issues of CGRect. Probably the best one, and definitely the easiest one.

  • "betterment". switch to storing right/bottom and then ignore the different set of new issues (see above). This is a breaking change, so only possible in, say, CoreGraphics v2 or whatever better is invented after CoreGraphics.

  • "cumbersome". invest in a more elaborate scheme where you store, say:

    // Two of the following will be set, the remaining one should be nil:
    var left: CGFloat?
    var right: CGFloat?
    var width: CGFloat?
    ...

    and handle all cases (lot's of code). Likewise, this is a breaking change, so only possible in, say, CoreGraphics v2 or whatever better is invented after CoreGraphics.

  • "tolerance". compare coordinates with some tolerances. It's tricky to do correctly in general case and there'll be issues with transitivity a == b, b == c but a <> c, which might or might not be a problem in a particular project. Strictly speaking this is also a breaking change, albeit less breaking than the other two.

  • "fractional". Switch from floating-point to fixed point coordinates (say 32 bits for integer part and 32 bit for fractional part). If I were creating "CoreGraphics v2" from scratch that would be my choice.

Edit. Added the fractional choice above.

10

CGRect has been public API on Apple's platforms for multiple decades; suffice to say that the basic type definitions are not going to change. (Also, CG is a library for screen graphics, not exact geometry primitives; from that perspective, this is a non-problem). If you want to do exact geometry use a library intended to do exact geometry. That entails a very different set of tradeoffs than CG, because that's not what CG is for. A hypothetical "CoreGraphics 2" still wouldn't be that library, because that's not what CG is for.

I should also note that even if it were possible, switching to right/bottom just moves the "problem". Now size queries return the "wrong answer" because the difference between two representable endpoints is not generally representable in floating-point.

9 Likes