› 看板 C_and_CPP 關於我們 聯絡資訊
作者elfkiller (沒有暱稱)
看板C_and_CPP
標題[問題] 凸多邊形
時間Thu Feb 12 21:15:41 2009
給一組平面上的點(x1,y1),(x2,y2)...(xn,yn) 連成一個凸n邊形 H 另隨便給定一點 P(x,y) 有沒有方法可以判斷P是在 H內部, H邊上還是 H外面 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 220.134.26.171
推 netsphere:這可以用 CONVEX HULL 的演算法解決~ 02/12 21:18
→ elfkiller:怎作? 凸n邊形已經給定了 why要再作一次convex hull? 02/12 21:26
推 ckclark:對所有的p_k 和p_k+1同正或同負就是在內部 有0就是在邊上 02/12 21:39
→ ckclark: ^外積 02/12 21:40
→ ckclark:在邊上的條件要再改一點點 02/12 21:41
推 HudsonE:先想三角形怎麼做, 再想多邊形 02/12 21:52
推 ledia:也可以算面積, 所有三角形 P,p_i,p_i+1 的面積和看看是否 02/12 23:29
→ ledia:等於整個 n 邊形的面積 02/12 23:30
→ ledia:在邊上的還要看有沒有 P,p_i,p_i+1 是零 02/12 23:30