algorithm - 包含区域之间的内部关系算法

Question

我有两个由它们包含的点定义的区域。

也就是说，一个区域是点 {X, Y} 的列表。

每个区域都是相连的。

一个区域在另一个区域内。

我需要一种算法来识别里面的区域。

有人可以为我提供解决此问题的算法的链接吗？

如果有人知道解决这个问题的opencv函数，非常欢迎。

提前致谢。

Answer 1

只要外部形状的点都不在内部形状的点内，这可以通过点定位算法在线性时间内完成。从两组中较大的一个中选择一个点，并通过射线投射检查它是否在另一个区域内。请参阅多边形中的点问题。此处提供了多种语言的全面实现集：光线投射实现。