# -*- coding: utf-8 -*-
# @Time         : 2019-09-18 16:55
# @Author       : Jayce Wong
# @ProjectName  : job
# @FileName     : segment_cross.py
# @Blog         : https://blog.51cto.com/jayce1111
# @Github       : https://github.com/SysuJayce

"""
Q：给定两个线段的坐标(也就是四个点的直角坐标系坐标)，判断这两个线段是否相交

### 判断线段是否相交可以利用向量的叉乘 ###
假定输入为P1、P2、Q1、Q2四个点的坐标，P1P2为一条线段，Q1Q2为另一条线段

两条线段相交只有两种情况
1. 其中一条线段的某一端点在另一条线段上；
2. 两条线段形成X形。

首先判断这四个点是否在另一条线段上，也就是说，判断P1是否在线段Q1Q2上，P2是否在线段Q1Q2上...
如果上述判断为真，那么这两条线段相交。【解决了第一种情况】

如果没有点在另一条线段上，那么进行叉乘判断。
先固定线段Q1Q2，然后以Q1为轴，计算Q1P1和Q1Q2、Q1P2和Q1Q2的叉乘是否异号；
然后固定线段P1P2，然后以P1为轴，计算P1Q1和P1P2、P1Q2和P1P2的叉乘是否异号。
当上述的叉乘都异号的时候，两条线段相交。
【解决了第二种情况】
"""

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __sub__(self, other):
        return Point(self.x - other.x, self.y - other.y)

class Segment:
    def __init__(self, point1, point2):
        self.point1 = point1
        self.point2 = point2
        self.x = point1.x - point2.x
        self.y = point1.y - point2.y

def crossProduct(v1, v2):
    return v1.x * v2.y - v2.x * v1.y

def onSegment(p, seg):
    """
    判断点在不在一条线段上，关键在于：
    1. 三点是否共线
    2. 点p是否在线段的延长线上。

    只要满足了三点共线，且点p不在延长线上，那么点p就在线段上。

    判断三点共线可以用向量的叉乘，三点共线即两个向量平行，也就是叉乘结果为零向量(对应到二维就是零)
    当点p的横纵坐标都在线段端点之间的时候，点p不在延长线上。
    :param p:
    :param seg:
    :return:
    """
    # 先确保点p不在延长线上
    if min(seg.point1.x, seg.point2.x) <= p.x <= max(seg.point1.x, seg.point2.x)\
            and min(seg.point1.y, seg.point2.y) <= p.y <= max(seg.point1.y, seg.point2.y):
        # 然后确保这三个点形成的向量两两平行，这里只要这三个向量中任意两个平行，第三个一定也平行
        if crossProduct(p - seg.point1, p - seg.point2) == 0:
            return True
        else:
            return False
    else:
        return False

def isCross(p1, p2, q1, q2):
    p1p2 = Segment(p1, p2)
    q1q2 = Segment(q1, q2)

    p1q1 = Segment(p1, q1)
    p1q2 = Segment(p1, q2)

    q1p1 = Segment(q1, p1)
    q1p2 = Segment(q1, p2)

    # 判断是否存在端点位于另一条线段上，是的话则两条线段相交
    if any([onSegment(p1, q1q2), onSegment(p2, q1q2),
            onSegment(q1, p1p2), onSegment(q2, p1p2)]):
        return True

    # 否则固定线段P1P2，判断Q1和Q2是否在P1P2的两侧(计算叉乘)
    # 然后固定线段Q1Q2，判断P1和P2是否在Q1Q2的两侧
    # 如果上面的判断均为真，那么这两条线段形成一个X
    return (crossProduct(p1p2, p1q1) * crossProduct(p1p2, p1q2) < 0)\
           and (crossProduct(q1q2, q1p1) * crossProduct(q1q2, q1p2) < 0)

def main():
    p1 = Point(0, 0)
    p2 = Point(2, 2)
    q1 = Point(1, 1)
    q2 = Point(0, 2)
    if isCross(p1, p2, q1, q2):
        print('Yes')
    else:
        print('No')

if __name__ == '__main__':
    main()

另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。

为企业提供成都网站建设、成都网站设计、网站优化、成都全网营销推广、竞价托管、品牌运营等营销获客服务。创新互联拥有网络营销运营团队，以丰富的互联网营销经验助力企业精准获客，真正落地解决中小企业营销获客难题，做到“让获客更简单”。自创立至今，成功用技术实力解决了企业“网站建设、网络品牌塑造、网络营销”三大难题，同时降低了营销成本，提高了有效客户转化率，获得了众多企业客户的高度认可！
文章题目：判断线段是否相交-创新互联
文章位置：http://csdahua.cn/article/djipdh.html