作者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
1F：推 netsphere:這可以用 CONVEX HULL 的演算法解決~ 02/12 21:18
2F：→ elfkiller:怎作? 凸n邊形已經給定了 why要再作一次convex hull? 02/12 21:26
3F：推 ckclark:對所有的p_k 和p_k+1同正或同負就是在內部 有0就是在邊上 02/12 21:39
4F：→ ckclark: ^外積 02/12 21:40
5F：→ ckclark:在邊上的條件要再改一點點 02/12 21:41
6F：推 HudsonE:先想三角形怎麼做, 再想多邊形 02/12 21:52
7F：推 ledia:也可以算面積, 所有三角形 P,p_i,p_i+1 的面積和看看是否 02/12 23:29
8F：→ ledia:等於整個 n 邊形的面積 02/12 23:30
9F：→ ledia:在邊上的還要看有沒有 P,p_i,p_i+1 是零 02/12 23:30