Computing rotated rectangle intersection area using C++

Viewed 211

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.

4 Answers

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.

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: Intersection between the rotated rectangles

Calculating intersection with Integral

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.

Related