Ответ 1
Возможно, вам стоит проверить (предупреждение в формате PDF! Также обратите внимание, что по какой-то причине порядок страниц обращается вспять) " Оптимальные алгоритмы для вычисления минимума Расстояние между двумя конечными планарными наборами" Туссен и Бхаттачарья:
В этой статье показано, что минимальное расстояние между двумя конечными плоских множеств, если [sic] n точек могут быть вычисляется в O (n log n) в худшем случае время работы и что это оптимально с постоянным коэффициентом. Кроме того, когда множества образуют выпуклый многоугольник, эта сложность может быть сведено к O (n).
Если два многоугольника пересекаются выпуклыми, возможно, вы также должны проверить (PDF-предупреждение! Опять-таки порядок страниц обращается вспять) " Оптимальный Алгоритм вычисления минимального расстояния между двумя пересекающимися выпуклыми многоугольниками" Туссена:
Пусть P = {p 1, p 2,..., p m} и Q = {q 1, q 2,..., q n} - два пересекающихся многоугольника, вершины которых заданы по их декартовым координатам в заказ. Оптимальный O (m + n) алгоритм представлен для вычисления минимальное эвклидовое расстояние между вершина p i в P и a вершина q j в Q.