Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.73/85: Рейтинг темы: голосов - 85, средняя оценка - 4.73
 Аватар для virtuos553
49 / 4 / 0
Регистрация: 18.12.2012
Сообщений: 247
Записей в блоге: 1

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

10.02.2014, 20:28. Показов 17281. Ответов 22
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Даны координаты точек двух отрезков, найти расстояние между ними.
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
10.02.2014, 20:28
Ответы с готовыми решениями:

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

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

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

22
Диссидент
Эксперт C
 Аватар для Байт
27714 / 17332 / 3810
Регистрация: 24.12.2010
Сообщений: 38,978
11.02.2014, 16:42
Студворк — интернет-сервис помощи студентам
Цитата Сообщение от programina Посмотреть сообщение
Все очень просто
Цитата Сообщение от virtuos553 Посмотреть сообщение
нужно найти точку на каждой прямой, и чтобы расстояние между ними было наименьшее
И совершенно очевидно, что эти точки вовсе не обязательно должны быть концевыми точками отрезков (хотя и могут ими быть).
Кстати, ТС тут допустил небольшую неточность. Видимо, следует читать "на каждом отрезке" Если б на прямой, то разговор был бы значительно проще.

Добавлено через 13 минут
Цитата Сообщение от Байт Посмотреть сообщение
разговор был бы значительно проще.
Вот 2 решения (для прямых).
1. Ищем экстремум указанной выше функции, но без ограничений 0<=t<=1 0<=s<=1. Такой экстремум один (не считая вырожденного случая параллельных прямых) - там всего-то 2 линейных уравнения df/dt = 0, df/ds = 0
2. Геометрический. Находим вектор N, перпендикулярный обоим прямым (векторное произведение AB x CD)
Строим плоскость P через т.А с нормалью N. Эта плоскость будет параллельна отрезку CD. Расстояние от точки С до плоскости Р и будет искомое.
Но, к сожалению, это не совсем то, что нужно ТС.
0
0 / 0 / 0
Регистрация: 19.12.2020
Сообщений: 7
19.12.2020, 21:23
Вариант - найти расстояние методом последовательных приближений:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>
 
/** 
 *  1. реализован основной алгоритм типа метода секущих Ньютона с минимальным интерфейсом для ввода параметров
 *  2. для удобства восприятия код сконцентрирован в одном файле
 */
using namespace std;
 
/** точка */
class Point {
public:
 
    Point() {
        x = 0;
        y = 0;
        z = 0;
    }
 
    Point(double inX, double inY, double inZ) {
        x = inX;
        y = inY;
        z = inZ;
    }
 
    void init(double inX, double inY, double inZ) {
        x = inX;
        y = inY;
        z = inZ;
 
    }
    double x;
    double y;
    double z;
};
 
/** отрезок */
class Line {
public:
    Point* A; //начало отрезка
    Point* B; //конец отрезка
    Point* M; //середина отрезка
 
    ~Line() {
        delete A;
        delete B;
        delete M;
    }
};
 
/** паттерн фабрика */
class InitFabriq {
public:
 
    static Point* createPoint(double x, double y, double z) {
        Point* p = new Point(x, y, z);
        return p;
    }
 
    static Line* createLine(Point* A, Point* B) {
        Point& refA = *A;
        Point& refB = *B;
        Point* M = InitFabriq::createPoint((refA.x + refB.x) / 2, (refA.y + refB.y) / 2, (refA.z + refB.z) / 2);
        Line* l = new Line();
        l->A = A;
        l->B = B;
        l->M = M;
        return l;
    }
 
    static Point* copyPoint(Point* src, Point* dst) {
        dst->x = src->x;
        dst->y = src->y;
        dst->z = src->z;
        return dst;
    }
 
    static Point* mediumPoint(Point* A, Point* B, Point* M) {
        Point& refA = *A;
        Point& refB = *B;
        M->x = (refA.x + refB.x) / 2;
        M->y = (refA.y + refB.y) / 2;
        M->z = (refA.z + refB.z) / 2;
        return M;
    }
};
 
/** нечто типа метода секущих Ньютона - сложность log(n) */
class Algoritm {
public:
 
    /** расстояние */
    static double distance(Point& A, Point& B) {
        return sqrt((A.x - B.x) *(A.x - B.x) + (A.y - B.y)*(A.y - B.y)+(A.z - B.z)*(A.z - B.z));
    }
 
