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

@rim41 · Регистрация: 16.03.2020

Студворк — интернет-сервис помощи студентам

Известны координаты точек, ограничивающие два отрезка. Как найти расстояние между этими отрезками? Под расстоянием подразумевается минимальное расстояние между двумя точками, лежащими на отрезках.

Например, для отрезков (0, 0) (5, 5) и (7, 5) (10, 18) расстояние будет 2, а для отрезков (0, 0) (0, 3) и (-1, 6) (2, 3) расстояние равно корню из двух, тк отрезки будут находится на расстоянии диагонали условной клетки.

Пробовал спросить у ChatGPT, но он выдал неверный ответ

Байт · 15.02.2023, 13:55

Сообщение от rim41

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

Общий подход таков.
Записываем уравнение отрезков в параметрическом виде
X1 = A1*t + B1*(1-t) 0<=t <= 1
X2 = A2*s + B2*(1-s) 0<=s <= 1
Это векторные уравнения. Их надо расписать покоординатно
Записываем R = f(t, s) между точками X1 - X2
Можно брать не расстояние, а его квадрат. Здесь это без разницы
И находить минимум функции f(t,s) в квадрате 0 <= t, s <= 1. Методами матанализа. Т.е. искать производные, их нулевые значения в области. затем анализировать на границах области и в вершинах квадрата.
Возможно, для частных случаев есть какие-то готовые формулы. Но это самый общий метод. И подходит для любых фигур, как только для них удается найти хорошее параметрическое задание

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

Сообщение от rim41

Пробовал спросить у ChatGPT, но он выдал неверный ответ

я уже не первый раз слышу жалобы но этого Искусственного Идиотика

@mathmichel · 15.02.2023, 14:10

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

@VSI · 15.02.2023, 14:23

Сообщение от rim41

Пробовал спросить у ChatGPT, но он выдал неверный ответ

Хотелось бы увидеть ЭТОТ ОТВЕТ...

@rim41 · 15.02.2023, 14:36 **[ТС]**

Сообщение от Байт

Т.е. искать производные, их нулевые значения в области. затем анализировать на границах области и в вершинах квадрата.

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

Сообщение от VSI

ЭТОТ ОТВЕТ...

Он либо упорно выдаёт что ответом будет минимальное расстояние от точки до точки либо говорит что мало параметров

@mathmichel · 15.02.2023, 14:36

Вот так можно решить в Mathcad без помощи ChatGPT

@rim41 · 15.02.2023, 14:40 **[ТС]**

Немного поспорив и поизменяв формулировки я добился следующего:

Кликните здесь для просмотра всего текста

Да, формула, которую я привел в прошлом ответе, не учитывает случай перпендикулярных отрезков. Для таких отрезков можно использовать следующий алгоритм:

Найти проекции начальной и конечной точек каждого отрезка на другой отрезок.
Если обе проекции попадают на отрезок, то расстояние между отрезками равно расстоянию между проекциями.
Если только одна проекция попадает на отрезок, то расстояние между отрезками равно расстоянию от этой проекции до другого отрезка.
Если обе проекции не попадают на отрезок, то расстояние между отрезками равно расстоянию до ближайшей из двух конечных точек другого отрезка.
Используя этот алгоритм, формула для расстояния между двумя отрезками может быть записана следующим образом:

Вычислить вектора отрезков AB и CD и их длины.
Если длины векторов равны нулю, то отрезки совпадают, поэтому расстояние равно нулю.
Вычислить вектор AC.
Вычислить скалярные произведения векторов AB и AC, и CD и AC.
Если оба скалярных произведения меньше или равны нулю, то проекции точек A и B лежат на отрезке CD, поэтому расстояние равно расстоянию между отрезками AB и CD, которое можно найти как расстояние между точками A и проекцией точки A на отрезок CD (или между точками B и проекцией точки B на отрезок CD, которые дадут одинаковый результат).
Если только одно скалярное произведение меньше или равно нулю, то одна проекция лежит на отрезке CD, а другая - за его пределами, поэтому расстояние равно расстоянию от проекции точки A или B на отрезок CD до отрезка AB.
Если оба скалярных произведения больше нуля, то проекции точек A и B лежат за пределами отрезка CD, поэтому расстояние равно расстоянию до ближайшей из двух конечных точек отрезка CD.
В результате получим следующую формулу для расстояния между двумя отрезками:

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
AB = sqrt((xB-xA)^2 + (yB-yA)^2) # Длина отрезка AB
CD = sqrt((xD-xC)^2 + (yD-yC)^2) # Длина отрезка CD
AC = (xC-xA)*(xB-xA) + (yC-yA)*(yB-yA) # Скалярное произведение векторов AC и AB
BD = (xD-xB)*(xB-xA) + (yD-yB)*(yB-yA) # Скалярное произведение векторов BD и AB
if AB == 0 and CD == 0:
    distance = sqrt((xA-xC)^2 + (yA-yC)^2) # Отрезки совпадают
