浅谈多边形与多边形关系的判断

浅谈多边形与多边形关系的判断区域与多边形我们这里所说的区域是指由边界形成的一个封闭的区域（闭域），区域内的点是连贯的，即内部任意两点都可以通过一条折线连接在一起。我们所说的多边形由线段依次首尾相连，组成一个封闭的区域，且线段之间除首尾相连外与其他线段没有任何连接。沿着组成多边形的线段一个方向行走，多边形所组成的封闭区域内部的点都在线段的一侧。线段两侧分别是区域内点和区域外点。几何分析（一）区域与区域我们比对区域，区域主要有相同、相离、相切（内切、外切）、相交、包含几种关系。表一区域与区域的关系序号类型特点备注1相同组成两个区域的点是同序或反序相连的2相离区域之间没有交点，且任何一个区域的任何一个顶点都不在另外区域的边上和内部点都在对方区域外部，且边不相交。3外切两个区域的边有共同点，但是任何一个区域的顶点都不在另一个区域内部（顶点在线端上我们认为也是相切）。两个区域的边有共同点，且任何一个区域的点都不在另外一个区域内部，同时没有边相交。4相交两个区域有共有部分，且有非共有部分。两个区域的线段之间有交点；或者一个区域的顶点在另一个区域内外都有5内切两个区域的边有共同点，但是其中一个区域的顶点在另一个区域内部（顶点在线端上我们认为也是相切）。6包含一个区域的所有顶点都在另外一个区域内部，且边没有相交。为了便于分析，我们设定区域都是按照顺时针方向排列顶点，即所有区域的内部都在当前边的右侧。我们首先判断区域相交的情况，区域相交必定是两个区域存在同时包含和互补包含的部分，又因为区域内部点是有边界（即线段）来分割的，在区域的相交必定是边界的相交，即是在一个区域的边界的左右两边同时出现另一个区域的边界。通过分析，我们可以发现只有以下几种情况，表二区域相交情况序号类型特点例图1普通相交组成两个区域的线段相交2顶点与边相交组成一个区域的其中一个线段的端点在组成另一个区域的线段上。以两条向量为邻边的平行四边形的面积。由于向量是有方向的，所以叉积也有方向，即正负。叉积的方向与两个相乘向量的的方向符合右手定则，即当=时，当右手的四指从以不超过180度转角转向时，竖起的大拇指指向是的方向。分别从线段A从a和b向线段B的端点c和d引出两条有向线段、和、，求()*()（叉乘后的积）的结果，当结果为负数时，线段A的两个端点a和b在线段B的两侧时；当结果为0时，a和b至少有1个点在B所在的直线上；当结果为正数时，则线段A的两个端点a和b在线段B的同一侧。同理，我们可以判断线段B的两个端点是否在线段A的两侧，如果线段A的两个端点a和b在线段B的两侧时，同时线段B的两个端点也在线段A的两侧，则线段A和B相交，如图1所示。图1两条线段相交2.当两个区域有共同点o时，如果两个区域的两条边分别依次交错分布，则两个区域相交，如图2。图2共同点的边图2中为正值的区域里只有和其中1条时，边相交，否则边不相交，也可认为是相切。当为正值的区域里只有和其中1条时，即叉乘的向量为正值，同时叉乘该向量为负值，角度内∠aob内只有一条向量（或线段）时，则边相交。2.当两个区域的边界有共同边时，我们可以认为共同边是一个点，参照当两个区域有共同点o时判断，如图3。图3共同边我们向量移动就是向量相加存在向量、，我们需要计算向量和转换成与m的关系，我们把沿着共同边位移到点b',则=-=（--）-=--=-（-）-=-，同理，=-，这样，我们可以将共同边转换成共同点来判断了（将、、、转换成、、、）。（三）点与区域点与区域的关系可以分成区域内、区域外和区域（边）上表四点与区域的关系序号类型特点备注1点在区域外点向上引出射线与区域边的交点的个数是奇数2点在区域内点向上引出射线与区域边的交点的个数是偶数3点在区域上点在区域的边上从点向上引一条射线，当点在区域内时，则射线和区域所有边的交点的个数为奇数；当点区域外时，则射线和区域所有边的交点的个数为偶数。当点在区域的边上时，称点在区域上。当点经过一条边的两个端点时，也分别计入1次交点。图4点在区域内图5点在区域外通过点向上引出的射线有两种特殊情况，一种是射线过区域的一个顶点，另一种情况是射线过区域的一条垂直横轴的边。图6射线过区域顶点图7射线过区域的边当射线经过区域的顶点时，如果经过顶点的两条边在射线两侧，则计3次交点(顶点为始点线段1次，顶点为终点线段1次，再增加1次)，如果经过顶点的两条边在射线同一侧，则计2次交点(顶点为始点线段1次，顶点为终点线段1次)；当射线经过区域的一条边，如果与该条边相接前后两条边在射线两侧，则计3次交点(垂线段前线段1次，垂线段后线段1次，垂线段1次)，如果与该条边相接前后两条边在射线同一侧，则计4次交点（垂线段前线段1次，垂线段后线段1次，垂线段1次，再增加1次）。通过以上合计交点数也符合点在区域内部时交点个数为奇数个，点在区域外部时交点个数为偶数个。（三）点与线段点与线段的关系序号类型特点备注1点在线段下方点向上引出射线与线段有交点2点不在线段下方点向上引出射线与线段没有交点3点在线段上点在线段之间当线段所在直线不是垂直线（与点所在射线平行）时，线段右面点与点的向量和线段左面点与点的向量叉积，为正数时，点在线段下部；为零时，点在线段上；为负数时，点在线段上部。当线段所在直线是垂直线时，点在下方点下部则点在线