Add functions to compute Union & Intersection Area of two rectangles

[AlexandreBrown]

Feature Request

Use Case

• When doing object detection using deep learning, we have to do what is known as non-max supression. To do so we need to compute the IoU (Intersection over Union) of two rectangles (compute area of the union and the area of the intersection of the two rectangles). Adding it to KMath would allow us to make use of it for the IoU computation without implementing the area computation part from scratch. Even though it is not very hard to do, I think it could be a nice addition to KMath since its usage can be much broader than just for deep learning, area computation is pretty generic in maths.

Proposal

• A function/method similar to getIntersectionArea(Rect1, Rect2)
• A function/method similar to getUnionArea(Rect1, Rect2)
  or
• A single function getIoU(Rect1, Rect2)
  Ideally the solution should be mockable so that library users have more freedom.

[altavir]

Thanks a lot for the request. It seems like a good addition to kmath-geometry package. We need to implement shapse first though. If you have any understanding how shape API should look like, it would be welcome.

[altavir]

And a clarification question. In object detection you probably search for intersection of rectangles alongside axis. Is it always this way or do we need also include rotations?

[AlexandreBrown]

@altavir That's correct, you can expect the rectangles to always be in the same orientation.

You can think of it like an N x N grid where each cell might have a rectangle that might or might not be larger than the grid cell.

So my use case doesn't need rotation.

[altavir]

Here is the code you can use for now for that purpose: https://pl.kotl.in/5_rip0Gfi

import kotlin.math.min
import kotlin.math.max

infix fun ClosedRange<Double>.intersect(other: ClosedRange<Double>): ClosedFloatingPointRange<Double>? {
    val left = max(start, other.start)
    val right = min(endInclusive, other.endInclusive)
    return if(left<=right){
        left..right
    } else {
        null
    }
}

data class Rectangle(val x : ClosedFloatingPointRange<Double>, val y: ClosedFloatingPointRange<Double>)

val Rectangle.surface get() = (x.endInclusive - x.start)*(y.endInclusive - y.start)

infix fun Rectangle.intersect(other: Rectangle): Rectangle?{
    val xIntersect = x.intersect(other.x) ?: return null
    val yIntersect = x.intersect(other.x) ?: return null
    return Rectangle(xIntersect, yIntersect)
}

fun main(){
    val res = Rectangle(0.0..1.0, 0.0..1.0) intersect Rectangle(0.5..1.5, 0.5..1.5)
    println(res?.surface)
}

We will deffinitely look further into geometry package for more complex cases.