Форум программистов, компьютерный форум CyberForum.ru

Найти расстояние между отрезками - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 4.87
virtuos553
 Аватар для virtuos553
48 / 3 / 1
Регистрация: 18.12.2012
Сообщений: 247
Записей в блоге: 1
10.02.2014, 20:28     Найти расстояние между отрезками #1
Даны координаты точек двух отрезков, найти расстояние между ними.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.02.2014, 20:28     Найти расстояние между отрезками
Посмотрите здесь:

Расстояние между двумя произвольно заданными на плоскости отрезками C++
C++ Найти наибольшее расстояние между точками
Найти расстояние между отрезком AB и прямой C++
C++ Задача на рекурсию. Найти кратчайшее расстояние между городами i и j даже если между ними нет прямой дороги
Скорость первого автомобиля V1 км/ч, второго — V2 км/ч, расстояние между ними S км. Определить расстояние между ними через T часов, если автомобили пе C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Chernobyl
211 / 211 / 67
Регистрация: 30.09.2012
Сообщений: 526
10.02.2014, 20:36     Найти расстояние между отрезками #2
Простая формула.
http://rudocs.exdat.com/pars_docs/tw..._m62270173.gif
Chernobyl
211 / 211 / 67
Регистрация: 30.09.2012
Сообщений: 526
10.02.2014, 20:44     Найти расстояние между отрезками #3
Прикрепил картинку.
Миниатюры
Найти расстояние между отрезками  
virtuos553
 Аватар для virtuos553
48 / 3 / 1
Регистрация: 18.12.2012
Сообщений: 247
Записей в блоге: 1
10.02.2014, 20:44  [ТС]     Найти расстояние между отрезками #4
Это расстояние между двумя точками, а мне нужно совсем другое
Amandosov
Знаток
156 / 156 / 65
Регистрация: 18.11.2012
Сообщений: 411
Записей в блоге: 2
10.02.2014, 20:45     Найти расстояние между отрезками #5
сейчас 1 минуту
Chernobyl
211 / 211 / 67
Регистрация: 30.09.2012
Сообщений: 526
10.02.2014, 20:47     Найти расстояние между отрезками #6
virtuos553, Простите, действительно поспешил.
virtuos553
 Аватар для virtuos553
48 / 3 / 1
Регистрация: 18.12.2012
Сообщений: 247
Записей в блоге: 1
10.02.2014, 22:04  [ТС]     Найти расстояние между отрезками #7
это не то

Добавлено через 10 секунд
хорошо
Байт
 Аватар для Байт
13941 / 8772 / 1220
Регистрация: 24.12.2010
Сообщений: 15,872
10.02.2014, 22:32     Найти расстояние между отрезками #8
Тут скорее математика, чем программирование...
Точки отрезка АВ задаются уравнением E = tA+(1-t)B (0<=t<=1), A,B - вектора, те. это 3 уравнения, надеюсь, понятно?
Соответственно F = tC + (1-s)D
Пишем функцию расстояния промежь Е и F - Пифагор в помощь! И находим ее минимум в квадрате 0<=t<=1, 0<=s<=1
Как положено. Экстремумы внутри области, на границах, и в вершинах квадрата. Кто будет меньше всех, тот и победил!
programina
 Аватар для programina
1912 / 597 / 37
Регистрация: 23.10.2011
Сообщений: 4,468
Записей в блоге: 2
10.02.2014, 22:36     Найти расстояние между отрезками #9
Цитата Сообщение от virtuos553 Посмотреть сообщение
Даны координаты точек двух отрезков, найти расстояние между ними.
А отрезки параллельны? Если нет, то невозможно найти расстояние.
AndrSlav
44 / 44 / 6
Регистрация: 20.12.2013
Сообщений: 241
10.02.2014, 22:46     Найти расстояние между отрезками #10
Цитата Сообщение от programina Посмотреть сообщение
Если нет, то невозможно найти расстояние.
Точнее, прямые, соответствующие этим отрезкам, не должны пересекаться.
Байт
 Аватар для Байт
