Search code examples
javageometrycomputational-geometryintersectionrectangles

how to calculate area of Intersection of Two Rotated Rectangles in Java?

I have two 2D rectangles, defined as an (x,y,height,width,angle). I need to calculate the approximate area of intersection of these two rectangles.

enter image description here

How can I do that in JAVA? Is it any library in JAVA such as shapely package in Python that can be use for this goal ? (I'm not sure How shapely package calculates area of intersection of two rectangles but I think it works well for this goal)

Solution

  • You can use the Sutherland-Hodgman clipping algorithm to compute the intersection polygon (from triangle to octagon). It amounts to clipping one of the polygons inside the four half-planes that define the other. It is probably worth to specialize the algorithm to rectangles, and maybe to make the clipping polygon axis aligned (as suggested by Joop).

    Then the area is computed by the shoelace formula.

    There is an efficient algorithm for convex polygon intersection in linear time by Toussaint (http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.50.7083), but it is uneasy to implement and will probably bring little benefit for such small targets.