Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 15.12.2009, 13:02
Obsidian

 
Сообщений: n/a

Нахождение точки пересечения 2 отрезков
Здравствуйте, я пытаюсь сделать граф дорог, и нужно создавать вершины(перекрестки) при пересечении 2 отрезков(дорог), при пересечении мне нужно сделать из 2 отрезков - 4 отрезка,один из концов которых находится в точке перекрестка. По какому алгоритму все это можно выполнить? Заранее спасибо что решили помочь
  #2  
Старый 15.12.2009, 14:28
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Стоит поискать в разделе "алгоритмы и методы"
  #3  
Старый 26.06.2010, 18:44
nestr

 
Сообщений: n/a

Все очень просто!
х1, у1 и х2,у2 - координаты вершин первого отрезка;
х3, у3 и х4,у4 - координаты вершин второго отрезка;

для нахождения пересечения составляем уравнения прямых:
первое уравнение:
(x-x1)/(x2-x1)=(y-y1)/(y2-y1);
второе уравнение
(x-x3)/(x4-x3)=(y-y3)/(y4-y3);
эти уравнения определяют прямую проходящую через две точки, то, что нам и надо.
Из этих уравнений находим х и у по следующим формулам:
x:=((x1*y2-x2*y1)*(x4-x3)-(x3*y4-x4*y3)*(x2-x1))/((y1-y2)*(x4-x3)-(y3-y4)*(x2-x1));
y:=((y3-y4)*x-(x3*y4-x4*y3))/(x4-x3);
так как наши прямые пересекаются, то у них есть общая точка пересечения с координатами (х,у), которую нам и надо найти.
для того, чтоб пересечение принадлежало нашим отрезкам, нужно его ограничить, т. е проверить условие:
если
(((x1<=x)and(x2>=x)and(x3<=x)and(x4>=x))or((y1<=y) and(y2>=y)and(y3<=y)and(y4>=y)))
то существует точка пересечения данных отрезков, а нет – то нет и точки пересечения.
Еще следует проверить параллельность этих отрезков при помощи угловых коэффициентов:
k1:=(x2-x1)/(y2-y1);
k2:=(x4-x3)/(y4-y3);
где k1 и k2 – тангенсы угла наклона отрезков к положительному направлению оси ОХ, если k1=k2, то отрезки параллельны, а значит, не имеют точек пересечения.

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

если остались вопросы или нужны исходники программ, пишите на мыло alexander.nestr@mail.ru или в icq 558213677.
  #4  
Старый 08.11.2010, 11:07
гость

 
Сообщений: n/a

По моему ошибка
По моему пропущен минус в первом уравнении для поиска Х. т.е. должно быть так
x:=-((x1*y2-x2*y1)*(x4-x3)-(x3*y4-x4*y3)*(x2-x1))/((y1-y2)*(x4-x3)-(y3-y4)*(x2-x1));
y:=((y3-y4)*(-x)-(x3*y4-x4*y3))/(x4-x3);
  #5  
Старый 21.12.2010, 23:43
aaaaaaaaaa

 
Сообщений: n/a

И это наверное, ещё не всё
Ещё надо бы обрабатывать k=NaN и Infinity
  #6  
Старый 16.03.2012, 12:02
Аватар для Vertex
Новичок

Отправить личное сообщение для Vertex Посмотреть профиль Найти все сообщения от Vertex
 
Регистрация: 22.06.2008
Адрес: Узбекистан, Ташкент
Сообщений: 22

Вариант
Что-то формулы очень сложные, выдают иногда ошибку деления на 0.
Да и факт пересечения не всегда определяет. Если кому-нибудь нужно - мой вариант:
Код:
BOOL	CrossLine(long x1, long y1, long x2, long y2, long x3, long y3, long x4, long y4, long &x, long &y) {
long	dx1 = x2 - x1;
long	dy1 = y2 - y1;
long	dx2 = x4 - x3;
long	dy2 = y4 - y3;
	x = dy1 * dx2 - dy2 * dx1;
	if(!x || !dx2)
		return
			false;
	y = x3 * y4 - y3 * x4;
	x = ((x1 * y2 - y1 * x2) * dx2 - y * dx1) / x;
	y = (dy2 * x - y) / dx2;
	return
		((x1 <= x && x2 >= x) || (x2 <= x && x1 >= x)) && ((x3 <= x && x4 >= x) || (x4 <= x && x3 >= x));
}
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
пересечение отрезков гость Реализация, исходники, языки 3 18.02.2011 13:17
Определить точки пересечения эллипсов like-nix Математические алгоритмы 3 13.10.2008 18:15
Нахождение максимально заданной точки Skylan Вычислительная геометрия 3 12.01.2008 17:02
Пересечение отрезков гость Реализация, исходники, языки 1 26.12.2007 00:29
Пересечение отрезков Lomir Задачи 2 22.10.2007 22:50