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

Question

[Oli]

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

1 1 2 2
2 1 3 0

Вывод
0.707106781

Comments

[Сергей c0re]

отрезками или точками??
а по какому принципе измерять расстояние между отрезками? между ближайшими точками отрезков?

[Сергей delphinpro]

Сергей c0re, по тому же принципу, что и в математике. В школе должны были рассказывать.

[Александр Скуснов]

Сергей delphinpro, По-моему, нет такого понятия "расстояние между отрезками".

[Сергей c0re]

Сергей delphinpro, я в школе учился 30 лет назад )))

Answer 1

[Rsa97]

Назовём концы отрезка как A₁-A₂ и B₁-B₂
Для начала проверьте вариант, когда отрезки пересекаются. В этом случае расстояние между ними равно нулю.
Берём первый конец первого отрезка (A₁). Опускаем перпендикуляр на прямую, построенную на втором отрезке. Получаем точку пересечения O. Если точка O лежит внутри второго отрезка, то берём расстояние A₁O. Если нет, то берём минимальное из A₁B₁ и A₁B₂.
Повторяем для точек A₂, B₁ и B₂.
Из четырёх полученных расстояний выбираем минимальное. Это и будет расстоянием между непересекающимися отрезками.

Answer 2

[Alexandroppolus]

Задача разбивается на две более простые подзадачи.

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

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

Answer 3

[evgeniy_lm]

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

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

Comments

[Oli]

Мне в условии не дано, это между серединами или нет

[evgeniy_lm]

Oli, Ну других вариантов нет

[Wataru]

Oli, evgeniy_lm, Расстояние между фигурами - обычно расстояние между двумя ближайшими точками.

Answer 4

[Сергей c0re]

тупое решение в лоб - идем в поисковик, и просто тупо пишем: расстояние между отрезками

вторая же ссылка (ну лично у меня) - Ю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: ну, .... пробовали?? или нужно на подносе?