Intersection over union calculation

Questions / Help
1

Hi,

I am trying to calculate the intersection over union for two oriented rectangles, like this picture;

I know there are lots of algorithms for this so I am curious if anyone has seen an implementation. Rectangles are stored as either four corners in counterclockwise order or {{center x, center y}, area, aspect, orientation} tuples.

Otherwise, any thoughts on how to accomplish this in elixir? I will be computing IoU for all pairwise combinations of two sets of ~100 rectangles for a soft-realtime application.

So something like:


defmodule Boxes do
  defstruct center: {0,0}, area: 0, aspect: 1.0, orientation: 0
  @type t :: %__MODULE__{center: {number(), number()}, area: number(), aspect: number(), orientation: number()}
  
  @doc """
  Computes the intersection over union score for two oriented rectangles.
  """
  def iou(box1, box2) do
    
  end
  

  def iou_batch(boxes1, boxes2) do
    Enum.map(boxes1, fn box1 -> Enum.map(boxes2, fn box2 -> iou(box1, box2) end) end)
  end

  @spec corners(__MODULE__.t()) :: list(number())
  @doc """
  Computes the corners of the box given a state vector
  """
  def corners(box) do
    [
      ... # you can assume this function works
    ]
  end
end
2

I haven’t seen an Elixir implementation. I suspect you will just have to code it up.

There is a topology library (search hex for “topo” - GitHub repo is here: GitHub - pkinney/topo: A Geometry library for Elixir that calculates spatial relationships between two geometries) that has functions to detect whether polylines intersect or overlap, but it doesn’t calculate the amount of overlap. You could take a look at that for some code examples.

I wouldn’t worry too much about performance - 100 x 99 x some basic arithmetic won’t take long at all on GHz (billions of calcs / second) CPUs.

The general approach would be:

  1. Convert all representations of rectangles into a common format
  2. Compute the polygon resulting from the intersection of the two rectangles - stack overflow has a couple of algorithms Calculate the area of intersection of two rotated rectangles in python - Stack Overflow and algorithm - Area of Intersection of Two Rotated Rectangles - Stack Overflow - another library from pkinney will give you intersections of lines - GitHub - pkinney/segseg_ex: Segment-segment intersection classifier and calculator for Elixir
  3. Compute the area of the resulting polygon. That would be the intersection. The union would be the area of the two rectangles minus the intersection.