13941 / 8772 / 1220
Регистрация: 24.12.2010
Сообщений: 15,872
10.02.2014, 22:57     Найти расстояние между отрезками #11
Цитата Сообщение от programina Посмотреть сообщение
А отрезки параллельны? Если нет, то невозможно найти расстояние.
Это круто! Вы бы хоть в свободную минуту посмотрели б, что такое расстояние Гугль, да и прочие поисковые системы, да и простой здравый смысл - в помощь.
Вопрос на засыпку - А между двумя непараллельными прямыми (в пространстве) расстояние найти возможно? Или (уже двумерный случай) между двумя окружностями?
Простите за возможную резкость, но не стоило, право слово, так сомневаться в наших возможностях.
Резюмирую. Расстояние есть? Оно определено? Как? Остается понять определение, и найти возможность это расстояние вычислить с наименьшими затратами

Добавлено через 1 минуту
Цитата Сообщение от AndrSlav Посмотреть сообщение
Точнее, прямые, соответствующие этим отрезкам, не должны пересекаться.
Господи Боже мой! А это откуда?
AndrSlav
44 / 44 / 6
Регистрация: 20.12.2013
Сообщений: 241
10.02.2014, 23:02     Найти расстояние между отрезками #12
Не успел добавить
Вообще, не очень понятно, что считать расстоянием между отрезками:
например, (0,0,0)-(1,1,0) и (10,10,10)-(20,20,10).
Здесь расстояние
a. не вычислить
b. 10 - расстояние между прямыми
с. расстояние между (1,1,0) и (10,10,10)
Мне ближе вариант b, но...

Добавлено через 1 минуту
Цитата Сообщение от Байт Посмотреть сообщение
Господи Боже мой! А это откуда?
Это как раз если считать расстояние между прямыми по перпендикуляру, вроде.

Ну и,соответственно,
d.
e.
f
...
Байт
 Аватар для Байт
13941 / 8772 / 1220
Регистрация: 24.12.2010
Сообщений: 15,872
10.02.2014, 23:04     Найти расстояние между отрезками #13
AndrSlav, Вы уже на правильном пути. Вы начинаете сомневаться. Но на всякий случай, выясните, что такое есть расстояние между двух множеств. Подсказать? Или сами догадаетесь?
AndrSlav
44 / 44 / 6
Регистрация: 20.12.2013
Сообщений: 241
10.02.2014, 23:10     Найти расстояние между отрезками #14
Цитата Сообщение от Байт Посмотреть сообщение
что такое есть расстояние между двух множеств.
Понятно, что расстояние - общее понятие, вот если бы было сказано "минимальное" или "максимальное" или между таких-то точек... Но, мне кажется (каюсь, не проверял), что расстояние между непересекающимися прямыми, например,- это по умолчанию минимальное расстояние.

Добавлено через 1 минуту
Цитата Сообщение от Байт Посмотреть сообщение
Подсказать? Или сами догадаетесь?
Или Вы считаете, что между скрещивающимися прямыми расстояние не так находится?
Байт
 Аватар для Байт
13941 / 8772 / 1220
Регистрация: 24.12.2010
Сообщений: 15,872
10.02.2014, 23:31     Найти расстояние между отрезками #15
Цитата Сообщение от AndrSlav Посмотреть сообщение
Понятно, что расстояние
Нет, вы меня положительно радуете (это всерьез). Даже не прочтя определения, вы уже сами, интуитивно к нему подходите. Так Лейбниц и Ньютон пытались понять, что такое дифференциал, и каждый понимал его по своему, каждый придумывал свои закорючки, но в итоге все оказалось одинаково.
Так вот. Определение. Расстояние между двумя множествами (в евклидовом пространстве, есствно, ибо только там понятие "расстояния" определено) это наименьшее расстояние между парами точек, к этим множествам принадлежащим"

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

Добавлено через 2 минуты
Цитата Сообщение от AndrSlav Посмотреть сообщение
между скрещивающимися прямыми расстояние не так находится?
Там нас спасает бесконечность. И векторная алгебра.
AndrSlav
44 / 44 / 6
Регистрация: 20.12.2013
Сообщений: 241
10.02.2014, 23:40     Найти расстояние между отрезками #16
Цитата Сообщение от Байт Посмотреть сообщение
Даже не прочтя определения
Ну, тык, мануал читается, если ничего не работает Для простых людей лучше писать прямо Функции. Найти расстояние между двумя заданными множествами точек на плоскости
programina
 Аватар для programina
