Расстояние между двумя выпуклыми многоугольниками в 3D

Ну, есть только несколько возможностей; самая короткая линия между двумя полигонами может быть:

1. между двумя вершинами
2. между ребром и вершиной
3. между двумя ребрами (Представьте себе два многоугольника на перпендикулярных плоскостях)
4. между вершиной и внутренней частью многоугольника
5. или многоугольники пересекаются

Случаи 1-3 решаются путем обработки каждой пары ребер + вершин как отрезка линии и перечисления расстояния . между всеми парами отрезков.

Для случая 4 Найдите расстояние между каждой вершиной и плоскостью другого многоугольника. Убедитесь, что линия (проходящая от вершины до ближайшей точки на плоскости) находится внутри другого многоугольника; если это не так, то Кратчайшая линия до другого многоугольника будет находиться по его периметру, о чем уже позаботились в случае 1 или 2.
(обязательно выполните эту проверку дляобоих полигонов)

Для случая 5, при хотя бы один отрезок прямой должен пересекаться с областью другого многоугольника - если бы они пересекались по своим периметрам, мы бы поймали его уже в случаях 1-3, а если бы вершина пересекла область, мы бы поймали ее в случае 4. Поэтому просто проверьте пересечениекаждого ребра с плоскостью другого многоугольника и посмотрите, находится ли точка пересечения внутри другого многоугольника.
(обязательно выполните эту проверку дляобоих полигонов)

Возьмите минимальное расстояние нашли во всем этом, и мы закончили.

То, что большинство людей предложили в этой теме, - это "взять все точки/ребра одного многоугольника и сравнить с каждой точкой / ребром другого". Это, вероятно, будет хорошо работать, если все, что вы делаете, это сравниваете два довольно простых полигона, и если вы не слишком заинтересованы в том, чтобы сделать это быстро.

Однако, если вы хотите довольно простой и лучший метод. Используйте, как предложил Бен Фойт, метод квадратичной оптимизации (т. е. квадратичное Программирование). В основном, ваши полигоны - это ваш набор линейные ограничения, то есть ваша точка решения должна лежать на внутренней стороне каждого ребра вашего полигона (это ограничение неравенства). И ваша функция затрат для оптимизации - это просто евклидово расстояние, то есть Q в стандартной формулировке-это просто матрица идентичности. После приведения в качестве такой задачи, вы можете либо использовать библиотеку, которая решает эту проблему (есть много таких), или вы можете изучить ее из книги и свернуть свой собственный код для нее (это довольно простой алгоритм для кодирования вверх).

Если вам нужен реальный метод для этого, например, если этот простой тест полигон-полигон является первым шагом к более сложным 3D-формам (например, твердое тело, состоящее из полигонов). Тогда, скорее всего, вы должны просто использовать пакет, который уже делает это. здесь - набор библиотек обнаружения столкновений, многие из которых выводят глубину проникновения или, что эквивалентно, минимальное расстояние.

Непонятно, что вы пробовали.

Это выглядит вероятным для сегментов как таковых.

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

Вероятно, существует оптимизация при рассмотрении вектора от одного центроида к другому и только при рассмотрении ребер, которые в некотором смысле находятся в этом направлении.

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