Search code examples
swiftmathcomputer-visiongeometrycomputational-geometry

Intersection over union for rectangles with different orientation

I need to implement an algorithm in swift to find the intersection over union (IoU) between two rectangles with different orientations in 2-dimensional space. I could not find any tutorials or sample codes to teach how to implement such an algorithm.

Could someone provide relevant resources?

Solution

  • You can use O'Rourke algorithm for calculation of intersection of two convex polygons. C and Java code is availaible on the page for book "Computational Geometry in C"

    enter image description here

    Algorithm traverses edges of polygons until it finds intersection (using orientation test). After intersection it chooses "the most inner" edge from two possible next ones to build intersection core polygon (always convex).

    When you have ordered list of vertices, you can calculate polygon area with shoelace formula.

    To get area of union, we can calculate (thanks to Yves Daoust for hint)

    Area(Union) = Area(P) + Area(Q) - Area(Intersection)