作者comt0928 (活在当下)
看板Prob_Solve
标题[问题] 判断线段有无穿过障碍物(visibility)
时间Sun May 17 16:14:12 2015
小弟不才....参考visibility graph 做路径规划的东西
蓝色为障碍物 其他两个三角形为起始点终点
每个顶点两两互连 很多线段
http://imgur.com/fgJzjMz
要扣掉不能行走路径 就是不能穿过障碍物
我的方法是用障碍物的边 跟 路径做有无交叉的判断
可是内部对角线连线 我却没办法解决
http://imgur.com/KPgIopP
後来有想到解决方法 就是多边形 顶点 点和点的距离 大於2 就删除路径
可是会删到多余的线段 就是凹下去那端 外围的连线并不是在障碍物内部
请各位大大 可以帮小弟忙一下吗 谢谢
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 122.116.245.12
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1431850454.A.950.html
※ 编辑: comt0928 (122.116.245.12), 05/17/2015 16:20:31
1F：→ cybelia: 在每个障碍物里随便多画一条线来判断 XD? 05/17 19:19
2F：→ comt0928: 後来想到了 先判断两个点是不是在同个多边形 05/17 19:59
3F：→ comt0928: 如果是的话 取两个点的中心点 来判断在多边形内部吗 05/17 19:59
4F：→ comt0928: 如果在内部就删除 如果在外部或多边形 边长上 就不删除 05/17 20:00
5F：推 FRAXIS: 给两个在同多边形的点 中心点在外部就表示连线都在外部？ 05/17 21:42
6F：→ comt0928: 应该是这样 暂时想到的方法 05/17 22:07
7F：推 fenzhang: 加判线段的向量极角是否在顶点极角内 05/18 02:40
8F：推 DJWS: 你的方法可以找到无交叉的边 无论那是内或外 05/18 05:44
9F：→ DJWS: 因此我猜你是想问"如何判断一条线是在多边形内还是外" 05/18 05:46
11F：→ DJWS: (更正一下 我讲的"一条线"应该改成"两点连线"比较精准) 05/18 05:47
12F：→ DJWS: 方法很简单:判断相邻的边是否从左右夹住对角线 05/18 05:49
13F：→ DJWS: ^^^^^^^^在多边形上的 05/18 05:52
14F：→ DJWS: 然後我讲的应该跟fenzhang讲的应该是同一个解法 05/18 06:00
15F：→ comt0928: 谢谢各位 硕班毕业了 08/24 23:52