请教最佳解法－－两条在同一水平线上的线段是否相交

Question

A，B，C，D构成两条线段， A和B为一条，C和D为另一条，两条线段都是在同一水平线上。然后判断这两条线是否有相交。应该有好几种判断方法，但是有没有一种最简单最佳的解法？

Answer 1

if abs((xa-xb)/(ya-yb)) <> abs((xc-xd)/(yc-yd)) then  msgbox "两条线相交"
一句代码搞定应该是比较简单的了吧

Answer 2

转一篇文献给楼主参考吧计算几何算法概览
 一、引言　　计算机的出现使得很多原本十分繁琐的工作得以大幅度简化，但是也有一些在人们直
观看来很容易的问题却需要拿出一套并不简单的通用解决方案，比如几何问题。作为计算
机科学的一个分支，计算几何主要研究解决几何问题的算法。在现代工程和数学领域，计
算几何在图形学、机器人技术、超大规模集成电路设计和统计等诸多领域有着十分重要的
应用。在本文中，我们将对计算几何常用的基本算法做一个全面的介绍，希望对您了解并
应用计算几何的知识解决问题起到帮助。二、目录　　本文整理的计算几何基本概念和常用算法包括如下内容：　　矢量的概念　　矢量加减法　　矢量叉积　　折线段的拐向判断　　判断点是否在线段上　　判断两线段是否相交　　判断线段和直线是否相交　　判断矩形是否包含点　　判断线段、折线、多边形是否在矩形中　　判断矩形是否在矩形中　　判断圆是否在矩形中　　判断点是否在多边形中　　判断线段是否在多边形内　　判断折线是否在多边形内　　判断多边形是否在多边形内　　判断矩形是否在多边形内　　判断圆是否在多边形内　　判断点是否在圆内　　判断线段、折线、矩形、多边形是否在圆内　　判断圆是否在圆内　　计算点到线段的最近点　　计算点到折线、矩形、多边形的最近点　　计算点到圆的最近距离及交点坐标　　计算两条共线的线段的交点　　计算线段或直线与线段的交点　　求线段或直线与折线、矩形、多边形的交点　　求线段或直线与圆的交点　　凸包的概念　　凸包的求法三、算法介绍　　矢量的概念：　　如果一条线段的端点是有次序之分的，我们把这种线段成为有向线段(directed 
segment)。如果有向线段p1p2的起点p1在坐标原点，我们可以把它称为矢量(vector)p2。　　矢量加减法：　　设二维矢量P = ( x1, y1 )，Q = ( x2 , y2 )，则矢量加法定义为： P + Q = ( 
x1 + x2 , y1 + y2 )，同样的，矢量减法定义为： P - Q = ( x1 - x2 , y1 - y2 )。
显然有性质 P + Q = Q + P，P - Q = - ( Q - P )。　　矢量叉积：　　计算矢量叉积是与直线和线段相关算法的核心部分。设矢量P = ( x1, y1 )，Q = ( 
x2, y2 )，则矢量叉积定义为由(0,0)、p1、p2和p1+p2所组成的平行四边形的带符号的面
积，即：P × Q = x1*y2 - x2*y1，其结果是一个标量。显然有性质 P × Q = - ( Q 
× P ) 和 P × ( - Q ) = - ( P × Q )。一般在不加说明的情况下，本文下述算法中
所有的点都看作矢量，两点的加减法就是矢量相加减，而点的乘法则看作矢量叉积。　　叉积的一个非常重要性质是可以通过它的符号判断两矢量相互之间的顺逆时针关系：　　若 P × Q > 0 , 则P在Q的顺时针方向。
　　若 P × Q < 0 , 则P在Q的逆时针方向。
　　若 P × Q = 0 , 则P与Q共线，但可能同向也可能反向。　　折线段的拐向判断：　　折线段的拐向判断方法可以直接由矢量叉积的性质推出。对于有公共端点的线段p0p1
和p1p2，通过计算(p2 - p0) × (p1 - p0)的符号便可以确定折线段的拐向：　　若(p2 - p0) × (p1 - p0) > 0,则p0p1在p1点拐向右侧后得到p1p2。　　若(p2 - p0) × (p1 - p0) < 0,则p0p1在p1点拐向左侧后得到p1p2。　　若(p2 - p0) × (p1 - p0) = 0,则p0、p1、p2三点共线。　　具体情况可参照下图：    　　判断点是否在线段上：　　设点为Q，线段为P1P2 ，判断点Q在该线段上的依据是：( Q - P1 ) × ( P2 - 
P1 ) = 0 且 Q 在以 P1，P2为对角顶点的矩形内。前者保证Q点在直线P1P2上，后者是保
证Q点不在线段P1P2的延长线或反向延长线上，对于这一步骤的判断可以用以下过程实
现：　　ON-SEGMENT(pi,pj,pk)　　if min(xi,xj) <= xk <= max(xi,xj) and min(yi,yj) <= yk <= max(yi,yj)　　then return true;　　else return false;　　特别要注意的是，由于需要考虑水平线段和垂直线段两种特殊情况，min(xi,xj)
<=xk<=max(xi,xj)和min(yi,yj)<=yk<=max(yi,yj)两个条件必须同时满足才能返回真值。　　判断两线段是否相交：　　我们分两步确定两条线段是否相交：　　(1)快速排斥试验　　　　设以线段 P1P2 为对角线的矩形为R， 设以线段 Q1Q2 为对角线的矩形为T，如
果R和T不相交，显然两线段不会相交。　　(2)跨立试验　　　　如果两线段相交，则两线段必然相互跨立对方。若P1P2跨立Q1Q2 ，则矢量 ( 
P1 - Q1 ) 和( P2 - Q1 )位于矢量( Q2 - Q1 ) 的两侧，即( P1 - Q1 ) × ( Q2 - 
Q1 ) * ( P2 - Q1 ) × ( Q2 - Q1 ) < 0。上式可改写成( P1 - Q1 ) × ( Q2 - Q1 ) 
* ( Q2 - Q1 ) × ( P2 - Q1 ) > 0。当 ( P1 - Q1 ) × ( Q2 - Q1 ) = 0 时，说明 
( P1 - Q1 ) 和 ( Q2 - Q1 )共线，但是因为已经通过快速排斥试验，所以 P1 一定在线
段 Q1Q2上；同理，( Q2 - Q1 ) ×(P2 - Q1 ) = 0 说明 P2 一定在线段 Q1Q2上。所以
判断P1P2跨立Q1Q2的依据是：( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - 
Q1 ) >= 0。同理判断Q1Q2跨立P1P2的依据是：( Q1 - P1 ) × ( P2 - P1 ) * ( P2 - 
P1 ) × ( Q2 - P1 ) >= 0。具体情况如下图所示：    　　在相同的原理下，对此算法的具体的实现细节可能会与此有所不同，除了这种过程
外，大家也可以参考《算法导论》上的实现。　　判断线段和直线是否相交：　　有了上面的基础，这个算法就很容易了。如果线段P1P2和直线Q1Q2相交，则P1P2跨立
Q1Q2，即：( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) >= 0。　　判断矩形是否包含点：　　只要判断该点的横坐标和纵坐标是否夹在矩形的左右边和上下边之间。    
　　判断线段、折线、多边形是否在矩形中：　　因为矩形是个凸集，所以只要判断所有端点是否都在矩形中就可以了。　　判断矩形是否在矩形中：　　只要比较左右边界和上下边界就可以了。　　判断圆是否在矩形中：　　很容易证明，圆在矩形中的充要条件是：圆心在矩形中且圆的半径小于等于圆心到矩
形四边的距离的最小值。　　判断点是否在多边形中：　　判断点P是否在多边形中是计算几何中一个非常基本但是十分重要的算法。以点P为端
点，向左方作射线L，由于多边形是有界的，所以射线L的左端一定在多边形外，考虑沿着
L从无穷远处开始自左向右移动，遇到和多边形的第一个交点的时候，进入到了多边形的
内部，遇到第二个交点的时候，离开了多边形，……所以很容易看出当L和多边形的交点
数目C是奇数的时候，P在多边形内，是偶数的话P在多边形外。　　但是有些特殊情况要加以考虑。如图下图(a)(b)(c)(d)所示。在图(a)中，L和多边形
的顶点相交，这时候交点只能计算一个；在图(b)中，L和多边形顶点的交点不应被计算；
在图(c)和(d) 中，L和多边形的一条边重合，这条边应该被忽略不计。如果L和多边形的
一条边重合，这条边应该被忽略不计。    　　为了统一起见，我们在计算射线L和多边形的交点的时候，1。对于多边形的水平边不
作考虑；2。对于多边形的顶点和L相交的情况，如果该顶点是其所属的边上纵坐标较大的
顶点，则计数，否则忽略；3。对于P在多边形边上的情形，直接可判断P属于多边行。由
此得出算法的伪代码如下：    count ← 0;
    以P为端点，作从右向左的射线L; 
    for 多边形的每条边s
     do if P在边s上 
          then return true;
        if s不是水平的
          then if s的一个端点在L上
                 if 该端点是s两端点中纵坐标较大的端点
                   then count ← count+1
               else if s和L相交
                 then count ← count+1;
    if count mod 2 = 1 
      then return true;
    else return false;
