我遇到了另一个算法问题,我需要确定完成此问题的最佳方法。
为了简化 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,如果是这样,他们是否可以发布一些关于如何构建所述算法的资源?
编辑:
圆弧用圆弧表示
最佳答案
在所有情况下都适用的合理方法是展平曲线多边形,即通过将代表它们的平面多边形转换为某种程度的精确度。这可以通过递归 segmentation 来完成。
然后使用扫描线方法检测交叉点。
请注意,您也可以预先使用扫描线方法,并在单调的部分分解弧线。无论如何要当心,两条不在交叉配置中的单调圆弧无论如何都可能相交。
关于c++ - 带弧的多边形内的多边形,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/49367838/