Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.86/22: Рейтинг темы: голосов - 22, средняя оценка - 4.86
virtuos553
48 / 3 / 0
Регистрация: 18.12.2012
Сообщений: 247
Записей в блоге: 1
1

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

10.02.2014, 20:28. Просмотров 4412. Ответов 20
Метки нет (Все метки)

Даны координаты точек двух отрезков, найти расстояние между ними.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.02.2014, 20:28
Ответы с готовыми решениями:

Расстояние между двумя произвольно заданными на плоскости отрезками
Ребят, подскажите как найти расстояние между двумя произвольно заданными на плоскости отрезками...

Найти расстояние от начала координат до каждой точки и расстояние между точками
задача на С++ На плоскости заданы точки своими координатами. Найти расстояние от начала координат...

Расстояние между двумя множествами точек - это расстояние между наиболее близко расположенными точками этих
1. Расстояние между двумя множествами точек - это расстояние между наиболее близко расположенными...

Задача на рекурсию. Найти кратчайшее расстояние между городами i и j даже если между ними нет прямой дороги
Дана матрица размером NxN с расстояниями между городами при наличии прямой дороги между ними. По...

Скорость первого автомобиля V1 км/ч, второго — V2 км/ч, расстояние между ними S км. Определить расстояние между ними через T часов, если автомобили пе
Скорость первого автомобиля V1 км/ч, второго — V2 км/ч, расстояние между ними S км. Определить...

20
Chernobyl
221 / 221 / 69
Регистрация: 30.09.2012
Сообщений: 545
10.02.2014, 20:36 2
Простая формула.
http://rudocs.exdat.com/pars_docs/tw..._m62270173.gif
0
Chernobyl
221 / 221 / 69
Регистрация: 30.09.2012
Сообщений: 545
10.02.2014, 20:44 3
Прикрепил картинку.
0
Миниатюры
Найти расстояние между отрезками  
virtuos553
48 / 3 / 0
Регистрация: 18.12.2012
Сообщений: 247
Записей в блоге: 1
10.02.2014, 20:44  [ТС] 4
Это расстояние между двумя точками, а мне нужно совсем другое
0
Amandosov
Знаток
156 / 156 / 185
Регистрация: 18.11.2012
Сообщений: 411
Записей в блоге: 2
10.02.2014, 20:45 5
сейчас 1 минуту
0
Chernobyl
221 / 221 / 69
Регистрация: 30.09.2012
Сообщений: 545
10.02.2014, 20:47 6
virtuos553, Простите, действительно поспешил.
0
virtuos553
48 / 3 / 0
Регистрация: 18.12.2012
Сообщений: 247
Записей в блоге: 1
10.02.2014, 22:04  [ТС] 7
это не то

Добавлено через 10 секунд
хорошо
0
Байт
Эксперт C
20290 / 12854 / 2689
Регистрация: 24.12.2010
Сообщений: 26,851
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
Как положено. Экстремумы внутри области, на границах, и в вершинах квадрата. Кто будет меньше всех, тот и победил!
1
programina
2053 / 608 / 41
Регистрация: 23.10.2011
Сообщений: 4,468
Записей в блоге: 2
10.02.2014, 22:36 9
Цитата Сообщение от virtuos553 Посмотреть сообщение
Даны координаты точек двух отрезков, найти расстояние между ними.
А отрезки параллельны? Если нет, то невозможно найти расстояние.
0
AndrSlav
65 / 53 / 14
Регистрация: 20.12.2013
Сообщений: 461
10.02.2014, 22:46 10
Цитата Сообщение от programina Посмотреть сообщение
Если нет, то невозможно найти расстояние.
Точнее, прямые, соответствующие этим отрезкам, не должны пересекаться.
0
Байт
Эксперт C
20290 / 12854 / 2689
Регистрация: 24.12.2010
Сообщений: 26,851
10.02.2014, 22:57 11
Цитата Сообщение от programina Посмотреть сообщение
А отрезки параллельны? Если нет, то невозможно найти расстояние.
Это круто! Вы бы хоть в свободную минуту посмотрели б, что такое расстояние Гугль, да и прочие поисковые системы, да и простой здравый смысл - в помощь.
Вопрос на засыпку - А между двумя непараллельными прямыми (в пространстве) расстояние найти возможно? Или (уже двумерный случай) между двумя окружностями?
Простите за возможную резкость, но не стоило, право слово, так сомневаться в наших возможностях.
Резюмирую. Расстояние есть? Оно определено? Как? Остается понять определение, и найти возможность это расстояние вычислить с наименьшими затратами

