Форум по Delphi программированию



Вернуться   Форум по Delphi программированию > Все о Delphi > [ "Начинающим" ]
Ник
Пароль
Регистрация <<         Правила форума         >> FAQ Пользователи Календарь Поиск Сообщения за сегодня Все разделы прочитаны

Ответ
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 20.03.2012, 15:54
Interface Interface вне форума
Активный
 
Регистрация: 23.05.2008
Адрес: Россия, Уфа
Сообщения: 203
Репутация: 1
По умолчанию Пересечение отрезков

Всем доброго времени суток. Давно я тут не появлялся
Сразу хочу извиниться:

- вопрос скорее относится к алгоритмам и математике, чем к программированию (т.е. за то, что не на тот форум)
- вопрос довольно примитивный(по форуму бегло поискал не нашел)
Итак, сам вопрос: Как определить пересекаются ли 2 отрезка. Но прежде чем меня закидают помидорами, отмечу: я уже решал эту задачу и меня интересует нахождение наиболее эффективного решения.
Сейчас у меня есть только одна мысль по этому поводу:

Возьмем 2 отрезка a и b.
Проверяем лежат ли концы отрезка b в разных полуплоскостях, которые - результат деления плоскости прямой, содержащей отрезок a. (не знаю, как написать это более адекватно)
И наоборот.
Если оба условия выполнены - то отрезки пересекаются.
Что бы проверить лежат ли отрезки в разных полуплоскостях я составлял уравнение прямой и проделывал некоторые другие несложные манипуляции.
Если я ошибся и таким образом нельзя определить пересечение отрезков - просьба сообщить мне об этом.

Собственно вопрос заключается в следующем :
Какие есть еще способы определения пересечения отрезков? Хотелось бы увидеть менее ресурсоемкие (содержащие меньшее количиство операций) способы. Код необязателен, т.к. все равно будет переписан с нуля. Мне нужен принцип\алгоритм.
__________________
Я ни в чем никогда не уверен... И в этом тоже...
Ответить с цитированием
  #2  
Старый 20.03.2012, 16:07
Аватар для NumLock
NumLock NumLock вне форума
Let Me Show You
 
Регистрация: 30.04.2010
Адрес: Северодвинск
Сообщения: 5,426
Версия Delphi: 7, XE5
Репутация: 59586
По умолчанию

Пересечение отрезков
__________________
Пишу программы за еду.
__________________
Ответить с цитированием
  #3  
Старый 20.03.2012, 16:33
Interface Interface вне форума
Активный
 
Регистрация: 23.05.2008
Адрес: Россия, Уфа
Сообщения: 203
Репутация: 1
По умолчанию

Да, именно о подобном способе я знаю. Спасибо за ссылку. Вопрос остается. Есть ли альтернативные способы решения этой задачи?
С сайта:
Цитата:
если у2 = у1 да, то принимаем k1 = 0 иначе
Определяем угловой коэффициент в уравнении прямой:
k1 = ( у2 - у1 ) / ( x2 - x1 )
Зачем такое условие? Может опечатка, ибо иначе это просто ненужная строка.
__________________
Я ни в чем никогда не уверен... И в этом тоже...

Последний раз редактировалось Interface, 20.03.2012 в 16:52.
Ответить с цитированием
  #4  
Старый 20.03.2012, 18:08
Аватар для Pilot_Red
Pilot_Red Pilot_Red вне форума
Продвинутый
 
Регистрация: 01.11.2006
Адрес: Карелия
Сообщения: 702
Версия Delphi: D7
Репутация: 11581
По умолчанию

Код:
function CollisionLine(LA1,LB1,LA2,LB2:Points):boolean;
var v1,v2,v3,v4:double;
begin
v1:=(lb2.X-la2.X)*(la1.y-la2.y)-(lb2.y-la2.y)*(la1.X-la2.X);
v2:=(lb2.X-la2.X)*(lb1.y-la2.y)-(lb2.y-la2.y)*(lb1.X-la2.X);
v3:=(lb1.X-la1.X)*(la2.y-la1.y)-(lb1.y-la1.y)*(la2.X-la1.X);
v4:=(lb1.X-la1.X)*(lb2.y-la1.y)-(lb1.y-la1.y)*(lb2.X-la1.X);
CollisionLine:=(v1*v2<0) and (v3*v4<0);

end;

где:
LA1,LB1 одна линия, соответственно LA2,LB2-вторая
Ответить с цитированием
Этот пользователь сказал Спасибо Pilot_Red за это полезное сообщение:
TennisAdept (12.06.2022)
Ответ



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

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

Ваши права в разделе
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения

BB-коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Быстрый переход


Часовой пояс GMT +3, время: 06:54.


 

Сайт

Форум

FAQ

RSS лента

Прочее

 

Copyright © Форум "Delphi Sources" by BrokenByte Software, 2004-2021

ВКонтакте   Facebook   Twitter   Ссылка на Telegram