file_converter.py 文件源码

python
阅读 28 收藏 0 点赞 0 评论 0

项目:timezonefinderL 作者: MrMinimal64 项目源码 文件源码
def line_segments_intersect(p1, p2, q1, q2, magn_delta_p):
    # solve equation line1 = line2
    # p1 + lambda * (p2-p1) = q1 + my * (q2-q1)
    # lambda * (p2-p1) - my * (q2-q1) = q1 - p1
    # normalize deltas to 1
    # lambda * (p2-p1)/|p1-p2| - my * (q2-q1)/|q1-q2| = q1 - p1
    # magn_delta_p = |p1-p2|  (magnitude)
    # magn_delta_q = euclidean_distance(q1[0], q1[1], q2[0], q2[1])
    if max(p1[0], p2[0]) < min(q1[0], q2[0]) or max(q1[0], q2[0]) < min(p1[0], p2[0]) or \
            max(p1[1], p2[1]) < min(q1[1], q2[1]) or max(q1[1], q2[1]) < min(p1[1], p2[1]):
        return False

    dif_p_x = p2[0] - p1[0]
    dif_p_y = p2[1] - p1[1]
    dif_q_x = q2[0] - q1[0]
    dif_q_y = q2[1] - q1[1]
    a = array([[dif_p_x, -dif_q_x], [dif_p_y, -dif_q_y]])
    # [[dif_p_x / magn_delta_p, -dif_q_x / magn_delta_q], [dif_p_y / magn_delta_p, -dif_q_y / magn_delta_q]])
    b = array([q1[0] - p1[0], q1[1] - p1[1]])
    try:
        x = linalg.solve(a, b)
    except linalg.linalg.LinAlgError:
        # Singular matrix (lines parallel, there is not intersection)
        return False

    if x[0] < 0 or x[0] > 1 or x[1] < 0 or x[1] > 1:
        # intersection of the two lines appears before or after actual line segments
        # in this use case it is important to include the points themselves when checking for intersections
        # that way a new edge that barely touches the old polygon is also legal
        return False

    return True
评论列表
文章目录


问题


面经


文章

微信
公众号

扫码关注公众号