医院网站管理系统,嘉兴制作网站软件,前端开发需要哪些技术,龙岗网站建设企业转自周见智 介绍 最近项目中要用到有关几何#xff08;Geometry#xff09;方面的知识#xff0c;程序需要判断给定的一条线段#xff08;Segment#xff09;与指定多边形#xff08;Polygon#xff09;的位置关系。这种关系分为三种#xff1a;多边形包含线段、多边形…转自周见智 介绍 最近项目中要用到有关几何Geometry方面的知识程序需要判断给定的一条线段Segment与指定多边形Polygon的位置关系。这种关系分为三种多边形包含线段、多边形与线段相交以及多边形与线段无关联。 起初我以为.NET类库中已经包含此种判定功能的API比如类似System.Drawing.Region这些类型后来等到实际要用的时候才发现根本就没这种“高级”算法。 没办法只能自己去写代码实现。后来在stackoverflow链接上找到了一个解决方案不过都是源代码并没有详细的说明。本文参照原作者提供的源码进行详细的说明。如果你只需要最终答案可以不用阅读本文所有内容文章最后会给出判断源代码很简答使用就一个方法代入参数直接调用即可但如果你想搞清楚怎么回事那么可以静下心来看看本文全部内容虽然比较复杂但是相信一定会有所收获的。 解决思路 线段与多边形的关系只有三种无关联、相交以及包含。我们可以分以下两步来进行分析 判断线段与多边形的各条边是否相交若是则线段与多边形属于“相交”关系如果线段与多边形的任何边都不相交那么我们接着判断线段的任意一个端点是否在多边形内部若是则整条线段肯定在多边形内即“包含”关系若不是则整条线段肯定都在多边形外部即“无关联”关系。上面两步看似简单实质相当复杂。判断线段与多边形各条边的关系涉及到了“线段与线段关系的判断”、判断线段任意一个端点是否在多边形内部涉及到了“点与线段关系的判断”总之要解决大问题必须先解决一些小问题 点与线段的关系线段与线段的关系点与多边形的关系下面依次介绍以上三个小问题的解决方法。 问题一点与线段的关系 点与线段只有两种关系 点在线段上点与线段无关联这种判断方法很简单只要我们能确保给定点P的Y坐标在线段AB两个端点的Y坐标之间或者点P的X坐标在两个端点的X坐标之间也行并且点P与线段AB任意端点间的斜率与AB线段斜率相等即可说明点P在线段AB上。 如上图如果Y2YY1且KK1则说明点P在线段AB上否则点P与线段AB无关联。 问题二线段与线段的关系 线段与线段也只有两种关系 两线段相交两线段无关联这种判断稍微复杂一些为了更方便计算涉及到了“平移”、“旋转”等操作。给定线段AB和CD先将两线段整体平移注意是整体让线段AB的A端点与原点0,0重合接着将两线段整体旋转注意是整体让线段AB与X轴的正方向重合。 如上图将任意两线段AB和CD按照“先整体平移再整体旋转”的顺序操作一遍最终让线段AB的A端点与原点0,0重合并让线段AB与X轴正方向重合。很显然任意线段均可以进行以上操作。接下来再在此基础上进行判断就比较简单了如果线段CD的两个端点C和D的Y坐标均大于零分布在第一、二象限或者均小于零分布在第三、四象限那么AB与CD肯定不相交换句话说CD的两个端点必须一个在X轴上方另一个在X轴下方时两条线段才有可能相交。如果线段CD的端点确实是一个在X轴上方一个在X轴下方接下来再计算直线AB和直线CD注意这里说的是直线的交点这时候两条直线一定有交点并且交点在X轴上这里暂定交点为P如果P在X轴的负方向上P.X0那么说明线段AB和CD不相交如果P在X轴正方向但是P的X坐标大于线段AB的长度那么说明线段AB和CD也不相交其他情况下线段AB和CD才属于“相交”关系。 问题三点与多边形的关系 点与多边形有三种关系 点与多边形无关联点在多边形上某条边上点在多边形内部判断点是否在多边形上需要用到解决问题一的方法即判断点与线段的关系。如果点不在多边形上那么需要判断它在多边形内部还是外部这个判断方法说难也不难说不难也挺难的。事实上只需要判断点在多边形每条边的左边还是右边注意这里的左边和右边定义见下图 如上图多边形ABCDE在右侧光源的照射下它的每条边如AB、BC等都会与Y轴上各自的投影如AB、BC等之间形成一个梯形区域如ABBA、BCCB等。我们只需要统计给定点P在这些梯形区域中的次数若点P在某条边对应的梯形区域内那么计数N加1最后看N是否为偶数如果N为偶数包括0那么说明点P不在多边形内部否则点P在多边形内部。上图中P1的计数N1只在ABBA内部所以点P1在多边形ABCDE内部而点P2的计数N2同时在AEEA和BCCB内部所以点P2不在多边形ABCDE内部同理点P3的计数N0所以它也不在多边形内部。 转载于:https://www.cnblogs.com/P3nguin/p/9379654.html
