Computing rotated rectangle intersection area using C++

Question

I am trying to calculate the intersection area of two arbitrarily sized and rotated rectangles using C++. I have found some information on non-rotated rectangles but very little on rotated and different sized rectangles. I would like to create a C/C++ program to do this.

Does anyone out there have any information/hints or better yet, some simple code that could help?

Thank you in advance for any assistance.

With the assumption that you have the vertices of the rectangles as x,y coordinates, you could look for intersection of lines formed by adjacent vertices in one rectangle with the other one: https://www.geeksforgeeks.org/check-if-two-given-line-segments-intersect/ — nahzor, Feb 27 '21 at 02:23
Look up a mathematics book and search for integral calculus and/or trigonometry. — paladin, Feb 27 '21 at 02:26

score 2 · Accepted Answer · answered Feb 27 '21 at 02:45

2

I think the easiest way to do this is to clip one rectangle against the other using the Sutherland-Hodgman algorithm: https://en.wikipedia.org/wiki/Sutherland%E2%80%93Hodgman_algorithm

Then you find the area of the resulting polygon using the shoelace formula: https://en.wikipedia.org/wiki/Shoelace_formula

answered Feb 27 '21 at 02:45

Matt Timmermans

53,709
3
46
87

I disagree, OP speaks about rectangulars. Rectangulars have this shiny property of being rectangular. Taking use of that is a good idea. – paladin Feb 27 '21 at 03:12
1

I think you'd feel differently if you tried to formulate a more specific answer than "use trigonometry". – Matt Timmermans Feb 27 '21 at 12:44

score 1 · Answer 2 · answered Feb 27 '21 at 19:01

There is already a question (with six answers) about that, however the OP there was interested in the approximate area of intersection.

If you need an exact solution, then you'll have to take into account many corner cases, which make geometrical problems so difficult to be solved correctly on a real computer with limited data precision - for example, see here.

Fortunately, there is already a number of high-quality computational geometry libraries, which can solve this kind of problems using exact computations with exact numbers. One of them is CGAL, which is a joint project of many universities, well developed and tested. However, this library doesn't support rotated rectangles as a separate entity - you'll need to work with general polygons. So, your code will look like this:

#include <iostream>
#include <vector>

#include <CGAL/Boolean_set_operations_2.h>
#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Polygon_2.h>
#include <CGAL/Polygon_with_holes_2.h>

using Kernel = CGAL::Exact_predicates_exact_constructions_kernel;
using Polygon = CGAL::Polygon_2<Kernel>;
using PolygonWithHoles = CGAL::Polygon_with_holes_2<Kernel>;
using Point = Polygon::Point_2;

int main()
{
  // ------ define polygon #1
  const std::vector<Point> pts1{/* ... polygon #1 vertices ... */};
  const Polygon p1(pts1.cbegin(), pts1.cend());
  // ------ define polygon #2
  const std::vector<Point> pts2{/* ... polygon #2 vertices ... */};
  const Polygon p2(pts2.cbegin(), pts2.cend());
  // ------ compute intersection - you'll get a single polygon without holes!!!
  std::vector<PolygonWithHoles> res;
  CGAL::intersection(p1, p2, std::back_inserter(res));
  // ------ output area of intersection
  std::cout << res[0].outer_boundary().area() << std::endl;
}

If you don't care about robustness of geometric calculations, then this library still can help you - you can choose regular double numbers to represent coordinates. In this case you'll get better performance with a possibility of getting wrong answers in some cases.

Great answer. It worked for me. I've also added a complete working example, based on yours, as another answer. — Ícaro Pires, Apr 25 '21 at 14:54

score 1 · Answer 3 · answered Apr 25 '21 at 15:02

A complete working example, based on @HEKTO answer:

#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Boolean_set_operations_2.h>
#include <CGAL/Polygon_2.h>
#include <CGAL/Polygon_with_holes_2.h>

using Kernel = CGAL::Exact_predicates_exact_constructions_kernel;
using Polygon = CGAL::Polygon_2<Kernel>;
using Point = CGAL::Point_2<Kernel>;
using PolygonWithHoles = CGAL::Polygon_with_holes_2<Kernel>;

int main() {
  const std::array<Point, 4> points1{Point(1.3, 2.5), Point(2.7, 2.5), Point(2.7, 5.5), Point(1.3, 5.5)};
  const Polygon polygon1(points1.cbegin(), points1.cend());

  const std::array<Point, 4> points2({Point(1.47, 2.65), Point(2.63, 2.34), Point(3.3, 4.85), Point(2.14, 5.16)});
  const Polygon polygon2(points2.cbegin(), points2.cend());

  std::vector<PolygonWithHoles> intersections;
  CGAL::intersection(polygon1, polygon2, std::back_inserter(intersections));

  std::cout << "Intersection area: " << intersections[0].outer_boundary().area() << std::endl;

  return EXIT_SUCCESS;
}

Output: Intersection area: 2.34555.

An illustration from the rectangles:

score -2 · Answer 4 · answered Feb 27 '21 at 03:29

-2

Use the properties of your rectangulars to your advantage. Rectangulars are rectangular! This makes it easy to calculate them using trigonometry or integral calculus.

PS using trigonometry is probably easier in your case.

answered Feb 27 '21 at 03:29

paladin

765
6
13

Computing rotated rectangle intersection area using C++

4 Answers4