Ближайшее расстояние между корпусом и коробкой

Question

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

Корпус задается гранями, вершинами, и я могу при необходимости триангулировать грани.

Answer 1

В статье приведен алгоритм поиска ближайшей пары между двумя выпуклыми оболочками.http://realtimecollisiondetection.net/pubs/SIGGRAPH04_Ericson_GJK_notes.pdf

В течение некоторого времени я думал, что, возможно, один из корпусов, поскольку AABB сделает этот алгоритм ненужным.К сожалению, я не обнаружил, что это правда.

Идея этого алгоритма состоит в том, что вы берете разницу Минковского в два корпуса.Ближайшая пара была бы точкой в ​​этой разности Минковского, ближайшей к началу координат.Теорема Картеодори гласит, что в трехмерном пространстве вам нужно только d + 1 точка, чтобы представить точку в корпусе.Таким образом, в основном вы выбираете наборы разности Минковского размером d + 1 и находите их самое близкое расстояние до начала координат.Ближайшая точка к началу координат найдена с помощью итерационного алгоритма.

Answer 2

Для корпуса внутри коробки (или любого другого выпуклого объекта):

Если они не пересекаются, то ближайшая точка в корпусе - это вершина корпуса, а не середина лица.

Простая итерация по всем вершинам корпуса и вычисление расстояния до каждой стороны коробки позволит вам найти пару точек (вершина корпуса + точка на поверхности бокса). Обратите внимание, что грань корпуса параллельна одной из граней бокса, вы получите более одной пары на одном расстоянии.

Корпус вне коробки:

Пара содержит точку края корпуса или коробки и точку на втором объекте. Итерация по всем краям корпуса и коробки и вычисление расстояния до всех граней другого объекта выглядит как подход, но лучше должен существовать.