У меня есть два выпуклых многоугольника в 3D. Они оба плоские на разных плоскостях, так что это пара лиц.
Как проще всего рассчитать ближайшее расстояние между этими двумя многоугольниками?
Изменить: длина самой короткой возможной линии, конечная точка которой находится в первом многоугольнике, а другая конечная точка - во втором многоугольнике. Расстояние, которое я ищу, - это длина этой самой короткой линии.
Это простая ограниченная оптимизация с линейными ограничениями и квадратичной целевой функцией. Можно использовать множество алгоритмов, например градиентный спуск.
Что ж, есть только несколько возможностей; Самая короткая линия между двумя полигонами может быть:
Все случаи 1-3 обрабатываются путем обработки каждой пары ребро + вершина как линейного сегмента и перечисления расстояние между всеми парами сегментов линии.
Для случая 4 найдите расстояние между каждой вершиной и плоскостью другого многоугольника. Убедитесь, что линия (от вершины до ближайшей точки на плоскости) находится внутри другого многоугольника; в противном случае самая короткая линия до другого многоугольника будет по его периметру, о чем уже позаботились в случае 1 или 2.
(обязательно выполните эту проверку для обоих многоугольники)
Для случая 5 хотя бы один отрезок линии должен пересекаться с площадью другого многоугольника - если бы они пересекались по своим периметрам, мы бы поймали его уже в случаях 1-3, а если бы вершина пересекала область, мы бы поймали это в случае 4. Так что просто проверьте пересечение каждого края с плоскостью другого многоугольника и посмотрите, точка пересечения находится внутри другого многоугольника.
(обязательно сделайте эту проверку для обоих многоугольников)
Возьмите минимальное расстояние, найденное во всем этом, и мы закончили.
Большинство людей предложили в этой цепочке «взять все точки / ребра одного многоугольника и сравнить с каждой точкой / ребрами другого». Это, вероятно, сработает нормально, если все, что вы сделаете, это сравните два довольно простых многоугольника, и если вы не слишком озабочены тем, чтобы сделать это быстро.
Однако, если вам нужен довольно простой и лучший способ. Используйте, как предлагает Бен Фойгт, метод квадратичной оптимизации (например, квадратичное программирование). По сути, ваши многоугольники - это ваш набор линейных ограничений, т.е. ваша точка решения должна лежать на внутренней стороне каждого края вашего многоугольника (это ограничение неравенства). И ваша функция затрат для оптимизации - это просто евклидово расстояние, то есть Q в стандартной формулировке - это просто единичная матрица. После того, как эта проблема была представлена как такая проблема, вы можете либо использовать библиотеку, которая решает эту проблему (их много), либо вы можете изучить ее из книги и накатать свой собственный код для нее (это довольно простой алгоритм для кодирования ).
Если вам нужен реальный метод для этого, например, если этот простой тест от многоугольника к многоугольнику является первым шагом к более сложным трехмерным формам (например, твердому телу из многоугольников). Тогда вам, скорее всего, следует просто использовать пакет, который уже делает это. Здесь представлен набор библиотек обнаружения столкновений, многие из которых определяют глубину проникновения. или, что то же самое, минимальное расстояние.
Непонятно, что вы пробовали.
Это похоже на сегменты как таковые.
Итак, все, что вам нужно сделать, это проверить все пары ребер. Я бы постарался реализовать это в первую очередь, прежде чем пытаться оптимизировать.
Вероятно, есть оптимизация при рассмотрении вектора от одного центроида к другому и только с учетом тех ребер, которые в некотором смысле находятся в этом направлении.
Прокрутите все вершины первого объекта, затем в этом цикле переберите все вершины второго объекта. В самом внутреннем цикле сравните расстояние между двумя текущими вершинами и сохраните наименьшее расстояние. Я делаю это все время, и пока у вас нет смехотворно большой сетки, это происходит практически мгновенно.
