O
O
Oli2021-12-01 09:12:58
Python
Oli, 2021-12-01 09:12:58

How to find the distance between two segments?

Hello! Can you please help. How to find the distance between segments? We are given the coordinates of the ends first of the first, then the second segments. For example:

1 1 2 2
2 1 3 0


Conclusion
0.707106781

Answer the question

In order to leave comments, you need to log in

4 answer(s)
R
Rsa97, 2021-12-01
@Rsa97

Let's name the ends of the segment as A 1 -A 2 and B 1 -B 2
First, check the option when the segments intersect. In this case, the distance between them is zero.
Take the first end of the first segment (A 1 ). We lower the perpendicular to the straight line built on the second segment. We get the intersection point O. If the point O lies inside the second segment, then we take the distance A 1 O. If not, then we take the minimum of A 1 B 1 and A 1 B 2 .
Repeat for points A 2 , B 1 and B 2 .
From the four obtained distances, we choose the minimum. This will be the distance between non-intersecting segments.

A
Alexandroppolus, 2021-12-01
@Alexandroppolus

The task is divided into two simpler subtasks.
1) Check the intersection of the segments. If they intersect, then the distance is 0. You can calculate the areas of the triangles formed by the vertices of the segments. The intersection will be if they have a different +- sign.
2) if they do not intersect, then find 4 distances, from each end of the segment to the other segment. This harm was discussed here earlier, look.

E
evgeniy_lm, 2021-12-01
@evgeniy_lm

How to find the distance between line segments

What is the distance?
1. Between the midpoints of the segments or between the vertices of the segments?
If we take the option between the middle, and the notation is
X11 Y11 X12 Y12
X21 Y21 X22 Y22
, then we get the value 1.414213562, which is exactly twice as much as yours

S
Sergey c0re, 2021-12-06
@erge

stupid decision in the forehead - we go to the search engine, and just stupidly write: the distance between the segments
is the second link (well, personally for me) - Yu2.30. The distance between the segments
is there and the description and the solution and the code, although
we take it in C and rewrite it in Python, we get:

#!/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: well, .... have you tried it?? Or do you need it on a tray?

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question