Как найти пересечение отрезков в python

If your lines are multiple points instead, you can use this version.

import numpy as np
import matplotlib.pyplot as plt
"""
Sukhbinder
5 April 2017
Based on:    
"""

def _rect_inter_inner(x1,x2):
    n1=x1.shape[0]-1
    n2=x2.shape[0]-1
    X1=np.c_[x1[:-1],x1[1:]]
    X2=np.c_[x2[:-1],x2[1:]]    
    S1=np.tile(X1.min(axis=1),(n2,1)).T
    S2=np.tile(X2.max(axis=1),(n1,1))
    S3=np.tile(X1.max(axis=1),(n2,1)).T
    S4=np.tile(X2.min(axis=1),(n1,1))
    return S1,S2,S3,S4

def _rectangle_intersection_(x1,y1,x2,y2):
    S1,S2,S3,S4=_rect_inter_inner(x1,x2)
    S5,S6,S7,S8=_rect_inter_inner(y1,y2)

    C1=np.less_equal(S1,S2)
    C2=np.greater_equal(S3,S4)
    C3=np.less_equal(S5,S6)
    C4=np.greater_equal(S7,S8)

    ii,jj=np.nonzero(C1 & C2 & C3 & C4)
    return ii,jj

def intersection(x1,y1,x2,y2):
    """
INTERSECTIONS Intersections of curves.
   Computes the (x,y) locations where two curves intersect.  The curves
   can be broken with NaNs or have vertical segments.
usage:
x,y=intersection(x1,y1,x2,y2)
    Example:
    a, b = 1, 2
    phi = np.linspace(3, 10, 100)
    x1 = a*phi - b*np.sin(phi)
    y1 = a - b*np.cos(phi)
    x2=phi    
    y2=np.sin(phi)+2
    x,y=intersection(x1,y1,x2,y2)
    plt.plot(x1,y1,c='r')
    plt.plot(x2,y2,c='g')
    plt.plot(x,y,'*k')
    plt.show()
    """
    ii,jj=_rectangle_intersection_(x1,y1,x2,y2)
    n=len(ii)

    dxy1=np.diff(np.c_[x1,y1],axis=0)
    dxy2=np.diff(np.c_[x2,y2],axis=0)

    T=np.zeros((4,n))
    AA=np.zeros((4,4,n))
    AA[0:2,2,:]=-1
    AA[2:4,3,:]=-1
    AA[0::2,0,:]=dxy1[ii,:].T
    AA[1::2,1,:]=dxy2[jj,:].T

    BB=np.zeros((4,n))
    BB[0,:]=-x1[ii].ravel()
    BB[1,:]=-x2[jj].ravel()
    BB[2,:]=-y1[ii].ravel()
    BB[3,:]=-y2[jj].ravel()

    for i in range(n):
        try:
            T[:,i]=np.linalg.solve(AA[:,:,i],BB[:,i])
        except:
            T[:,i]=np.NaN


    in_range= (T[0,:] >=0) & (T[1,:] >=0) & (T[0,:] <=1) & (T[1,:] <=1)

    xy0=T[2:,in_range]
    xy0=xy0.T
    return xy0[:,0],xy0[:,1]


if __name__ == '__main__':

    # a piece of a prolate cycloid, and am going to find
    a, b = 1, 2
    phi = np.linspace(3, 10, 100)
    x1 = a*phi - b*np.sin(phi)
    y1 = a - b*np.cos(phi)

    x2=phi
    y2=np.sin(phi)+2
    x,y=intersection(x1,y1,x2,y2)
    plt.plot(x1,y1,c='r')
    plt.plot(x2,y2,c='g')
    plt.plot(x,y,'*k')
    plt.show()

Я понял, что вопрос в другом, но во избежание споров о том, что можно решить проще, накидал простой пример на C#

void PrintIntersection(int a1, int b1, int a2, int b2)
{
    // координаты должны быть упорядочены
    if (a1 > b1) (a1, b1) = (b1, a1);
    if (a2 > b2) (a2, b2) = (b2, a2);
    
    // первым будет отрезок с наименьшей первой координатой
    if (a1 > a2) (a1, b1, a2, b2) = (a2, b2, a1, b1);
    
    if (b1 < a2) {
        Console.WriteLine("Пустое множество");
        return;
    }
    
    if (b1 == a2)
    {
        Console.WriteLine(b1);
        return;
    }

    Console.WriteLine($"{a2} {b1}");
}

Проверка

PrintIntersection(1, 3, 2, 4);
PrintIntersection(1, 2, 3, 4);
PrintIntersection(5, 6, 6, 8);
PrintIntersection(6, 8, 5, 6);
PrintIntersection(1, 2, 1, 2);  

Вывод

2 3
Пустое множество
6
6
1 2

Нельзя стоять в стороне,

Итак, мы имеем линейную систему:

A ₁ * x + B ₁ * y = C ₁
A ₂ * x + B ₂ * y = C ₂

допустим это с правилом Крамера, поэтому решение можно найти в детерминантах:

x = D _x/D
y = D _y/D

где D — главный определитель системы:

A ₁ B ₁
 A ₂ B ₂

и D _x и D _y могут быть найдены из матриц:

C ₁ B ₁
C ₂ B ₂

и

A ₁ C ₁
A ₂ C ₂

(обратите внимание, так как столбец C заменяет столбцы кодов x и y)

Итак, теперь, для ясности для python, чтобы не испортить вещи, пусть делает сопоставление между математикой и python. Мы будем использовать массив L для хранения наших коэффициентов A, B, C линейных уравнений и intestead pretty x, y у нас будет [0], [1], но в любом случае. Таким образом, то, что я написал выше, будет иметь следующий код в коде:

при D

L1 [0] L1 [1]
L2 [0] L2 [1]

для D _x

L1 [2] L1 [1]
L2 [2] L2 [1]

для D _y

L1 [0] L1 [2]
L2 [0] L2 [2]

Теперь перейдите для кодирования:

line — вырабатывает коэффициенты A, B, C линейного уравнения с помощью двух точек,
intersection — находит точку пересечения (если она есть) двух строк, предоставленных коэффами.

from __future__ import division 

def line(p1, p2):
    A = (p1[1] - p2[1])
    B = (p2[0] - p1[0])
    C = (p1[0]*p2[1] - p2[0]*p1[1])
    return A, B, -C

def intersection(L1, L2):
    D  = L1[0] * L2[1] - L1[1] * L2[0]
    Dx = L1[2] * L2[1] - L1[1] * L2[2]
    Dy = L1[0] * L2[2] - L1[2] * L2[0]
    if D != 0:
        x = Dx / D
        y = Dy / D
        return x,y
    else:
        return False

Пример использования:

L1 = line([0,1], [2,3])
L2 = line([2,3], [0,4])

R = intersection(L1, L2)
if R:
    print "Intersection detected:", R
else:
    print "No single intersection point detected"

a = [1,1]
b = [2,2]
c = [3,2]
d = [4,1]
def judge(a,b,c,d):
  if min(a[0],b[0])<=max(c[0],d[0]) and min(c[1],d[1])<=max(a[1],b[1]) and min(c[0],d[0])<=max(a[0],b[0]) and min(a[1],b[1])<=max(c[1],d[1]):
    return True
  else:
    return False
a = judge(a,b,c,d)
print(a)

Интеллектуальная рекомендация

Вам также может понравиться