c++ - 带弧的多边形内的多边形

Question

我遇到了另一个算法问题，我需要确定完成此问题的最佳方法。

为了简化 View ，我有 2 个多边形(多边形 A 和 B)，它们可以是凸面或非凸面(凹面？)并且它们是“简单的”。多边形将由直线或圆弧组成，但多边形不会自行循环。我需要确定 A 是否完全包含 B。

我目前确定多边形 A 是否包含多边形 B 的方法是查看 B 的边界框是否在 A 内部。但是，我遇到了一些问题并得到了误报。为了保存解释，我的问题与这个人遇到的问题相同:https://math.stackexchange.com/questions/2273108/polygon-in-polygon-testing

在其中一个答案中，您会看到一张图片，说明什么会导致误报。答案还包含指向可能解决方案的链接: Check if polygon is inside a polygon

我不太赞成线相交法，因为当我们处理圆弧时，事情会变得有点复杂。虽然，如果有人可以发布一个使与弧线相交变得简单的好答案，我仍然愿意继续进行线相交。

所以，我想问社区是否有另一种更简单的方法来确定多边形 A 是否完全包围多边形 B，如果是这样，他们是否可以发布一些关于如何构建所述算法的资源？

编辑:

圆弧用圆弧表示

Answer 1

在所有情况下都适用的合理方法是展平曲线多边形，即通过将代表它们的平面多边形转换为某种程度的精确度。这可以通过递归 segmentation 来完成。

然后使用扫描线方法检测交叉点。

---

请注意，您也可以预先使用扫描线方法，并在单调的部分分解弧线。无论如何要当心，两条不在交叉配置中的单调圆弧无论如何都可能相交。