1912 / 597 / 37
Регистрация: 23.10.2011
Сообщений: 4,468
Записей в блоге: 2
10.02.2014, 23:42     Найти расстояние между отрезками #17
Цитата Сообщение от Байт Посмотреть сообщение
Это круто! Вы бы хоть в свободную минуту посмотрели б, что такое расстояние Гугль, да и прочие поисковые системы, да и простой здравый смысл - в помощь.
Ну смотрите, расстояние от меня до центра Земли допустим 6000 кМ. Если я буду мерить это расстояние не от центра Земли, а от центра Солнца, то этот отрезок тоже можно обозвать расстоянием от меня до центра Земли, но он будет значительно отличаться от отрезка измеренного из центра Земли до меня. Поэтому никакого конкретного расстояния найти нельзя если заблаговременно не определить откуда до куда мерить.
virtuos553
 Аватар для virtuos553
48 / 3 / 1
Регистрация: 18.12.2012
Сообщений: 247
Записей в блоге: 1
11.02.2014, 08:13  [ТС]     Найти расстояние между отрезками #18
В моей задаче найти расстояние, означает найти наименьшее расстояние между этими отрезками, как правильно было выше сказано, нужно найти точку на каждой прямой, и чтобы расстояние между ними было наименьшее, проблема заключается в самом алгоритме, я не знаю как решать ибо слишком много случаев вырисовывается
Байт
 Аватар для Байт
13941 / 8772 / 1220
Регистрация: 24.12.2010
Сообщений: 15,872
11.02.2014, 11:02     Найти расстояние между отрезками #19
virtuos553, обратите внимание на пост #8. Там я допустил ошибку (описку), поэтому повторю.
Цитата Сообщение от Байт Посмотреть сообщение
Точки отрезка АВ задаются уравнением E = tA+(1-t)B (0<=t<=1), A,B - вектора, те. это 3 уравнения, надеюсь, понятно?
Соответственно F = sC + (1-s)D
|EF| = http://www.cyberforum.ru/cgi-bin/latex.cgi?\sqrt{{(tAx+(1-t)Bx-sCx-(1-s)Dx)}^{2} + {(tAy+(1-t)By-sCy-(1-s)Dy)}^{2} + {(tAx+(1-t)Bz-sCz-(1-s)Dz)}^{2}}
У этой функции от 2-х переменных надо найти минимум в квадрате 0<=t<=1, 0<=s<=1
Корень можно убрать.
Далее ищите экстремумы внутри квадрата, на границах, в вершинах. Берете самый маленький. Это будет ОН.
Занудливо, но ничего страшного по сути.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.02.2014, 13:06     Найти расстояние между отрезками
Еще ссылки по теме:

C++ Найти наибольшее расстояние между точками
C++ Найти максимальное расстояние между точками на плоскости
C++ Найти расстояние между символами с1 и с2

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
programina
 Аватар для programina
1912 / 597 / 37
Регистрация: 23.10.2011
Сообщений: 4,468
Записей в блоге: 2
11.02.2014, 13:06     Найти расстояние между отрезками #20
virtuos553, в чем тогда проблема? Все очень просто, находите расстояния между точками.
C++
  struct P
  {
    float x, y;
  };
 
  P a, b; // отрезок АB
  a.x = 3.0; a.y = 4.0;
  b.x = 8.0; b.y = 1.0;
  P c, d; // отрезок CD
  c.x = 5.0; c.y = 7.0;
  d.x = 9.0; d.y = 5.0;
  
  // расстояние от точки A до точки C
  float distance = pow( pow(a.x-c.x,2)+pow(a.y-c.y,2) , 0.5 );
 
  // и так далее находите расстояния между всеми
  // нужными точками
  // самое малое расстояние будет ответом
Yandex
Объявления
11.02.2014, 13:06     Найти расстояние между отрезками
Ответ Создать тему
Опции темы

Текущее время: 08:58. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru