91超碰碰碰碰久久久久久综合_超碰av人澡人澡人澡人澡人掠_国产黄大片在线观看画质优化_txt小说免费全本

溫馨提示×

溫馨提示×

您好,登錄后才能下訂單哦!

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務條款》

判斷線段是否相交

發布時間:2020-07-18 11:12:03 來源:網絡 閱讀:718 作者:Jayce_SYSU 欄目:編程語言
# -*- 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()
向AI問一下細節

免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:is@yisu.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。

AI

瓮安县| 凤庆县| 思茅市| 碌曲县| 乡宁县| 甘谷县| 常宁市| 德格县| 高平市| 贵南县| 景德镇市| 长沙市| 民权县| 富蕴县| 建宁县| 黄龙县| 古交市| 遂平县| 瓮安县| 小金县| 山东| 台南市| 巩留县| 新巴尔虎右旗| 江口县| 苗栗县| 富宁县| 湾仔区| 扎囊县| 聂荣县| 东安县| 漳平市| 安平县| 灵山县| 大新县| 怀宁县| 六枝特区| 卓尼县| 达孜县| 咸宁市| 白水县|