Добавлено через 1 минуту
Цитата Сообщение от AndrSlav Посмотреть сообщение
Точнее, прямые, соответствующие этим отрезкам, не должны пересекаться.
Господи Боже мой! А это откуда?
0
AndrSlav
65 / 53 / 14
Регистрация: 20.12.2013
Сообщений: 461
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
...
0
Байт
Эксперт C
20290 / 12854 / 2689
Регистрация: 24.12.2010
Сообщений: 26,851
10.02.2014, 23:04 13
AndrSlav, Вы уже на правильном пути. Вы начинаете сомневаться. Но на всякий случай, выясните, что такое есть расстояние между двух множеств. Подсказать? Или сами догадаетесь?
0
AndrSlav
65 / 53 / 14
Регистрация: 20.12.2013
Сообщений: 461
10.02.2014, 23:10 14
Цитата Сообщение от Байт Посмотреть сообщение
что такое есть расстояние между двух множеств.
Понятно, что расстояние - общее понятие, вот если бы было сказано "минимальное" или "максимальное" или между таких-то точек... Но, мне кажется (каюсь, не проверял), что расстояние между непересекающимися прямыми, например,- это по умолчанию минимальное расстояние.

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

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

Добавлено через 2 минуты
Цитата Сообщение от AndrSlav Посмотреть сообщение
между скрещивающимися прямыми расстояние не так находится?
Там нас спасает бесконечность. И векторная алгебра.
0
AndrSlav
65 / 53 / 14
Регистрация: 20.12.2013
Сообщений: 461
10.02.2014, 23:40 16
Цитата Сообщение от Байт Посмотреть сообщение
Даже не прочтя определения
Ну, тык, мануал читается, если ничего не работает Для простых людей лучше писать прямо Функции. Найти расстояние между двумя заданными множествами точек на плоскости
0
programina
2053 / 608 / 41
Регистрация: 23.10.2011
Сообщений: 4,468
Записей в блоге: 2
10.02.2014, 23:42 17
Цитата Сообщение от Байт Посмотреть сообщение
Это круто! Вы бы хоть в свободную минуту посмотрели б, что такое расстояние Гугль, да и прочие поисковые системы, да и простой здравый смысл - в помощь.
Ну смотрите, расстояние от меня до центра Земли допустим 6000 кМ. Если я буду мерить это расстояние не от центра Земли, а от центра Солнца, то этот отрезок тоже можно обозвать расстоянием от меня до центра Земли, но он будет значительно отличаться от отрезка измеренного из центра Земли до меня. Поэтому никакого конкретного расстояния найти нельзя если заблаговременно не определить откуда до куда мерить.
0
virtuos553
48 / 3 / 0
Регистрация: 18.12.2012
Сообщений: 247
Записей в блоге: 1
11.02.2014, 08:13  [ТС] 18
В моей задаче найти расстояние, означает найти наименьшее расстояние между этими отрезками, как правильно было выше сказано, нужно найти точку на каждой прямой, и чтобы расстояние между ними было наименьшее, проблема заключается в самом алгоритме, я не знаю как решать ибо слишком много случаев вырисовывается
0
Байт
Эксперт C
20290 / 12854 / 2689
Регистрация: 24.12.2010
Сообщений: 26,851
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
Корень можно убрать.
Далее ищите экстремумы внутри квадрата, на границах, в вершинах. Берете самый маленький. Это будет ОН.
Занудливо, но ничего страшного по сути.
1
programina
2053 / 608 / 41
Регистрация: 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 );
 
  // и так далее находите расстояния между всеми
  // нужными точками
  // самое малое расстояние будет ответом
0
11.02.2014, 13:06
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.02.2014, 13:06

Найти расстояние между символами с1 и с2
я смог сделать только что бы подсчитывались все символы в строке, то есть общее количество...

Найти расстояние между множествами
Расстояние между двумя множествами точек – это расстояние между наиболее близко расположенными...

Найти расстояние между множествами
Расстояние между двумя множествами точек – это расстояние между наиболее близко расположенными...


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru