@irina222222

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

Здравствуйте! Можете, пожалуйста, помочь. Как найти расстояние между отрезками? Нам на вход дают координаты концов сначала первого, затем второго отрезков. Например:
1 1 2 2
2 1 3 0


Вывод
0.707106781
  • Вопрос задан
  • 3079 просмотров
Пригласить эксперта
Ответы на вопрос 4
Rsa97
@Rsa97
Для правильного вопроса надо знать половину ответа
Назовём концы отрезка как A1-A2 и B1-B2
Для начала проверьте вариант, когда отрезки пересекаются. В этом случае расстояние между ними равно нулю.
Берём первый конец первого отрезка (A1). Опускаем перпендикуляр на прямую, построенную на втором отрезке. Получаем точку пересечения O. Если точка O лежит внутри второго отрезка, то берём расстояние A1O. Если нет, то берём минимальное из A1B1 и A1B2.
Повторяем для точек A2, B1 и B2.
Из четырёх полученных расстояний выбираем минимальное. Это и будет расстоянием между непересекающимися отрезками.
Ответ написан
Комментировать
Alexandroppolus
@Alexandroppolus
кодир
Задача разбивается на две более простые подзадачи.

1) Проверить пересечение отрезков. Если пересекаются, то расстояние равно 0. Можно посчитать площади треугольников, образованных вершинами отрезков. Пересечение будет, если они имеют разный знак +-.

2) если не пересекаются, то найти 4 расстояния, от каждого конца отрезка до другого отрезка. Это вреде обсуждалось тут ранее, поищи.
Ответ написан
Комментировать
@evgeniy_lm
Как найти расстояние между отрезками

Какое расстояние?
1. Между срединами отрезков или межу вершинами отрезков?
Если взять вариант между срединами, а формат записи
X11 Y11 X12 Y12
X21 Y21 X22 Y22
то получим значение 1,414213562 что ровно в два раза больше чем ваше
Ответ написан
erge
@erge
Примус починяю
тупое решение в лоб - идем в поисковик, и просто тупо пишем: расстояние между отрезками

вторая же ссылка (ну лично у меня) - Ю2.30. Расстояние между отрезками

там и описание и решение и код, правда на Си
берем его и переписываем на Python, получаем:

#!/usr/bin/env python3
# -*- coding: utf-8 -*- 

import math

def ras (x1, y1, x2, y2, x3, y3):
  ## Если отрезок вертикальный - меняем местами координаты каждой точки.
  if x1==x2:
    x1, y1 = y1, x1
    x2, y2 = y2, x2
    x3, y3 = y3, x3
  k=(y1-y2)/(x1-x2) ## Ищем коэффициенты уравнения прямой, которому принадлежит данный отрезок.
  d=y1-k*x1
  xz=(x3*x2-x3*x1+y2*y3-y1*y3+y1*d-y2*d)/(k*y2-k*y1+x2-x1)
  dl=-1
  if ( xz<=x2 and xz>=x1 ) or ( xz<=x1 and xz>=x2 ):
    dl=math.sqrt((x3-xz)*(x3-xz)+(y3-xz*k-d)*(y3-xz*k-d)) ## Проверим лежит ли основание высоты на отрезке.
  return dl


## Вводим параметры отрезков
# xa, ya, xb, yb = [1, 1, 2, 2]
# xc, yc, xd, yd = [2, 1, 3, 0]

xa, ya, xb, yb = [int(s) for s in input().split()]
xc, yc, xd, yd = [int(s) for s in input().split()]

min=-1
t=-2
s=-2

o=(xb-xa)*(-yd+yc)-(yb-ya)*(-xd+xc)
o1=(xb-xa)*(yc-ya)-(yb-ya)*(xc-xa)
o2=(-yd+yc)*(xc-xa)-(-xd+xc)*(yc-ya)

if o!=0:
  t=o1/o
  s=o2/o

if (t>=0 and s>=0) and (t<=1 and s<=1):
  min=0 ## Проверим пересекаются ли отрезки.
else: 
  ## Найдём наименьшую высоту опущенную из конца одного отрезка на другой.
  dl1=ras(xa,ya,xb,yb,xc,yc)
  min=dl1
  dl2=ras(xa,ya,xb,yb,xd,yd)
  if ( dl2<min and dl2!=-1 ) or min==-1 :
    min=dl2
  dl3=ras(xc,yc,xd,yd,xa,ya)
  if ( dl3<min and dl3!=-1 ) or min==-1 :
    min=dl3
  dl4=ras(xc,yc,xd,yd,xb,yb)
  if ( dl4<min and dl4!=-1) or min==-1 :
    min=dl4
  if min==-1 :
    ## В случае, если невозможно опустить высоту найдём минимальное расстояние между точками.
    dl1=math.sqrt((xa-xc)*(xa-xc)+(ya-yc)*(ya-yc))
    min=dl1
    dl2=math.sqrt((xb-xd)*(xb-xd)+(yb-yd)*(yb-yd))
    if dl2<min :
      min=dl2
    dl3=math.sqrt((xb-xc)*(xb-xc)+(yb-yc)*(yb-yc))
    if dl3<min :
      min=dl3
    dl4=math.sqrt((xa-xd)*(xa-xd)+(ya-yd)*(ya-yd))
    if dl4<min :
      min=dl4

print (min)


PS: ну, .... пробовали?? или нужно на подносе?
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы