判断点是否在多边形内

这个问题的来源是如何判断机器人在某个多边形的区域内。

使用面积法,这是显而易见的,对于不规则的多边形面积计算,参考这里,需要知道每个顶点的坐标。连续取两个顶点和点O构成三角形,求出所有三角形的面积和。

如果知道了每个点的坐标,三角形面积可以用海伦公式计算,所以需要求出所有的边长,这样计算量就大了。


机器人是在运动的,如果一直判断是否在某多边形内,计算量太大,先判断机器人坐标到多边形重心的距离是否小于一定阈值,若小于再进行判断。

对于矩形重心,求四个点坐标均值即可,对于不规则多边形,重心求解比较复杂,参考求简单多边形的重心可视化实现

其他还有射线法、求内角法,前者的实现比较复杂,后者用反三角函数,也会增加计算量。