elif AB == 0:
    distance = point_to_segment_distance(xA, yA, xC, yC, xD, yD) # Отрезок AB вырожден
elif CD == 0:
    distance = point_to_segment_distance(xC, yC, xA, yA, xB, yB) # Отрезок CD вырожден
elif AC <= 0 and BD <= 0:
    distance = point_to_segment_distance(xA, yA, xC, yC, xD, yD) # Проекции лежат на отрезке CD
elif AC <= 0:
    distance = point_to_segment_distance(xA, yA, xC, yC, xD, yD) # Проекция точки A лежит на отрезке CD
elif BD <= 0:
    distance = point_to_segment_distance(xB, yB, xC, yC, xD, yD) # Проекция точки B лежит на отрезке CD
else:
    distance = min(point_to_point_distance(xA, yA, xC, yC),
                   point_to_point_distance(xA, yA, xD, yD),
                   point_to_point_distance(xB, yB, xC, yC),
                   point_to_point_distance(xB, yB, xD, yD)) # Проекции лежат за пределами отрезка CD

То есть вроде бы и ответ есть, но используются якобы имеющиеся функции point_to_point_distance и point_to_segment_distance.

Не по теме:

Интересно, что псевдокод он выдал практически полностью питоном. Вот она, пропаганда! Уже до нейросетей добралась. И язык ответа на вопрос по программированию по умолчанию в нем тоже питон...

@mathmichel · 15.02.2023, 14:47

Сообщение от rim41

но используются якобы имеющиеся функции point_to_point_distance и point_to_segment_distance.

Видно, что ChatGPT выдал правильный программный код на Питоне, который учитывает все случаи. А функции надо искать в соответствующих библиотеках для Питона.

@rim41 · 15.02.2023, 14:56 **[ТС]**

Сообщение от mathmichel

функции надо искать в соответствующих библиотеках для Питона.

не, это он от себя выдал, нет такого в питоне (к сожалению). Буду пытаться выбить из него код этих функций. Да и не особо питон это, тут для возведения в степень используется ^, а в питоне ^ - XOR, а в степень через ** возводят. Просто совпало, что он в псевдокоде elif использовал

Добавлено через 44 секунды

Сообщение от mathmichel

соответствующих библиотеках

А вот это вполне возможно, не обратил внимания на эти слова. Посмотрю, может кто-то уже реализовывал такое

Добавлено через 2 минуты

Сообщение от rim41

Буду пытаться выбить из него код этих функций

Пока получил следующее:

Python
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
import math
 
def point_to_segment_distance(x, y, x1, y1, x2, y2):
    """Вычисляет расстояние от точки (x, y) до отрезка, определяемого
    двумя точками (x1, y1) и (x2, y2).
 
    Аргументы:
    x, y -- координаты точки
    x1, y1 -- координаты первой точки отрезка
    x2, y2 -- координаты второй точки отрезка
 
    Возвращает:
    Расстояние от точки до отрезка.
    """
    # Если отрезок вырожден в точку, возвращаем расстояние до точки
    if x1 == x2 and y1 == y2:
        return math.sqrt((x - x1) ** 2 + (y - y1) ** 2)
 
    # Вычисляем проекцию точки на отрезок
    u = ((x - x1) * (x2 - x1) + (y - y1) * (y2 - y1)) / ((x2 - x1) ** 2 + (y2 - y1) ** 2)
    xp = x1 + u * (x2 - x1)
    yp = y1 + u * (y2 - y1)
 
    # Если проекция точки лежит внутри отрезка, возвращаем расстояние до неё
    if 0 <= u <= 1:
        return math.sqrt((x - xp) ** 2 + (y - yp) ** 2)
 
    # Иначе возвращаем расстояние до ближайшей из двух концов отрезка
    return min(math.sqrt((x - x1) ** 2 + (y - y1) ** 2),
               math.sqrt((x - x2) ** 2 + (y - y2) ** 2))
 
 
