首页 > 试题广场 >

要确定点p0是否在简单多边形P(不一定是凸多边形)内部,一种

[问答题]
要确定点p0是否在简单多边形P(不一定是凸多边形)内部,一种方法是检查由p0发出的全部射线,看它们是否与p的边界相交奇数次,但是p0本身不能位于边界上。试说明如何在(n)时间内计算出p0是否在一个由n个顶点组成的多边形的内部。(提示:确保当射线与多边形边界在顶点处相交,以及当射线遮盖住多边形的一条边时,  算法的正确性。)

这道题你会答吗?花几分钟告诉大家答案吧!