作者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