Алгоритм нахождения длины отрезка, соединяющего центр двух прямоугольников - PullRequest
Новая
       75

Алгоритм нахождения длины отрезка, соединяющего центр двух прямоугольников

1 голос
/ 09 декабря 2011

Хорошо, вот история: я нашел эту проблему в одной из коробок для пиццы несколько недель назад.В нем говорилось, что если вы сможете решить эту проблему до того, как закончите пиццу, вас наймут на работу в tripadviser.Хотя я не собираюсь брать на работу, эта проблема попала мне в глаза и испортила мне внимание к пицце и ужину.Я разработал что-то, но с некоторыми предположениями.Вот вопрос:

Предположим, мы знаем P, QR и S. Есть линия, соединяющая центры каждого прямоугольника.Нам нужно выяснить точки C и D. Я не уверен, есть ли какая-то другая переменная, которую мы должны знать, чтобы решить эту проблему.enter image description here

РЕДАКТИРОВАТЬ

Ищете объяснение программного или псевдокода - нет необходимости переходить на обмен.

Есть предложения?

Ответы [ 2 ]

4 голосов
/ 09 декабря 2011

Пошагово сделать это довольно просто:

  1. Вычислить A = (P + Q) / 2 и B = R + S / 2 (компонент за компонентом)
  2. Уравнение для линии между A и B: L(t) = t * A + (1 - t) * (B - A).Просто решите это линейное уравнение для t*, чтобы L(t*).y = Q.y получило C = L(t*).Проделайте то же самое с L (t) .y = Ry, чтобы получить D.

Вы также можете использовать значения t*, которые вы получаете при решении для C и D, для определения таких патологических случаев, какперекрывающиеся прямоугольники.

1 голос
/ 09 декабря 2011

На самом деле вам не нужно находить точки C и D, чтобы найти расстояние.

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

Теперь представьте себе вертикальную линию, проходящую через A, и горизонтальную линию, проходящую через B. Они пересекаются в точке, назовите это X. Также представьте вертикальную линию, проходящую через C, и назовите ее точку пересечения с верхним краем прямоугольника RS - C'.

Вы можете тривиально вычислить длину AX. Но длина AX - это половина высоты RS + половина высоты PQ (оба из которых вы знаете) + длина CC'.

Итак, теперь вы знаете длину CC' (назовите это x).

Вы также можете вычислить угол (назовите его n), который AB составляет с CC' из A и координат B, поскольку вы знаете, что CC' является вертикальным.

Ergo, длина сегмента CD равна x * cos(n).

...