小弟不才....參考visibility graph 做路徑規劃的東西
藍色為障礙物 其他兩個三角形為起始點終點
每個頂點兩兩互連 很多線段
http://imgur.com/fgJzjMz
要扣掉不能行走路徑 就是不能穿過障礙物
我的方法是用障礙物的邊 跟 路徑做有無交叉的判斷
可是內部對角線連線 我卻沒辦法解決
http://imgur.com/KPgIopP
後來有想到解決方法 就是多邊形 頂點 點和點的距離 大於2 就刪除路徑
可是會刪到多餘的線段 就是凹下去那端 外圍的連線並不是在障礙物內部
請各位大大 可以幫小弟忙一下嗎 謝謝

在每個障礙物裡隨便多畫一條線來判斷 XD?

後來想到了 先判斷兩個點是不是在同個多邊形如果是的話 取兩個點的中心點 來判斷在多邊形內部嗎如果在內部就刪除 如果在外部或多邊形 邊長上 就不刪除

給兩個在同多邊形的點 中心點在外部就表示連線都在外部？

應該是這樣 暫時想到的方法

加判線段的向量極角是否在頂點極角內

你的方法可以找到無交叉的邊 無論那是內或外因此我猜你是想問"如何判斷一條線是在多邊形內還是外"http://stackoverflow.com/questions/693837/(更正一下 我講的"一條線"應該改成"兩點連線"比較精準)方法很簡單:判斷相鄰的邊是否從左右夾住對角線^^^^^^^^在多邊形上的然後我講的應該跟fenzhang講的應該是同一個解法

謝謝各位 碩班畢業了