小弟不才....参考visibility graph 做路径规划的东西
蓝色为障碍物 其他两个三角形为起始点终点
每个顶点两两互连 很多线段
http://imgur.com/fgJzjMz
要扣掉不能行走路径 就是不能穿过障碍物
我的方法是用障碍物的边 跟 路径做有无交叉的判断
可是内部对角线连线 我却没办法解决
http://imgur.com/KPgIopP
后来有想到解决方法 就是多边形 顶点 点和点的距离 大于2 就删除路径
可是会删到多余的线段 就是凹下去那端 外围的连线并不是在障碍物内部
请各位大大 可以帮小弟忙一下吗 谢谢

在每个障碍物里随便多画一条线来判断 XD?

后来想到了 先判断两个点是不是在同个多边形如果是的话 取两个点的中心点 来判断在多边形内部吗如果在内部就删除 如果在外部或多边形 边长上 就不删除

给两个在同多边形的点 中心点在外部就表示连线都在外部？

应该是这样 暂时想到的方法

加判线段的向量极角是否在顶点极角内

你的方法可以找到无交叉的边 无论那是内或外因此我猜你是想问"如何判断一条线是在多边形内还是外"http://stackoverflow.com/questions/693837/(更正一下 我讲的"一条线"应该改成"两点连线"比较精准)方法很简单:判断相邻的边是否从左右夹住对角线^^^^^^^^在多边形上的然后我讲的应该跟fenzhang讲的应该是同一个解法

谢谢各位 硕班毕业了