Имам два изпъкнали многоъгълника в 3D. И двете са плоски на различни равнини, така че са двойка лица.
Кой е най-простият начин за изчисляване на най-близкото разстояние между тези два многоъгълника?
Редактиране: Дължината на възможно най-късата линия, която има крайна точка в първия многоъгълник и друга крайна точка във втория многоъгълник. Разстоянието, което търся, е дължината на тази възможно най-къса линия.
Това е проста ограничена оптимизация с линейни ограничения и квадратична целева функция. Има много алгоритми, които могат да се използват, като градиентно спускане.
Е, има само няколко възможности; най-късата линия между двата полигона може да бъде:
Всички случаи 1-3 се решават чрез третиране на всеки ръб + двойка върхове като линеен сегмент и изброяване на разстояние между всички двойки линии-сегменти.
За случай 4 намерете разстоянието между всеки връх и равнината на другия многоъгълник. Проверете, за да се уверите, че линията (простираща се от върха до най-близката точка на равнината) е вътре в другия многоъгълник; ако не е, тогава най-късата линия до другия многоъгълник ще бъде по неговия периметър, за който вече се погрижихме в случай 1 или 2.
(не забравяйте да направите тази проверка и за и двете многоъгълници)
За случай 5 поне един сегмент трябва да се пресича с площта на другия многоъгълник - ако се пресичат по периметрите си, щяхме да го уловим вече в случаи 1-3, а ако връх пресече областта, щяхме да уловим в случай 4. Затова просто проверете пресечната точка на всеки ръб с равнината на другия многоъгълник и вижте дали пресечната точка е вътре в другия многоъгълник.
(не забравяйте да направите тази проверка за и двата многоъгълника)
Вземете минималното разстояние, намерено във всичко това, и сме готови.
Това, което повечето хора са предложили в тази тема, е "вземете всички точки/ръбове на един многоъгълник и сравнете с всяка точка/ръбове на другия". Това вероятно ще работи добре, ако всичко, което правите, е да сравнявате два доста прости полигона и ако не сте твърде загрижени да правите това бързо.
Ако обаче искате доста лесен и по-добър метод. Използвайте, както е предложено от Ben Voigt, метод за квадратична оптимизация (т.е. Квадратно програмиране). По принцип вашите полигони са вашият набор от линейни ограничения, т.е. вашата точка на решение трябва да лежи към вътрешната страна на всеки ръб на вашия многоъгълник (това е ограничение от неравенство). И вашата разходна функция, която трябва да оптимизирате, е само евклидовото разстояние, т.е. Q в стандартната формулировка е само матрицата на идентичност. Веднъж хвърлен като такъв проблем, можете или да използвате библиотека, която решава този проблем (има много от тях там), или можете да го изучавате от книга и да навиете свой собствен код за него (това е доста лесен алгоритъм за кодиране ).
Ако искате реален метод за това, например, ако този прост тест от многоъгълник към многоъгълник е първата стъпка към по-сложни 3D форми (като твърдо тяло, направено от многоъгълници). Тогава най-вероятно просто трябва да използвате пакет, който вече прави това. Тук е набор от библиотеки за откриване на сблъсък, много от които извеждат дълбочина на проникване или, еквивалентно, минимално разстояние.
Не е ясно какво сте опитали.
Това изглежда вероятно за сегментите сами по себе си.
Тогава всичко, което трябва да направите, е да проверите всички двойки ръбове. Бих искал първо да внедря това, преди да се опитам да оптимизирам.
Вероятно има оптимизация при разглеждането на вектора от единия центроид към другия и разглеждането само на ръбове, които са в някакъв смисъл в тази посока.
Преминете през всички върхове на първия обект, след това в този цикъл преминете през всички върхове на втория обект. Във вашия най-вътрешен цикъл сравнете разстоянието между двата текущи върха и запазете най-ниското разстояние. Правя го по този начин през цялото време и стига да нямате абсурдно голяма мрежа, това става почти мигновено.
