use*_*014 3 algorithm geospatial
我听说很多人说以编程方式在非凸多边形中找到一个点比在凸多边形中找到一个点更难.我在缠绕这个问题时遇到了麻烦.这是真的？如果是这样,为什么？
因此,您要检查点P是在多边形内部还是外部.
如果多边形是凸的,那么您可以迭代组成多边形的每个线段,并检查该线P的哪一侧.P位于多边形的内侧,如果它位于每个线段的右侧,则顺时针方向.
如果多边形是凹的,则此算法不起作用.适用于凹多边形的算法是从P沿任意方向跟踪到无穷大,并计算多边形边缘交叉的次数.当且仅当交叉数为奇数时,P在多边形内.该算法有一堆边缘情况需要考虑,并且通常更复杂,因此编写算法需要更多的程序员工作.
从某种意义上说算法更难以正确编写,是的,它更难.
在计算复杂性的意义上,两种算法都具有Θ(N)渐近运行时间.从这个意义上说,这两个问题同样困难.