def point_to_point_distance(x1, y1, x2, y2):
    """Вычисляет расстояние между двумя точками.
 
    Аргументы:
    x1, y1 -- координаты первой точки
    x2, y2 -- координаты второй точки
 
    Возвращает:
    Расстояние между двумя точками.
    """
    return math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)

Буду подгонять под свои требования, оставлю это тут на случай если кому надо будет.

@Igor3D · 15.02.2023, 17:20

Ну если код доводить до ума то должен быть класс вектор/точка для которого реализованы 4 арифметических действия и небольшой набор ф-ций. Тогда текст будет выглядеть примерно так

C++
1
2
vec v = p2 - p1;  // векторная арифметика
float u = dot(v, p) / lengthSquared(v);  // скалярное произведение (dot) на квадрат длины

По решению. То что Вы нашли неплохо, но не вижу варианта где отрезки пересекаются. Пусть отрезки заданы парами точек (p0, p1) и (p2, p3). Тогда

p0 + (p1 - p0) * s = p2 + (p3 - p2) * t;

Расписываете по x и y, получаете 2 ур-я из которых находите 2 неизвестные s и t. Если оба от 0 до 1 - отрезки пересеклись и расстояние = 0.

К сожалению, на 3D случай это не обобщается, т.к. там прямые могут скрещиваться. Попытки прорваться "голым матаном" (брать производные и.т.п) неизменно тонут в бесконечном "расписывании"

Но это уже другая тема/история

Добавлено через 2 минуты

Не по теме:

Интересно сделает ли ТС класс "вектор"? Ставлю что нет, это покажется ненужным. Ну кто знает, все-таки надо верить в людей :)

@rim41 · 16.02.2023, 07:01 **[ТС]**

Сообщение от Igor3D

сделает ли ТС класс "вектор"?

Я делаю для себя некое подобие симуляции геометрических фигур на плоскости, и да, всё у меня представлено классами. Единственное, я взял не вектор, а отрезок, ибо пока что для меня не было критичным отсутствие конкретного направления, а ChatGPT при обращении к нему намного лучше понимает класс отрезка. В итоге функция выглядит так:

Python
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
def segments_distance(segment1: LineSegment, segment2: LineSegment) -> float:
    AB = segment1.length # Длина отрезка AB
    CD = segment2.length # Длина отрезка CD
    
    AC = (segment2.start.x - segment1.start.x) * (segment1.end.x - segment1.start.x) + (segment2.start.y - segment1.start.y) * (segment1.end.y-segment1.start.y) # Скалярное произведение векторов AC и AB
    BD = (segment2.end.x - segment1.end.x) * (segment1.end.x - segment1.start.x) + (segment2.end.y - segment1.end.y) * (segment1.end.y-segment1.start.y) # Скалярное произведение векторов BD и AB
 
    if AB == 0 and CD == 0:
        return math.sqrt((segment1.start.x - segment2.start.x) ** 2 + (segment1.start.y - segment2.start.y) ** 2)
 
    elif (AC <= 0) or (AB == 0) or (AC <= 0 and BD <= 0):
        return point_to_segment_distance(segment1.start, segment2)
    
    elif CD == 0:
        return point_to_segment_distance(segment2.start, segment1)
    
    elif BD <= 0:
        return point_to_segment_distance(segment1.end, segment2)
    
    return min(
            points_distance(segment1.start, segment2.start),
            points_distance(segment1.start, segment2.end),
            points_distance(segment1.end, segment2.start),
            points_distance(segment1.end, segment2.end)
        )

Может кому-то пригодится, перенести с питона на нужный язык в данном случае вообще не будет проблемой

@Worldmaster · 16.02.2023, 08:54

Сообщение от Байт

я уже не первый раз слышу жалобы но этого Искусственного Идиотика

Ну если не способны сформулировать внятно задачу то очевидно что и ответ получите соответствующий. Нормально ИИ справляется с той задачей для которой он был создан.

Сообщение от VSI

Хотелось бы увидеть ЭТОТ ОТВЕТ...

Вот что она мне сформулировала:

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
using System;
 
class Point {
    public double x, y;
 
    public Point(double x, double y) {
        this.x = x;
        this.y = y;
    }
}
 
class Line {
    public Point p1, p2;
 
    public Line(Point p1, Point p2) {
        this.p1 = p1;
        this.p2 = p2;
    }
}
 
