
我最近在算一个问题,也需要判断二维平面上的四个点构成的四边形的凹凸性。研究了一下这个问题,也查到这个公式,思考了一段时间,终于明白了其意义。
首先这个问题可以简单也可以复杂。区别在于告知这四个点,但是连接方式是否告知。1)如果告知连接方式,那么这个问题很简单,可以解决的办法也很多。2)如果不告知连接方式,可以进一步思考:只知道四个点,但连接方式未知,假如这四个点其构成四边形,那么构成方式是否唯一?构成四边形的凹凸性是否确定?
先说简单的,如果连接方式已知,按照12,23,34,41的方式连接,那么这个问题的思路有很多。先提供一种通俗易懂的思路:连接方式已知的话,四边形的各个顶点就已经确定,那么可以通过余弦定理计算出两个边形成的夹角,这里的夹角范围在0到180度。如果是凸四边形,那么四个内角和必然是360度;如果是凹四边形,内角和必然会小于360度。
再说复杂的,如果连接方式未定,那么这四个点构成四边形的方式是否唯一。先说结论:如果四点能构成凸多边形,则连接方式唯一;如果不能构成凸多边形则连接方式不唯一。没有严格的证明,但是下面的图形应该可以说明以上结论。
给定任意四点(不存在三点及以上共线),可随意选取其中三点ABC做出一个三角形,这个三角形将整个平面或分为7个区域,总共两大类。第一类是上图中的阴影部分,很明显,如果第四个点D落在阴影部分,则如论如何连接,这四个点都不可能构成凸四边形;第四个点只有落在阴影部分外面,才有可能构成凸四边形,并且连接方式也固定。
如果第四个点落在了阴影部分,四点只能构成凹四边形,如上图所示,明显连接方式不唯一。
但以上分析也同时说明了一个结论:四点位置已知,则其构成四边形的凹凸性就已经确定,与连接方式无关。因为三点确定下来之后,第四个点所处位置只有两种可能:1阴影部分,则四点构成凹四边形;2 非阴影部分,则点构成凸四边形。
既然凹凸性与连接方式无关,则只要告知四个点的位置信息,那么必定能判断出这四个点构成的四边形的凹凸性,即使当这四个点构成凹四边形时的连接方式可能有多种。其实上,通过上图的分析,一个简单的方法已经呼之欲出:随意取三点ABC,可以计算出直线AB,AC,BC的一次函数,那么阴影部分和非阴影部分就可以用函数表示出来,再判断第四个点处在哪部分,就能判断出凹凸性了。这个方法直接,但是略显复杂,但可以预料的是最后化简的结果其实上和题主提供的算法是等价的。因为所谓大于小于零其实就是判断点在线的左侧还是右侧罢了。
直接来说题主提供的式子的含义是什么。要理解这个式子,首先得搞懂凹四边形和凸四边形本质的区别是什么。所谓凸多边形(不拘泥于只有四条边),就是连接任意两个相邻顶点,构成的直线都处在这个多边形的同一侧,不会分割这个多边形;相反凹多边形,则必定存在至少一条由两个相邻顶点构成的直线穿过了这个多边形的内部。既然如此,我们就可以通过这个区别来区分这两种情况。现在有任意四个点,记为1,2,3,4,连接方式未知,如果我们把1和4连接起来,同时把2和3连接起来,那么那么边14和边23与最后构成的四边形的关系只有两种:1,14和23同时是这个四边形的边(对应下图中A和C);2, 14和23同时是这个四边形的两条对角线(对应下图中B和D)。
如果我们来分析上图这四种情况,可以发现
A:2和3在直线14的同一侧;同时1和4在直线23的同一侧;
B:2和3分居直线14的两侧;同时1和4分居直线的23的两侧;
C:2和3在直线14的同一侧;而1和4分居直线23的两侧;
D:2和3在直线14的同一侧;而1和4分居直线23的两侧;
可以看出,对于AB情况的凸四边形,23与14的相对关系永远是同步的;而对于CD情况的凹四边形,23与14的相对关系总是相反的。
那么如何判断一个点是在直线的哪一侧呢,这就得说到向量积这个概念了,同时还要熟悉右手定则。大致是这样,两个向量的向量积(或者加叉乘)结果同样是一个向量,其大小是这由两个向量围成的三角形的面积,方向由右手定则来决定(张开右手掌,竖起大拇指,让第一个向量垂直穿过掌心,同时手掌弯曲尝试去握住第二个向量,最后大拇指的方向即为向量积的方向,可以看出,向量积的方向总是垂直两个于向量所组成的平面)。如果认为给定的点是在xy平面,则两个在xy平面的向量的向量积方向会在z方向,大小可正可负。假如说三个点A,B,C的坐标分别为 , 则向量AB= ,向量AC= ,则AB与AC的向量积
由于这个向量是在z方向,所以x和y方向的分量均为零,所以只需要关心z方向的大小就行了。可以看出如果最后算出z方向的分量是正的,那么由A到B到C是逆时针方向;反之就是顺时针方向。显然,回到之前的四个点,如果我要判断14和23的相对位置,那么我可以固定41作为参考向量,计算向量41与向量42的叉积,同时计算向量41以向量43的叉积,得到结果如果符号相同,则证明2和3在直线41的同一侧;符号相反分居两侧。因此题主图片中的z1和z2其实就是在判断2和3个点在直线41的同侧或者两侧。下面简单证明之:
上式判断点2在直线41的哪一侧。
这个式子判断点3在41的哪一侧,这个式子与题主图片中的式子隔了一个负号,这是为了后面方面简化情况,暂且搁置区别。
同理可以判断点1和4在直线23的哪一侧,就会得到题主图中的第三个和第四个式子,当然也有一个式子隔了一个负号。
那么题主图中判断z1*z2和z3*z4是否大于零代表什么意思呢?
我么回到之前图三的四种情况。因为z1和-z2代表的是点2和点3分布在直线14同侧或者两侧的情况。
很明显当z1z2大于零时,z1和z2同号,也就意味着z1和-z2异号,说明点2和点3分布在直线14的两侧,对应情况B,如果z3z4再大于零,说明点1和点4分布在直线23的两侧,进一步确认是情况B,说明1234四个点构成凸四边形;
z1z2小于零或者z3z4小于零时情况也可以照此分析。
我不清楚题主图中是何程序,判断正确返回+1相信对很多程序是一样的,我惯用的matlab判断错误则返回0,但似乎有些程序是返回-1。我个人觉得题主所截图的程序应该是返回-1的,并且-1&&-1=1。这样就能解释通这个式子适用于所有情况。
(z1*z2>0)&&(z3*z4>0),这个式子要为真,只有以下这两种情况:
1,z1与z2同号,z3与z4同号,意思是点2和点3分布在直线14两侧,并且点1和点4分布在直线23两侧,对应图3情况中的B;
2 z1与z2异号,z3与z4异号,意思是是点2和点3分布在直线14同侧,并且点1和点4分布在直线23同侧,对应图3情况中的A;
当这个式子为假时就已经排除了A和B情况,故不可能为凸四边形了。当然我图3中的四种情况并没有点2点3在直线14两侧,而点1点4在直线23同侧的情况,但并不影响上述讨论,因为只是点分配顺序的问题罢了。重要的是,对于一个四边形,任选两条没有公共顶点的连线,他们之间的相对关系必须永远同步才能保证其构成凸四边形。
