Почему моя функция утверждает, что эти линии пересекаются?

Question

У меня есть функция python, которая берет четыре точки и проверяет, пересекаются ли две линии, сделанные из этих точек, и если они это сделают, то вернется точка, где они пересекаются. Функция работает по большей части, за исключением того, что она, по-видимому, обрабатывает все строки как бесконечные, даже если они не являются.

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

def intersect(a, b, c, d):
    den = ((b.x - a.x) * (d.y - c.y)) - ((b.y - a.y) * (d.x - c.x))

    num1 = ((a.y - c.y) * (d.x - c.x)) - ((a.x - c.x) * (d.y - c.y))
    num2 = ((a.y - c.y) * (b.x - a.x)) - ((a.x - c.x) * (b.y - a.y))
    if not den:
        return

    r = num1 / den
    s = num2 / den

    if 0 < r < 1 and s > 0:
        pt = [0, 0]
        pt[0] = a.x + r * (b.x - a.x)
        pt[1] = a.y + r * (b.y - a.y)
        return pt
    else:
        return

Входные данные, которые я даю, это:

intersect(
    Vector(302,252),
    Vector(306,252),
    Vector(305,455),
    Vector(305,400)
)

Что дает точку пересечения 305, 252. Если бы эти линии были бесконечными, они бы здесь пересекались, но это не так.

Answer 1

Я до сих пор не уверен, почему, но моя функция принимает линии go бесконечно от / / 1007 * в направлении b / d. Поскольку это действительно нужно для другой части моей программы, я сделал одну, которая действительно работает, и назвал ее segintersect(). Он использует модуль shapely, поэтому вам придется установить его, но после всех различных функций, которые я пробовал, эта работала с наименьшей головной болью.

from shapely.geometry import LineString, Point

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

def segintersect(a1, a2, b1, b2):
    line1 = LineString([(a1.x, a1.y), (a2.x, a2.y)])
    line2 = LineString([(b1.x, b1.y), (b2.x, b2.y)])

    int_pt = line1.intersection(line2)
    return [int_pt.x, int_pt.y] if (type(int_pt) == Point) else []

Эта функция правильно возвращает пересечения отрезков линии .

Answer 2

Если вы в порядке с использованием shapely, я думаю, что ваш ответ - лучший ответ.

Если вам интересен способ найти его без использования внешних библиотек, то вы можете найти точка пересечения двух линий (примечание: не сегменты, линии), а затем проверьте, лежит ли эта точка на обоих сегментах.

Чтобы проверить, лежит ли она на сегментах, вы можете проверить расстояние от двух точки, определяющие сегмент, и сравните это с длиной сегмента. Если сумма двух расстояний совпадает с длиной отрезка, то точка лежит на нем.

Это пример кода:

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

def calc_distance(a, b):
    return math.sqrt((b.x - a.x)*(b.x - a.x) + (b.y - a.y)*(b.y - a.y))

def intersect(a, b, c, d):
    x1diff = b.x - a.x
    x2diff = d.x - c.x

    y1diff = b.y - a.y
    y2diff = d.y - c.y

    m1 = 0
    m2 = 0
    if (x1diff != 0):
        m1 = (b.y - a.y) / (b.x - a.x)

    if (x2diff != 0):
        m2 = (d.y - c.y) / (d.x - c.x)

    # If the slope is the same, the segments are parallel
    if (m1 == m2):
        return None

    q1 = a.y - (m1 * a.x)
    q2 = c.y - (m2 * c.x)

    x = (q2 - q1) / (m1 - m2)
    y = (m1 * x) + q1

    dist_from_a = calc_distance(Vector(x, y), a)
    dist_from_b = calc_distance(Vector(x, y), b)
    segment_length = calc_distance(a, b)

    if (dist_from_a + dist_from_b) != segment_length:
        return None

    dist_from_c = calc_distance(Vector(x, y), c)
    dist_from_d = calc_distance(Vector(x, y), d)
    segment_length = calc_distance(c, d)

    if (dist_from_c + dist_from_d) == segment_length:
        return Vector(x, y)

    return None

v = intersect(
    Vector(302,252),
    Vector(306,252),
    Vector(305,455),
    Vector(305,400)
)

print(v.x, v.y) # This will print None

v = intersect(
    Vector(0, 0),
    Vector(2, 2),
    Vector(2, 0),
    Vector(0, 2),
)

print(v.x, v.y) # This will print 1.0 1.0

Answer 3

Есть много математики, чтобы найти, пересекаются ли две линии. проверьте ссылку на математику за ней. Реализация того же python ниже

import numpy as np

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

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

def find_intersection(l1, l2):
    def slope(l):
        return (l.p2.y - l.p1.y)/(l.p2.x - l.p1.x)

    def intercept(l, m):
        return l.p1.y - m*l.p1.x


    m1 = slope(l1)
    m2 = slope(l2)
    b1 = intercept(l1, m1)
    b2 = intercept(l2, m2)

    A = np.array([
        [-m1, 1],
        [-m2, 1]
    ])

    b = np.array([[b1],[b2]])
    return np.dot(np.linalg.inv(A), b)        

# check whether p is on the line or not
def onLine(l1: Line, p: Point):   
    return True if p.x <= max(l1.p1.x, l1.p2.x) and p.x <= min(l1.p1.x, l1.p2.x) and p.y <= max(l1.p1.y, l1.p2.y) and p.y <= min(l1.p1.y, l1.p2.y) else False           


def direction(a, b, c):
    val = (b.y-a.y)*(c.x-b.x)-(b.x-a.x)*(c.y-b.y);
    if val == 0:
        return 0     # colinear
    elif val < 0:
        return 2     # anti-clockwise direction
    return 1       # clockwise direction

def isIntersect(l1: Line, l2: Line):
    #four direction for two lines and points of other line
    dir1 = direction(l1.p1, l1.p2, l2.p1);
    dir2 = direction(l1.p1, l1.p2, l2.p2);
    dir3 = direction(l2.p1, l2.p2, l1.p1);
    dir4 = direction(l2.p1, l2.p2, l1.p2);

    if dir1 != dir2 and dir3 != dir4 :
        return True, find_intersection(l1, l2)

    if dir1==0 and onLine(l1, l2.p1): # when p2 of line2 are on the line1
        return True, l1.p1

    if dir2==0 and onLine(l1, l2.p2): # when p1 of line2 are on the line1
        return True, l2.p2

    if dir3==0 and onLine(l2, l1.p1): #when p2 of line1 are on the line2
        return True, l1.p1

    if dir4==0 and onLine(l2, l1.p2): #when p1 of line1 are on the line2
        return True, l1.p2

    return False, None

Тестовые случаи:

isIntersect(Line(Point(15, 10), Point(49,25)),
                           Line(Point(32, 32), Point(29,5)))

isIntersect(Line(Point(0, 0), Point(5, 5)),
                           Line(Point(5, 6), Point(3, 10)))

• Если точки являются линейными, то вернуть одну из них (бесконечные решения)
• Если точки не коллинеарны и не пересекаются, то существует одно уникальное решение. Преобразовать две линии в стандартные линейные уравнения найти пересечение, решая уравнения с использованием матрицы обратной. ie. найти inverse(A).b