import numpy as np
def get_intersect(a1, a2, b1, b2):
"""
Returns the point of intersection of the lines passing through a2,a1 and b2,b1.
a1: [x, y] a point on the first line
a2: [x, y] another point on the first line
b1: [x, y] a point on the second line
b2: [x, y] another point on the second line
"""
s = np.vstack([a1,a2,b1,b2]) # s for stacked
h = np.hstack((s, np.ones((4, 1)))) # h for homogeneous
l1 = np.cross(h[0], h[1]) # get first line
l2 = np.cross(h[2], h[3]) # get second line
x, y, z = np.cross(l1, l2) # point of intersection
if z == 0: # lines are parallel
return (float('inf'), float('inf'))
return (x/z, y/z)
if __name__ == "__main__":
print get_intersect((0, 1), (0, 2), (1, 10), (1, 9)) # parallel lines
print get_intersect((0, 1), (0, 2), (1, 10), (2, 10)) # vertical and horizontal lines
print get_intersect((0, 1), (1, 2), (0, 10), (1, 9)) # another line for fun
Объяснение
Обратите внимание, что уравнение линии ax+by+c=0
. Итак, если точка находится на этой прямой, то это решение (a,b,c).(x,y,1)=0
(.
— скалярное произведение)
пусть l1=(a1,b1,c1)
, l2=(a2,b2,c2)
будут двумя линиями, а p1=(x1,y1,1)
, p2=(x2,y2,1)
будут двумя точками.
Нахождение прямой, проходящей через две точки:
пусть t=p1xp2
(перекрестное произведение двух точек) будет вектором, представляющим линию.
Мы знаем, что p1
находится на линии t
, потому что t.p1 = (p1xp2).p1=0
. Мы также знаем, что p2
находится на t
, потому что t.p2 = (p1xp2).p2=0
. Таким образом, t
должна быть линией, проходящей через p1
и p2
.
Это означает, что мы можем получить векторное представление линии, взяв векторное произведение двух точек на этой линии.
Находим точку пересечения:
Теперь пусть r=l1xl2
(перекрестное произведение двух прямых) будет вектором, представляющим точку
Мы знаем, что r
лежит на l1
, потому что r.l1=(l1xl2).l1=0
. Мы также знаем, что r
лежит на l2
, потому что r.l2=(l1xl2).l2=0
. Таким образом, r
должно быть точкой пересечения линий l1
и l2
.
Интересно, что мы можем найти точку пересечения, взяв векторное произведение двух прямых.
person
Norbu Tsering
schedule
10.03.2017