[問題] 判斷線段有無穿過障礙物(visibility)

[comt0928 (活在當下)]

小弟不才....參考visibility graph 做路徑規劃的東西

藍色為障礙物 其他兩個三角形為起始點終點

每個頂點兩兩互連 很多線段
http://imgur.com/fgJzjMz


要扣掉不能行走路徑 就是不能穿過障礙物

我的方法是用障礙物的邊 跟 路徑做有無交叉的判斷

可是內部對角線連線 我卻沒辦法解決
http://imgur.com/KPgIopP


後來有想到解決方法  就是多邊形 頂點 點和點的距離 大於2 就刪除路徑

可是會刪到多餘的線段 就是凹下去那端 外圍的連線並不是在障礙物內部

請各位大大 可以幫小弟忙一下嗎 謝謝

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.116.245.12
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1431850454.A.950.html
※ 編輯: comt0928 (122.116.245.12), 05/17/2015 16:20:31
→ cybelia: 在每個障礙物裡隨便多畫一條線來判斷 XD?
→ comt0928: 後來想到了 先判斷兩個點是不是在同個多邊形
→ comt0928: 如果是的話 取兩個點的中心點 來判斷在多邊形內部嗎
→ comt0928: 如果在內部就刪除 如果在外部或多邊形 邊長上 就不刪除
推 FRAXIS: 給兩個在同多邊形的點 中心點在外部就表示連線都在外部？
→ comt0928: 應該是這樣 暫時想到的方法
推 fenzhang: 加判線段的向量極角是否在頂點極角內
推 DJWS: 你的方法可以找到無交叉的邊  無論那是內或外
→ DJWS: 因此我猜你是想問"如何判斷一條線是在多邊形內還是外"
→ DJWS: http://stackoverflow.com/questions/693837/
→ DJWS: (更正一下 我講的"一條線"應該改成"兩點連線"比較精準)
→ DJWS: 方法很簡單:判斷相鄰的邊是否從左右夾住對角線
→ DJWS:                ^^^^^^^^在多邊形上的
→ DJWS: 然後我講的應該跟fenzhang講的應該是同一個解法
→ comt0928: 謝謝各位 碩班畢業了