1

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

#include <iostream>
#include <cmath>
#include <algorithm>
#define ld long double

using namespace std;

ld mindiff;

ld distance(ld xa, ld ya, ld xb, ld yb) {
    return sqrt((xb - xa)*(xb - xa) + (yb - ya)*(yb - ya));
}

ld mindifference(ld x1, ld y1, ld x2, ld y2, ld x3, ld y3) {
    ld l = distance(x1, y1, x3, y3);
    ld r = distance(x2, y2, x3, y3);
    for (int i = 0; i <= 100; i++) {
        if (l <= r) {
            r = distance((x1 + x2) / 2, (y1 + y2) / 2, x3, y3);
            x2 = (x1 + x2) / 2;
            y2 = (y1 + y2) / 2;
        }
        else {
            l = distance((x1 + x2) / 2, (y1 + y2) / 2, x3, y3);
            x1 = (x1 + x2) / 2;
            y1 = (y1 + y2) / 2;
        }
    }
    return l;
}

int main() {
    ld x1, y1, x2, y2, xa, ya;
    cin >> x1 >> y1 >> x2 >> y2;
    cin >> xa >> ya;
    cout << fixed;
    cout.precision(6);
    cout << mindifference(x1, y1, x2, y2, xa, ya) << endl;
    return 0;
}
13
  • Совет: Нет смысла постоянно считать корни, можно работать с квадратами расстояний. Корень достаточно взять один раз, от полученного результата. 31 окт 2018 в 19:22
  • 2
    "перебрать точки на ... отрезке" - Вы знаете, сколько там, на отрезке, точек? Очень много.
    – user176262
    31 окт 2018 в 19:23
  • Эм.. Бинарный поиск предполагает монотонную функцию - не думаю, что расстояние между точками отрезков таковой является. А вот тернарный может подойти.
    – Qwertiy
    31 окт 2018 в 19:25
  • Ну да тернарным можно) 31 окт 2018 в 19:25
  • И вообще, стоп. Это же двумерная штука, а не одномерная.
    – Qwertiy
    31 окт 2018 в 19:25

1 ответ 1

4

Во-первых, для нахождения расстояния от точки (x, y) до отрезка (ax, ay)-(bx, by) не нужна никакая "бинарка". Использовать поисковый алгоритм для нахождения этого расстояния - безобразие. Это элементарная задача вычислительной геометрии. Например, в целых числах (не выжимая процессорные такты и не беспокоясь о переполнениях)

int point_to_segment_distance_sq(int x, int y, int ax, int ay, int bx, int by)
{
  // Обеспечим, чтобы наш отрезок был более горизонтальным, чем вертикальным
  int dx = bx - ax, dy = by - ay;
  if (std::abs(dx) < std::abs(dy))
  {
    std::swap(x, y);
    std::swap(ax, ay);
    std::swap(bx, by);
    std::swap(dx, dy);
  }

  // Обеспечим, чтобы наш отрезок шел слева направо
  if (dx < 0)
  {
    std::swap(ax, bx);
    std::swap(ay, by);
    dx = -dx;
    dy = -dy;
  }

  // Действия, выполненные выше, нужны только для того, чтобы впоследствии
  // мы могли проверить, попадает ли точка (px, py) (см. ниже) внутрь нашего
  // отрезка (ax, ay)-(bx, by). Теперь это можно сделать простым сравнением
  // `px < ax` и `px > bx` 

  // Строим уравнение прямой
  int A = dy, B = -dx, C = -(A * ax + B * bx);

  // Вычисляем ненормированное ориентированное расстояние от точки до прямой
  int d = A * x + B * y + C;

  // Находим проекцию нашей точки на прямую
  int absq = A * A + B * B;
  int px = x - A * d / absq, py = y - B * d / absq;

  // Проверяем, не попали ли мы за пределы отрезка
  if (px < ax)
  {
    px = ax;
    py = ay; 
  }
  else if (px > bx)
  {
    px = bx;
    py = by; 
  }

  // Возвращаем квадрат расстояния
  x -= px;
  y -= py;
  return x * x + y * y;
}

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

8
  • не нужна никакая "бинарка" - "у ней внутре - неонка". +1, конечно.
    – user176262
    31 окт 2018 в 20:22
  • Если мы запустим вашу программу из четырех концов,то не факт что ето будёт найменьшее расстояние,или я что то не понял? 31 окт 2018 в 20:29
  • @AndriyOleksievets да, Вы что-то не поняли
    – user176262
    31 окт 2018 в 20:34
  • @Andriy Oleksievets: Если отрезки не пересекаются - то факт. Если вы считаете, что это "не факт", то вам должно быть несложно привести контрпример, где минимальное расстояние достигается не на конце отрезка? 31 окт 2018 в 20:34
  • @AnT вырвано из контекста , но например если отрезки не лежат на одной плоскости)) 1 ноя 2018 в 16:53

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.