Есть задача определения расстояния* между двумя плоскими многоугольниками в пространстве . (плоскости произвольные).
Без потери интереса к реализации можно ограничиться выпуклыми многоугольниками.
Я пока не придумал ничего лучше, чем:
1) Измерить попарно расстояние между ребер.
2) Измерить расстояние от всех вершин до другого многоугольника.
3) Проверить, не пересекают ли ребра другой многоугольник (расстояние 0).
Соответственно, наименьшее из них и будет искомым.
Есть ли какие-то принуипиально более интересные алгоритмы?
Также интересны эффективные критерии грубой нижней оценки.
То есть, если меня интересуют только близкие расстояния (<D), при этом вероятность такого события < X (например, 5 %),
то я готов сначала провернуть нечто, в дальнейшем бесполезное, если оно, например, на 20% быстрее выяснит, что расстояние заведомо больше D.
Спасибо за Ваши ссылки и идеи.
*формально, речь о наименьшем расстоянии между произвольной парой точек, принаждлежащих этим мноугольникам.
Ты не упомянул об отбрасывании по минимальному расстоянию между охватывающими прямоугольниками.
И тест на пересечение, я надеюсь не порёберная проверка.
А так, для выпуклых, наверное только полным перебором пар вершин...
Грубейшая оценка расстояния снизу:
— вокруг многоугольника описываем окружность (как получится);
— находим расстояние между центрами окружностей искомых многоугольников, вычитаем радиусы (как бы имеем дело с описывающими сферами).
(для нахождения описывающей окружности можно, например, взять за ее диаметр отрезок между наиболее удаленными вершинами многоугольника)
Более тонкая оценка:
— вычитаем не радиус окружности, а проекцию его на линию, проходящую через центры (для каждого прямоугольника нужно знать нормаль плоскости)
Еще более тонкая:
— переходим в (ортонормированную) систему координат, в которой OXY совпадает с плоскостью первого многоугольника
— находим проекцию второго многоугольника на эту плоскость
— находим расстояние Df между проекцией и первым многоугольником на плоскости, а также наименьшее расстояние H до плоскости
— D >= sqrt(Df^2 + H^2)
(вместо многоугольника можно рассмотреть описывающую окружность)
Здравствуйте, wvk.
Спасибо за отклик.
wvk>Ты не упомянул об отбрасывании по минимальному расстоянию между охватывающими прямоугольниками.
Да, за истекшее время я уже нашел и реализовал такой критерий. Кстати, точнее — охватывающие параллелипипеды (у меня — 3D).
wvk>И тест на пересечение, я надеюсь не порёберная проверка.
С этого места, пожалуйста, подробнее?
Единственный окончательный критерий того, что они пересекаются, который я на данный момент осознал, такой: какое-либо ребро пересекает внутренность другого многоугольника. Вы знаете лучше? Подскажите, пожалуйста.
С другой стороны, я использую дополнительные проверки, которые во многих случаях "говорят", что они заведомо не пересекаются.
wvk>А так, для выпуклых, наверное только полным перебором пар вершин...
И ребер, как я уже писал.
И для невыпуклых, мне кажется, тут ничего не меняется.
Здравствуйте, Кодт, спасибо за идеи:
К>Грубейшая оценка расстояния снизу: К>- вокруг многоугольника описываем окружность (как получится); К>- находим расстояние между центрами окружностей искомых многоугольников, вычитаем радиусы (как бы имеем дело с описывающими сферами). К>(для нахождения описывающей окружности можно, например, взять за ее диаметр отрезок между наиболее удаленными вершинами многоугольника)
Это, все же, на порядок сложней описывающего параллелипипида, при приблизительно той же эффективности.
К>Более тонкая оценка: К>- вычитаем не радиус окружности, а проекцию его на линию, проходящую через центры (для каждого прямоугольника нужно знать нормаль плоскости)
К>Еще более тонкая: К>- переходим в (ортонормированную) систему координат, в которой OXY совпадает с плоскостью первого многоугольника К>- находим проекцию второго многоугольника на эту плоскость К>- находим расстояние Df между проекцией и первым многоугольником на плоскости, а также наименьшее расстояние H до плоскости К>- D >= sqrt(Df^2 + H^2) К>(вместо многоугольника можно рассмотреть описывающую окружность)
А вот это уже по выч. мощности близко к точному расчету расстояния.
Здравствуйте, Croc, Вы писали:
К>>Грубейшая оценка расстояния снизу: К>>- находим расстояние между центрами окружностей искомых многоугольников, вычитаем радиусы (как бы имеем дело с описывающими сферами).
C>Это, все же, на порядок сложней описывающего параллелипипида, при приблизительно той же эффективности.
Я исходил из того, что если нужно находить расстояния "каждый с каждым", то можно предварительно найти центры и радиусы (O(N*V), N — число многоугольников, V — число вершин), а затем быстро-быстро...
Хотя с параллелепипедами будет быстрее... Но искать расстояние между параллелепипедами — более сложная задача; впрочем, можно сделать объединение подходов:
— центр параллелепипеда находим элементарно
— радиус = половине макс.габарита
К>>Еще более тонкая: К>>- переходим в (ортонормированную) систему координат, в которой OXY совпадает с плоскостью первого многоугольника К>>- находим проекцию второго многоугольника на эту плоскость К>>- находим расстояние Df между проекцией и первым многоугольником на плоскости, а также наименьшее расстояние H до плоскости К>>- D >= sqrt(Df^2 + H^2) К>>(вместо многоугольника можно рассмотреть описывающую окружность)
C>А вот это уже по выч. мощности близко к точному расчету расстояния.
Но опять же, если мы для каждого многоугольника проведем предварительную работу по нахождению нормали его плоскости...
Между прочим, гарантировать что многоугольник плоский можно только для треугольников.
Ты это как-то фиксируешь?
Здравствуйте, Croc, Вы писали:
C>Здравствуйте, wvk. C>Спасибо за отклик.
wvk>>Ты не упомянул об отбрасывании по минимальному расстоянию между охватывающими прямоугольниками.
C>Да, за истекшее время я уже нашел и реализовал такой критерий. Кстати, точнее — охватывающие параллелипипеды (у меня — 3D).
Имелись в виду прямоугольники с рёбрами параллельными линии пересечения плоскостей
(если конечно плоскости не параллельны
это несколько более точный тест, но и чуть более сложный соответственно
wvk>>И тест на пересечение, я надеюсь не порёберная проверка. C>С этого места, пожалуйста, подробнее? C>Единственный окончательный критерий того, что они пересекаются, который я на данный момент осознал, такой: какое-либо ребро пересекает внутренность другого многоугольника. Вы знаете лучше? Подскажите, пожалуйста.
Очевидно они могут пересекаться только по линии пересечения плоскостей
несложно для каждого найти пересечение с этой линией, и сравнивать уже их.
Здравствуйте, wvk, Вы писали:
wvk>>>И тест на пересечение, я надеюсь не порёберная проверка.
... wvk>Очевидно они могут пересекаться только по линии пересечения плоскостей wvk>несложно для каждого найти пересечение с этой линией, и сравнивать уже их.
Да, кстати, я пока все еще вожусь с невыпуклыми Пересечения получатся многосвязанные ...
А сейчас я сначала проверяю, пересекает ли ребро плоскость, и если да, то тогда уже смотрю, оно внутри или снаружи.
Думаю, что вычислительно это сравнимо, хотя из обоих подходов можно сварить что-то более шустрое.
К>Я исходил из того, что если нужно находить расстояния "каждый с каждым", то можно предварительно найти центры и радиусы (O(N*V), N — число многоугольников, V — число вершин), а затем быстро-быстро... К>Хотя с параллелепипедами будет быстрее... Но искать расстояние между параллелепипедами — более сложная задача;
Ну, не скажи.
Ведь точность тут не нужна (это же критерий грубейшей оценки снизу), вот и достаточно проверить растояния покординатно. Получается весьма быстро.
К>Между прочим, гарантировать что многоугольник плоский можно только для треугольников. К>Ты это как-то фиксируешь?
Перекуём баги на фичи!
