c#竖直射线法判断点是否再多边形里面

一、开发环境：

          VS2017   C#winform

二、竖直射线法大致介绍

          通过被判断的点P(x0,y0)引出竖直的上下两条射线，如果两条射线与多变形的交点都为奇数个，那么这个点再多边形里面，反之，这个点在多边形外面，反之，则在多边形里面（前提：针对凸多边形，但是如果在端点处细讨论，那么同样可以适用于凹多边形，这里只介绍凸多边形）

三、如何判断竖直向下的射线是否与某一条边会有交点。

       1、先介绍一些点和直线的关系     

        1）对于p(x0,y0)判断它在直线L：ax+by+c=0(a必须大于0）的上侧还是下侧，我们知道如果

        ax0+by0+c>0（a>0),点p在直线L的下侧；

        ax0+by0+c=0  (a>0),点p在直线L上

        ax0+by0+c<0  (a>0),点p在直线L上侧。

     如下图：

       2）对于P(x0,y0),一条过P1(x1,y1),P2(x2,y2)的直线：（y2-y1)(x-x1)+(x2-x1)(y1-y)=0   (y2>y1)

      那么只用判断: f=(y2-y1)*(x0-x1)+(x2-x1)*(y1-y0)

     if :  f>0 则说明点在直线的下侧，

           f=0 则说明点在直线上

           f<0 则说明点在直线上侧

     2、开始介绍算法（这里是竖直向下的射线）

     先介绍符号：P(x0,y0)是需要判断的点，多变形的顶点序列Points[n],其中Points[n]=Points[0],交点个数countDown=0

    1）对于每一条边(Points[i],Points[i+1])进行遍历：p1(x1,y1)为边上的两个点Y坐标大的那个点，p2(x2,y2)为边上两个点Y坐标小的那个点。xMin为两个点较小的x坐标，xMax为两个点较大的x坐标

   2）如果x0不在范围（xMin,xMax)中，说明射线一定没有交点，i=i+1,跳到下一条边进行判断。否则跳到第3)步

   3）f=(y2-y1)*(x0-x1)+(x2-x1)*(y1-y0)  

           if (f>0&&x0!=Points[i].X)    countDown+=1，i+=1,跳到第1)步（x0!=Points[i].X是为了每一个顶点只被访问一次）

          if(f==0&&x0!=Points[i].X)     说明点在边上，退出

          if(f<0)  i+=1；  跳到第1）步

4）所有边都被遍历完，countDown为偶数，说明点在多边形外，为奇数，计算向上的射线的交点。这里就不介绍向上的射线的交点求法了。

 

等几天贴代码

     

       

 

 

 

 

 

 

总结

以上是生活随笔为你收集整理的c#竖直射线法判断点是否再多边形里面的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。