Минимальное расстояние между двумя повернутыми прямоугольниками с разными углами

Question

Как рассчитать минимальное расстояние между двумя прямоугольниками?
Это просто для прямоугольников, у которых нет углов (то есть 0 градусов один), но для повернутых прямоугольников с любыми разными углами I не знаю как это сделать.

Можете ли вы порекомендовать какой-либо способ?

WhiteFlare

Answer 1

1. Рассчитать координаты всех 8 точек 2 прямоугольников.
2. Возьмите два наименьших расстояния среди всех 4 * 4 = 16 пар точек (точек из разных прямоугольников).И получить 3 точки P1, P2 и P3 {Две из них принадлежат одному прямоугольнику, а третьи к другому}
3. 2 точки, принадлежащие одному прямоугольнику, следует рассматривать как сегментсегмент и третья точка.

Answer 2

1. Убедитесь, что они сначала пересекаются (попробуйте взять точку из одного прямоугольника и проверить, находится ли она внутри другого прямоугольника).
   Есть несколько способов сделать это. Один из методов ( не самый лучший , но легко объяснимый) заключается в следующем.
   Пусть A1, A2, A3, A4 - точки прямоугольника, T - какой-то другой момент.
   Затем подсчитайте квадраты для треугольников:
   S1 = (A1,A2,T), S2 = S(A2,A3,T), S3 = S(A3, A4, T), S4 = S(A4, A1, A2).
   Пусть S_rectangle - квадрат прямоугольника.
   Тогда T лежит внутри прямоугольника <=> S1 + S2 + S3 + S4 = S_rectangle.
   
   Если реактивные треугольники не пересекаются друг с другом, выполните следующие действия.

2. Рассчитать координаты всех 8 точек 2 прямоугольников.

3. Возьмите минимум среди всех 4 * 4 = 16 пар точек (точек из разных прямоугольников).
   Давайте обозначим это min_1.

4. Затем возьмите некоторую точку из первого прямоугольника (4 способа сделать это),
   возьмите 4 сегмента другого прямоугольника (4 способа),
   отметьте любой перпендикуляр от этой точки, чтобы этот сегмент получил внутренний сегмент.
   Возьмите минимум таких перпендикуляров. Обозначим это min_2.

5. То же, что и в 3, но взять точку из второго прямоугольника, строки из первого:
   вы получите min_3.

6. result = min(min_1, min_2, min_3)