class Program {
static double Distance(Line l1, Line l2) {
    double minDistance = double.MaxValue;
    double distance;
 
    distance = PointToPointDistance(l1.p1, l2.p1);
    if (distance < minDistance) minDistance = distance;
 
    distance = PointToPointDistance(l1.p1, l2.p2);
    if (distance < minDistance) minDistance = distance;
 
    distance = PointToPointDistance(l1.p2, l2.p1);
    if (distance < minDistance) minDistance = distance;
 
    distance = PointToPointDistance(l1.p2, l2.p2);
    if (distance < minDistance) minDistance = distance;
 
    return minDistance;
}
 
static double PointToPointDistance(Point p1, Point p2) {
    double dx = p2.x - p1.x;
    double dy = p2.y - p1.y;
 
    return Math.Sqrt(dx * dx + dy * dy);
}
 
    static void Main(string[] args) {
        Line l1 = new Line(new Point(0, 0), new Point(5, 5));
        Line l2 = new Line(new Point(7, 5), new Point(10, 18));
        double distance = Distance(l1, l2);
 
        Console.WriteLine("Distance: " + distance);
    }
}

Добавлено через 8 минут
Ну или другой вариант с перпендикуляром видимо на отрезок:

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
        static double Distance(Line l1, Line l2)
        {
            double minDistance = double.MaxValue;
            double distance;
 
            distance = PointToLineDistance(l1.p1, l2);
            if (distance < minDistance) minDistance = distance;
 
            distance = PointToLineDistance(l1.p2, l2);
            if (distance < minDistance) minDistance = distance;
 
            distance = PointToLineDistance(l2.p1, l1);
            if (distance < minDistance) minDistance = distance;
 
            distance = PointToLineDistance(l2.p2, l1);
            if (distance < minDistance) minDistance = distance;
 
            return minDistance;
        }
 
        static double PointToLineDistance(Point p, Line l)
        {
            double A = l.p2.Y - l.p1.Y;
            double B = l.p1.X - l.p2.X;
            double C = l.p2.X * l.p1.Y - l.p1.X * l.p2.Y;
 
            return Math.Abs(A * p.X + B * p.Y + C) / Math.Sqrt(A * A + B * B);
        }

Сообщение от rim41

Например, для отрезков (0, 0) (5, 5) и (7, 5) (10, 18) расстояние будет 2, а для отрезков (0, 0) (0, 3) и (-1, 6) (2, 3) расстояние равно корню из двух, тк отрезки будут находится на расстоянии диагонали условной клетки.

Вообще было бы не плохо чтобы ТС нарисовал на бумаге оба отрезка и показал графически что он считает минимальным расстоянием. Потому как с указанными точками не очень то получаются ответы:

расстояние будет 2

и

расстояние равно корню из двух

Вот на графике очевидно что в первом случае ТС берет расстояние между точками а во втором случае перпендикуляр на отрезок.
Если в первом случае опустить перпендикуляр то он не будет равен двум поскольку линия имеет наклон.

Сообщение от rim41

Интересно, что псевдокод он выдал практически полностью питоном. Вот она, пропаганда! Уже до нейросетей добралась. И язык ответа на вопрос по программированию по умолчанию в нем тоже питон...

На каком языке попросите на том гпт и напишет. Ей все равно.

@rim41 · 16.02.2023, 11:16 **[ТС]**

Worldmaster,

Не по теме:

можно узнать что за программка / сайт?

@Worldmaster · 16.02.2023, 13:16

Сообщение от rim41

можно узнать что за программка / сайт?

Что именно??

графике на Wolfram, код с GptChat

@Igor3D · 16.02.2023, 13:28

Сообщение от Worldmaster

Code
1
2
3
4
5
6
7
static double PointToLineDistance(Point p, Line l)
        {
            double A = l.p2.Y - l.p1.Y;
            double B = l.p1.X - l.p2.X;
            double C = l.p2.X * l.p1.Y - l.p1.X * l.p2.Y;
return Math.Abs(A * p.X + B * p.Y + C) / Math.Sqrt(A * A + B * B);
}

А можно узнать "геометрический смысл" (ну или "теоретические основы") такого решения? Напр чему соответствует A * p.X + B * p.Y ?

Спасибо

@Worldmaster · 16.02.2023, 13:30

Сообщение от Igor3D

