使用C++计算旋转矩形相交面积

Question

我正在尝试使用 C++ 计算两个任意大小和旋转的矩形的交集面积。我发现了一些关于非旋转矩形的信息，但关于旋转和不同大小的矩形的信息很少。我想创建一个 C/C++ 程序来执行此操作。

有没有人有 information/hints 或更好的一些简单代码可以提供帮助？

提前感谢您的帮助。

Answer 1

我认为最简单的方法是使用 Sutherland-Hodgman 算法将一个矩形夹在另一个矩形上：https://en.wikipedia.org/wiki/Sutherland%E2%80%93Hodgman_algorithm

然后使用鞋带公式求得多边形的面积：https://en.wikipedia.org/wiki/Shoelace_formula

Answer 2

充分利用矩形的属性。长方形就是长方形！这使得使用三角学或积分学计算它们变得容易。

PS 在您的情况下使用三角函数可能更容易。

Answer 3

已经有一个 question（有六个答案），但是那里的 OP 对近似交叉区域感兴趣。

如果您需要精确的解决方案，那么您将不得不考虑许多极端情况，这使得几何问题很难在真实计算机上正确解决有限的数据精度 - 例如，参见here。

幸运的是，已经有一些高质量的计算几何库，可以用精确的数字精确计算来解决这类问题。其中之一是 CGAL，它是许多大学的联合项目，经过精心开发和测试。但是，此库不支持将旋转矩形作为单独的实体 - 您需要使用一般多边形。因此，您的代码将如下所示：

#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;
}

如果你不关心几何计算的鲁棒性，那么这个库仍然可以帮助你——你可以选择常规的double数字来表示坐标。在这种情况下，您将获得更好的性能，但在某些情况下可能会得到错误的答案。

Answer 4

一个完整的工作示例，基于@HEKTO 回答：

#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;
}

输出：Intersection area: 2.34555.

来自矩形的插图：

使用C++计算旋转矩形相交面积

Computing rotated rectangle intersection area using C++

c++

intersection

rectangles

area

computational-geometry