作者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/m.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