c++ - 我有大量边界框，如何计算重复项？

Question

我有一个边界框列表，我想知道如何计算哪些是冗余/重复的。

原因是我有 200 万个我发送到 API，我想知道哪些与其他重叠，因此我可以减少它们，因此每个框只覆盖一个独特的土地区域，所以没有两个边界框覆盖同一块的地理空间。

我将如何计算以使这些边界框每个都覆盖自己独特的地理土地空间？

我正在用 C++ 编写这个程序。

Answer 1

我认为这个任务比你想象的要复杂。

您必须拆分现有的盒子，直到不存在重叠，然后删除完全包含在另一个盒子中的盒子。

我建议您检查一下您是否可以接受，而不是为您提供解决方案：

1）删除完全包含在另一个盒子中的盒子。
2) 保留（部分）重叠的框。

对于 200 万，您需要一个空间索引 (QuadTree)，以获取一个框附近的所有框的列表。

如果你必须避免任何重叠，那么你必须继续思考结果应该是什么？
A）重叠矩形的联合，因此不再是矩形，而是多边形。
或 B) 结果应该是矩形。

Answer 2

您可以检查一个框的 X% 的顶点是否在另一个框内以查找它是否重叠，但我认为这不是最佳解决方案。