49 / 4 / 0
Регистрация: 18.12.2012
Сообщений: 247
Записей в блоге: 1
1

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

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

Author24 — интернет-сервис помощи студентам
Даны координаты точек двух отрезков, найти расстояние между ними.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
10.02.2014, 20:28
Ответы с готовыми решениями:

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

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

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

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

22
Диссидент
Эксперт C
27706 / 17322 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
11.02.2014, 16:42 21
Author24 — интернет-сервис помощи студентам
Цитата Сообщение от 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 22
Вариант - найти расстояние методом последовательных приближений:
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 23
Точное решение можно получить исследуя на экстремум функцию расстояния между прямыми заданными параметрически, которые содержат эти отрезки :
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
19.01.2024, 16:48
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
19.01.2024, 16:48
Помогаю со студенческими работами здесь

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

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

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

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


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru