Есть задача определения расстояния* между двумя плоскими многоугольниками в пространстве . (плоскости произвольные).
Без потери интереса к реализации можно ограничиться выпуклыми многоугольниками.
Я пока не придумал ничего лучше, чем:
1) Измерить попарно расстояние между ребер.
2) Измерить расстояние от всех вершин до другого многоугольника.
3) Проверить, не пересекают ли ребра другой многоугольник (расстояние 0).
Соответственно, наименьшее из них и будет искомым.
Есть ли какие-то принуипиально более интересные алгоритмы?
Также интересны эффективные критерии грубой нижней оценки.
То есть, если меня интересуют только близкие расстояния (<D), при этом вероятность такого события < X (например, 5 %),
то я готов сначала провернуть нечто, в дальнейшем бесполезное, если оно, например, на 20% быстрее выяснит, что расстояние заведомо больше D.
Спасибо за Ваши ссылки и идеи.
*формально, речь о наименьшем расстоянии между произвольной парой точек, принаждлежащих этим мноугольникам.