　　其中做射线L的方法是：设P'的纵坐标和P相同，横坐标为正无穷大（很大的一个正
数），则P和P'就确定了射线L。 　　判断点是否在多边形中的这个算法的时间复杂度为O(n)。　　另外还有一种算法是用带符号的三角形面积之和与多边形面积进行比较，这种算法由
于使用浮点数运算所以会带来一定误差，不推荐大家使用。 　　判断线段是否在多边形内： 　　线段在多边形内的一个必要条件是线段的两个端点都在多边形内，但由于多边形可能
为凹，所以这不能成为判断的充分条件。如果线段和多边形的某条边内交（两线段内交是
指两线段相交且交点不在两线段的端点），因为多边形的边的左右两侧分属多边形内外不
同部分，所以线段一定会有一部分在多边形外(见图a)。于是我们得到线段在多边形内的
第二个必要条件：线段和多边形的所有边都不内交。 　　线段和多边形交于线段的两端点并不会影响线段是否在多边形内；但是如果多边形的
某个顶点和线段相交，还必须判断两相邻交点之间的线段是否包含于多边形内部（反例见
图b)。     　　因此我们可以先求出所有和线段相交的多边形的顶点，然后按照X-Y坐标排序(X坐标
小的排在前面，对于X坐标相同的点，Y坐标小的排在前面，这种排序准则也是为了保证水
平和垂直情况的判断正确)，这样相邻的两个点就是在线段上相邻的两交点，如果任意相
邻两点的中点也在多边形内，则该线段一定在多边形内。 
章能带你走进这个丰富多彩的世界。

Answer 3

　　证明如下：
　　　命题1：
　　　　如果线段和多边形的两相邻交点P1 ，P2的中点P' 也在多边形内，则P1, P2之间
的所有点都在多边形内。
     　　证明：
　　　　假设P1,P2之间含有不在多边形内的点，不妨设该点为Q，在P1, P'之间，因为多
边形是闭合曲线，所以其内外部之间有界，而P1属于多边行内部，Q属于多边性外部，
P'属于多边性内部，P1-Q-P'完全连续，所以P1Q和QP'一定跨越多边形的边界，因此在
P1,P'之间至少还有两个该线段和多边形的交点，这和P1P2是相邻两交点矛盾，故命题成
立。证毕。 　　由命题1直接可得出推论：
　　推论2：
　　　　设多边形和线段PQ的交点依次为P1,P2,……Pn，其中Pi和Pi+1是相邻两交点，线
段PQ在多边形内的充要条件是：P，Q在多边形内且对于i =1, 2,……, n-1，Pi ,Pi+1的
中点也在多边形内。　　在实际编程中，没有必要计算所有的交点，首先应判断线段和多边形的边是否内交，
倘若线段和多边形的某条边内交则线段一定在多边形外；如果线段和多边形的每一条边都
不内交，则线段和多边形的交点一定是线段的端点或者多边形的顶点，只要判断点是否在
线段上就可以了。　　至此我们得出算法如下：    if 线端PQ的端点不都在多边形内 
      then return false;
    点集pointSet初始化为空;
    for 多边形的每条边s
      do if 线段的某个端点在s上
           then 将该端点加入pointSet;
         else if s的某个端点在线段PQ上
           then 将该端点加入pointSet;
         else if s和线段PQ相交 // 这时候已经可以肯定是内交了
           then return false;
    将pointSet中的点按照X-Y坐标排序;
    for pointSet中每两个相邻点 pointSet[i] , pointSet[ i+1]
      do if pointSet[i] , pointSet[ i+1] 的中点不在多边形中
           then return false;
    return true;　　这个过程中的排序因为交点数目肯定远小于多边形的顶点数目n，所以最多是常数级
的复杂度，几乎可以忽略不计。因此算法的时间复杂度也是O(n)。 　　判断折线是否在多边形内： 　　只要判断折线的每条线段是否都在多边形内即可。设折线有m条线段，多边形有n个顶
点，则该算法的时间复杂度为O(m*n)。 　　判断多边形是否在多边形内： 　　只要判断多边形的每条边是否都在多边形内即可。判断一个有m个顶点的多边形是否
在一个有n个顶点的多边形内复杂度为O(m*n)。 　　判断矩形是否在多边形内： 　　将矩形转化为多边形，然后再判断是否在多边形内。 　　判断圆是否在多边形内： 　　只要计算圆心到多边形的每条边的最短距离，如果该距离大于等于圆半径则该圆在多
边形内。计算圆心到多边形每条边最短距离的算法在后文阐述。 　　判断点是否在圆内： 　　计算圆心到该点的距离，如果小于等于半径则该点在圆内。 　　判断线段、折线、矩形、多边形是否在圆内： 　　因为圆是凸集，所以只要判断是否每个顶点都在圆内即可。 　　判断圆是否在圆内： 　　设两圆为O1,O2，半径分别为r1, r2，要判断O2是否在O1内。先比较r1，r2的大小，
如果r1<r2则O2不可能在O1内；否则如果两圆心的距离大于r1 - r2 ，则O2不在O1内；否
则O2在O1内。 　　计算点到线段的最近点： 　　如果该线段平行于X轴（Y轴），则过点point作该线段所在直线的垂线，垂足很容易
求得，然后计算出垂足，如果垂足在线段上则返回垂足，否则返回离垂足近的端点；如果
该线段不平行于X轴也不平行于Y轴，则斜率存在且不为0。设线段的两端点为pt1和pt2，
斜率为：k = ( pt2.y - pt1. y ) / (pt2.x - pt1.x );该直线方程为：y = k* ( x - 
pt1.x) + pt1.y。其垂线的斜率为 - 1 / k，垂线方程为：y = (-1/k) * (x - 
point.x) + point.y 。 　　联立两直线方程解得：x = ( k^2 * pt1.x + k * (point.y - pt1.y ) + 
point.x ) / ( k^2 + 1) ，y = k * ( x - pt1.x) + pt1.y;然后再判断垂足是否在线段
上，如果在线段上则返回垂足；如果不在则计算两端点到垂足的距离，选择距离垂足较近
的端点返回。 　　计算点到折线、矩形、多边形的最近点： 　　只要分别计算点到每条线段的最近点，记录最近距离，取其中最近距离最小的点即
可。 　　计算点到圆的最近距离及交点坐标： 　　如果该点在圆心，因为圆心到圆周任一点的距离相等，返回UNDEFINED。 　　连接点P和圆心O，如果PO平行于X轴，则根据P在O的左边还是右边计算出最近点的横
坐标为centerPoint.x - radius 或 centerPoint.x + radius。如果PO平行于Y轴，则根
据P在O的上边还是下边计算出最近点的纵坐标为 centerPoint.y -+radius或 
centerPoint.y - radius。如果PO不平行于X轴和Y轴，则PO的斜率存在且不为0，这时直
线PO斜率为k = （ P.y - O.y ）/ ( P.x - O.x )。直线PO的方程为：y = k * ( x - 
P.x) + P.y。设圆方程为:(x - O.x ) ^2 + ( y - O.y ) ^2 = r ^2，联立两方程组可以
解出直线PO和圆的交点，取其中离P点较近的交点即可。 

Answer 4

Imports System.Drawing
Imports System.MathPublic Class Form1    Function IsPingXing(ByVal A As Point, ByVal B As Point, ByVal C As Point, ByVal D As Point) As Boolean        If A.X = B.X Then
            If C.X = D.X And A.X <> C.X Then
                Return True
            End If
        End If
        If A.Y = B.Y Then
            If C.Y = D.Y And A.Y <> C.Y Then
                Return True
            End If
        End If        'B--A,D--C
        If A.X > B.X And C.X > D.X Then
            If (A.Y > B.Y And C.Y > D.Y) Or (A.Y < B.Y And C.Y < D.Y) Then
                If ((A.Y - B.Y) / (A.X - B.X)) = ((C.Y - D.Y) / (C.X - D.X)) Then
                    Return True
                End If
            Else
                Return False
            End If
        End If        'A--B,C--D
        If A.X < B.X And C.X < D.X Then
            If (A.Y > B.Y And C.Y > D.Y) Or (A.Y < B.Y And C.Y < D.Y) Then
                If ((A.Y - B.Y) / (A.X - B.X)) = ((C.Y - D.Y) / (C.X - D.X)) Then
                    Return True
                End If
            Else
                Return False
            End If
        End If        'B--A,C--D
        If B.X < A.X And C.X < D.X Then
            If (B.Y > A.Y And C.Y > D.Y) Or (B.Y < A.Y And C.Y < D.Y) Then
                If ((B.Y - A.Y) / (B.X - A.X)) = ((C.Y - D.Y) / (C.X - D.X)) Then
                    Return True
                End If
            Else
                Return False
            End If
        End If        'A--B,D--C
        If A.X < B.X And D.X < C.X Then
            If (A.Y > B.Y And D.Y > C.Y) Or (A.Y < B.Y And D.Y < C.Y) Then
                If ((A.Y - B.Y) / (A.X - B.X)) = ((D.Y - C.Y) / (D.X - C.X)) Then
                    Return True
                End If
            Else
                Return False
            End If
        End If    End Function    Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click        If IsPingXing(New Point(1, 1), New Point(2, 2), New Point(2, 1), New Point(3, 2)) Then
            MsgBox("true")
        Else
            MsgBox("false")
        End If    End SubEnd Class