А можно узнать "геометрический смысл" (ну или "теоретические основы") такого решения? Напр чему соответствует A * p.X + B * p.Y ?

Этот код сгенерирован ChatGPT. Не могу ручаться за правильность. Но мне кажется это вычисление перпендикуляра до линии и вычисление его длины.
ABC - это возможно общее уравнение прямой.

@mathmichel · 16.02.2023, 13:39

Сообщение от Igor3D

Попытки прорваться "голым матаном" (брать производные и.т.п) неизменно тонут в бесконечном "расписывании"

А зачем расписывать, если достаточно эту задачу предоставить математическому пакету!

Сообщение от Worldmaster

Потому как с указанными точками не очень то получаются ответы

У меня все эти ответы получились в Mathcad (пост под №6 в данном топике).

@rim41 · 16.02.2023, 14:01 **[ТС]**

Сообщение от Worldmaster

Wolfram

Я так посмотрел, wolfram - это довольно много всего, что именно позволяет так вводить данные и получать график?

@Igor3D · 16.02.2023, 14:20

Сообщение от Worldmaster

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

C - это векторное произведение векторов l.p1 и l.p2 (выходящих из начала координат O). Она же (двойная) площадь тр-ка (O, p1, p2)

(A * p.X + B * p.Y) - площадь (2) тр-ка (O, p, p + (p1 - p2))

А вот дальше как-то не сообразю

Сообщение от mathmichel

А зачем расписывать, если достаточно эту задачу предоставить математическому пакету!

Ну идеология "я раб лампы" не всем подходит

@Worldmaster · 16.02.2023, 14:28

Сообщение от rim41

Я так посмотрел, wolfram - это довольно много всего, что именно позволяет так вводить данные и получать график?

ну например простой запрос "Построение отрезка в Wolfram" приводит к мануалу Line Segment.

Ссылка на сегмент

Сообщение от mathmichel

У меня все эти ответы получились в Mathcad (пост под №6 в данном топике).

Получилось то получилось только теперь объясните что получилось то??

ТС нужен инструмент не для ручного использования наверное а функция которую можно было бы встроить в какое нибудь приложение.
А с маткадом то это как то не так просто получается.

Новые блоги и статьи Все статьи Все блоги /
Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114	Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .	Расчёт токов в цепи постоянного тока igorrr37 05.01.2026 / * Дана цепь постоянного тока с сопротивлениями и напряжениями. Надо найти токи в ветвях. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и решает её. Последовательность действий:. . .
Новый CodeBlocs. Версия 25.03 palva 04.01.2026 Оказывается, недавно вышла новая версия CodeBlocks за номером 25. 03. Когда-то давно я возился с только что вышедшей тогда версией 20. 03. С тех пор я давно снёс всё с компьютера и забыл. Теперь. . .	Модель микоризы: классовый агентный подход anaschu 02.01.2026 Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .	Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .

@rim41 1045 / 313 / 78 Регистрация: 16.03.2020 Сообщений: 954

	Как найти расстояние между двумя отрезками? 15.02.2023, 12:32. Показов 5061. Ответов 28 Метки нет (Все метки) Известны координаты точек, ограничивающие два отрезка. Как найти расстояние между этими отрезками? Под расстоянием подразумевается минимальное расстояние между двумя точками, лежащими на отрезках. Например, для отрезков (0, 0) (5, 5) и (7, 5) (10, 18) расстояние будет 2, а для отрезков (0, 0) (0, 3) и (-1, 6) (2, 3) расстояние равно корню из двух, тк отрезки будут находится на расстоянии диагонали условной клетки. Пробовал спросить у ChatGPT, но он выдал неверный ответ 0

@mathmichel $Эксперт по математике/физике$ 11066 / 7367 / 3989 Регистрация: 14.01.2014 Сообщений: 16,799
	15.02.2023, 14:10
	По сути дела всё это сводится к элементарной задаче нелинейного программирования с линейными ограничениями. Ничего сложного нет. 0

@mathmichel $Эксперт по математике/физике$ 11066 / 7367 / 3989 Регистрация: 14.01.2014 Сообщений: 16,799
	15.02.2023, 14:36
	Вот так можно решить в Mathcad без помощи ChatGPT Миниатюры 1

@rim41 1045 / 313 / 78 Регистрация: 16.03.2020 Сообщений: 954
	16.02.2023, 11:16 [ТС]
	Worldmaster, Не по теме: можно узнать что за программка / сайт? 0

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

Решение