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
24 / 21 / 3 Регистрация: 04.11.2014 Сообщений: 283 |
|
1 |
|
Пересечение двух отрезков24.05.2016, 23:58. Показов 65511. Ответов 6
Доброго времени суток. Передо мной стоит задача: написать программу для определения, пересекаются ли два отрезка на плоскости, а если пересекаются, то найти точку пересечения. Изначально вводятся координаты концов каждого отрезка x и y. Гуглил, везде выдаёт алгоритмы на C++, я c ним я не сильно дружу.
0 |
vdm_mar 39 / 39 / 25 Регистрация: 25.10.2015 Сообщений: 102 |
||||
25.05.2016, 01:57 |
2 |
|||
Код набросал на скорую руку — об улучшении не думал, некогда. Там еще и точки пересечения — с кучей чисел после запятой, не знаю, на сколько знаков округлить. Формулы нахождения координат точки пересечения (x, y) накидал на бумажке, из решения системы с двумя переменными (основа — формкла прямой Ax+By+C=0), проверил и в минусовых отрезках, вроде получается. Алгоритм — по двум точкам каждого из отезка определяем формулы прямых, на которых лежат отрезки (A1x+B1y+C1=0, A2x+B2y+C2=0) и точку пересечения, если она есть. Потом проверяем точку пересечения на нахождение ее на одном из отрезков. «Выплыло» деление на ноль, но это отдельный случай, когда отрезки параллельны.
0 |
438 / 430 / 159 Регистрация: 21.05.2016 Сообщений: 1,338 |
|
25.05.2016, 02:41 |
3 |
x = (-C1 — B1*y) / A1 Вот тут тоже деление на ноль
1 |
vdm_mar 39 / 39 / 25 Регистрация: 25.10.2015 Сообщений: 102 |
||||
25.05.2016, 02:56 |
4 |
|||
Точно, сенкс!
1 |
24 / 21 / 3 Регистрация: 04.11.2014 Сообщений: 283 |
|
25.05.2016, 20:38 [ТС] |
5 |
vdm_mar, спасибо за отзыв на мою просьбу, но это не совсем то, что необходимо. Вы написали программу для определения нахождения точки пересечения в принципе, а мне необходимо узнать пересекаются ли они в данный момент, без их продлевания до пересечения.
0 |
39 / 39 / 25 Регистрация: 25.10.2015 Сообщений: 102 |
|
25.05.2016, 20:46 |
6 |
Я отрезки не продлевал. Я проверял принадлежность точки пересечения прямых отрезкам. Вот подробней: Блин. Пока писал, нашёл в своём коде ошибки — нет проверки, если отрезки принадлежат одной прямой, и частично или полностью перекрывают друг друга. В общем, моему коду — отбой.
0 |
21 / 34 / 14 Регистрация: 23.07.2014 Сообщений: 148 |
|
28.05.2016, 21:58 |
7 |
В scipy есть для этого LinearEntity, и у него есть методы для определения параллельности, нахождения точки пересечения и тд и тп.
0 |
IT_Exp Эксперт 87844 / 49110 / 22898 Регистрация: 17.06.2006 Сообщений: 92,604 |
28.05.2016, 21:58 |
Помогаю со студенческими работами здесь Пересечение двух отрезков на числовой прямой Найти пересечение двух ОТРЕЗКОВ каждый из которых ограничен двумя точками Пересечение отрезков.
Пересечение отрезков Нужно узнать, пересекаются… Искать еще темы с ответами Или воспользуйтесь поиском по форуму: 7 |
Нельзя стоять в стороне,
Итак, мы имеем линейную систему:
A 1 * x + B 1 * y = C 1
A 2 * x + B 2 * y = C 2
допустим это с правилом Крамера, поэтому решение можно найти в детерминантах:
x = D x/D
y = D y/D
где D — главный определитель системы:
A 1 B 1
A 2 B 2
и D x и D y могут быть найдены из матриц:
C 1 B 1
C 2 B 2
и
A 1 C 1
A 2 C 2
(обратите внимание, так как столбец 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"
Справочный блогhttps://www.cnblogs.com/wuwangchuxin0924/p/6218494.html
https://blog.csdn.net/s0rose/article/details/78831570
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)
Интеллектуальная рекомендация
1037b -Reach Media (симуляция)
1037B — Reach Median time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output You are given an array aa of nn integers and an in…
Общий класс пейджинга ~
Сейчас я изучаю JSP, и я думаю о том, как перейти к нумерации страниц. Похоже, что существует несколько способов пейджинга в Интернете. Я только начал думать о том, чтобы поместить все записи в список…
[C ++] переменные и основные типы
1. Перечислите Из приведенного выше кода можно увидеть, что целочисленное значение не может быть назначено типу перечисления (требуется преобразование принудительного типа), но тип перечисления может …
Вам также может понравиться
SQLite система обучения 0-19
0, в последнее время используется SQLite много, но много вещей не очень хорошо, поэтому я хочу, чтобы узнать SQLITE. 1. Первое, что это недоразумение, синтаксис SQL по-прежнему отличается от си…
Модель цепочки ответственности
1. Концепция модели цепочки ответственности. Шаблон цепочки ответственности содержит несколько командных объектов и ряд объектов обработки. Каждый обрабатывающий объект определяет, какие командные объ…
Простой инструмент анализа производительности C ++
Наш серверный проект имеет десятки тысяч строк кода. Вчера я хотел проанализировать его узкие места производительности, чтобы увидеть, есть ли какие -либо места. GCC предоставляет __pretty_function__ …