    /** основной алгоритм */
    static double MediumLogScan(Line* line1, Line* line2, double inEps) {
 
        double dist[3];
 
        double eps = numeric_limits<double>::infinity();
        Point* focus = line1->M;
 
        int count = 0;
        while (eps > inEps) {
            dist[0] = Algoritm::distance(*focus, *line2->A);
            dist[1] = Algoritm::distance(*focus, *line2->M);
            dist[2] = Algoritm::distance(*focus, *line2->B);
            cout << "distances:" << dist[0] << "  " << dist[1] << "  " << dist[2] << endl;
            if (dist[0] > dist[2]) {
                InitFabriq::copyPoint(line2->M, line2->A);
                eps = abs(dist[1] - dist[0]);
            } else {
                InitFabriq::copyPoint(line2->M, line2->B);
                eps = abs(dist[1] - dist[2]);
            }
            line2->M = InitFabriq::mediumPoint(line2->A, line2->B, line2->M);
            count++;
        }
        cout << "distance=" << dist[1] << " iterations=" << count << endl;
        return dist[1];
    }
 
};
 
 
int main(int argc, char** argv) {
 
    cout << "Упрощенный интерфейс ввода параметров" << endl;
    cout << "Пример ввода точки пространства через пробел: 0.1 0.1 0.5" << endl;
    
    double a, b, c;
    cout << "Введите первую точку первого отрезка: " << endl;
    cin >> a >> b >> c;
    Point* A1 = InitFabriq::createPoint(a, b, c);
    cout << "Введите вторую точку первого отрезка: " << endl;
    cin >> a >> b >> c;
    Point* B1 = InitFabriq::createPoint(a, b, c);
    Line* line1 = InitFabriq::createLine(A1, B1);
 
    cout << "Введите первую точку второго отрезка: " << endl;
    cin >> a >> b >> c;
    Point* A2 = InitFabriq::createPoint(a, b, c);
    cout << "Введите вторую точку второго отрезка: " << endl;
    cin >> a >> b >> c;
    Point* B2 = InitFabriq::createPoint(a, b, c);
    Line* line2 = InitFabriq::createLine(A2, B2);
    
    cout << "Введите порядок точности(например такой 0.0001) " << endl;
    double eps;
    cin >> eps;
  
    Algoritm::MediumLogScan(line1, line2, eps);
    double result = Algoritm::MediumLogScan(line2, line1, eps);
    cout<<"Минимальное расстояние = "<<result<<endl;
 
 
    delete line1;
    delete line2;
 
    return 0;
}
0
0 / 0 / 0
Регистрация: 19.12.2020
Сообщений: 7
19.01.2024, 16:48
Точное решение можно получить исследуя на экстремум функцию расстояния между прямыми заданными параметрически, которые содержат эти отрезки :
http://www.cleverstudents.ru/l... space.html
1) Составляем параметрическое уравнение для первого отрезка типа x(t) = x0 + t(x1-x0), y(t) = y0 + t(y1-y0) ... и такие же для второго x(u), y(u) ... t меняется от 0 до 1, u тоже.
2) Записываем квадрат расстояния между точками как функцию d(u,t) = (x(t)-x(u))^2 + ...
3) Ищем ее экстремум дифференцированием. Если он в пределах [0,1] и для t, и для u - ура, найдено. Если нет - надо смотреть предельные расстояния для концов отрезков.

Одним словом, типичная задача поиска минимума функции двух переменных.
А вот собственно и вывод формул на python для экстремальных значений параметров {t, u} из уравнения отрезков. Это позволит вычислить пару точек-кандидатов для нахождения расстояния между отрезками:

Python
1
2
3
4
from sympy import *
init_printing(pretty_print=False)
t,u,x1,y1,z1,x2,y2,z2,x3,y3,z3,x4,y4,z4=symbols('t u x1 y1 z1 x2 y2 z2 x3 y3 z3 x4 y4 z4')
solve([diff((x1+t*(x2-x1)-x3-u*(x4-x3))**2+(y1+t*(y2-y1)-y3-u*(y4-y3))**2+(z1+t*(z2-z1)-y3-u*(z4-z3))**2,t),diff((x1+t*(x2-x1)-x3-u*(x4-x3))**2+(y1+t*(y2-y1)-y3-u*(y4-y3))**2+(z1+t*(z2-z1)-y3-u*(z4-z3))**2,u)], [t,u])
А вот ссылка на быстрый поиск расстояния между отрезками:
https://jasoncantarella.com/oc... melsky.pdf
https://stackoverflow.com/ques... ents-in-3d
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
19.01.2024, 16:48

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

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
23
Ответ Создать тему
Новые блоги и статьи
Запустил конкурс "тем и промптов для текстовых квестов созданных почти чисто ИИ"
Adler 06.10.2026
Всем привет! За последние три-четыре дня я создал более 16 текстовых квестовых игр используя преимущественно по одному запросу к ИИ на игру. Мне так понравилось смотреть все ветки/ сцены во всех. . .
ИИ не может найти нужный язык в списке
Supersumestria 05.10.2026
Я ему даю вот такое изображение и прошу найти и подчеркнуть немецкий язык. Возвращает он вот это: https:/ / i. **********/ vqBWLe2. png Нужную строчку в 3й колонке просто выдумал. . Это. . .
Новая последняя моя музыка в SUNO
zorxor 05.10.2026
Здравствуйте, дорогие мои друзья! С большой радостью я хотел бы представить вам свою новую последнею музыку, которую сгенерировала мне по моей просьбе нейросеть SUNO. С уважением, zorxor. Это. . .
Программный домашний кинотеатр
russiannick 27.09.2026
Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .
Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого
zorxor 21.09.2026
Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .
Мобильное приложение ColorStep
pavlinmavlin 17.09.2026
Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .
Запрет дублирования строк в табличной части
Maks 13.09.2026
Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .
Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр.
Jin X 06.09.2026
Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru