Расчет кратчайшего расстояния

Question

У меня есть программа, где пользователь может разместить на экране две коробки. Они могут быть размещены в любом месте, и я уже зафиксировал функцию, чтобы получить координаты x2, x1, y2 и y1 обоих полей. Теперь, когда пользователь разместил обе коробки, я хочу нарисовать линию между серединой одной из сторон на коробке1 до середины одной из сторон коробки2. Я хотел бы учесть кратчайшее расстояние между двумя сторонами. Так что линия, которая нарисована, всегда рисуется между сторонами двух ящиков, что приведет к кратчайшей линии.

В такой момент, я хотел бы больше внимания уделять математике в школе. Кто-нибудь может мне помочь? Это для веб-приложения, и я использую javascript.

Answer 1

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

Левый край - это потенциальная точка привязки, если другая координатная координата координатного блока меньше, чем текущая ячейка меньшего x-координаты.

Нижний край является потенциальной точкой привязки тогда и только тогда другой коробки «центра Y-координата больше, чем текущее поле» больше у-координат.

И так далее ...

После этого, у вас есть список кандидатов в обоих полях. Фактические опорные точки можно рассчитать как центр края (((edgeLeft + edgeRight)/2, (edgeTop + edgeBottom)/2)). Теперь вам нужно проверить, какая комбинация приводит к кратчайшей строке. Итерация каждого кандидата:

for each candidate1 in candidates of box 1 
    for each candidate2 in candidates of box2 
     ... 

Теперь проверьте, соответствует ли комбинация пересечению. Например. если candidate1 - левый край, а candidate2 имеет большую координату x, есть пересечение. Пропустите комбинации, которые приводят к пересечению.

Из других комбинаций вычислить длину линии (на самом деле квадрат длины: (candidate1.x-candidate2.x)^2 + (candidate1.y-candidate2.y)^2). Помните самый короткий, и у вас есть оптимальная линия подключения.

Поскольку у вас есть только 4 опорных точки на коробку, что приводит к 16 возможным комбинациям, вы также можете пропустить поиск кандидатов и проверить все ребра для пересечения.

Вы также можете слить ключ поиска кандидата и пересечения (в результате поиска кандидата в комбинации). Это позволяет вам выбирать жизнеспособные комбинации, где легче проверить пересечения.