Ближайшая точка на вогнутой поверхности от точки
Учитывая объединение выпуклых объектов и точки p в этом объединении, как каждый находит самую близкую точку на (вогнутой) поверхности объединения от p?
Если это имеет значение я могу легко найти самую близкую точку на поверхности единственного выпуклого объекта, это - объединение нескольких, это дает мне проблемы.
Править: Я ужасно сожалею, я имел в виду объединение объектов а не пересечения :( Извинения всем, кто ответил.
EDIT2: вот маленькое изображение, описывающее любезность ситуации AakashM, самой близкой точки на поверхности от O, b является самой близкой точкой на поверхности B от O, и x является точкой, которую я на самом деле ищу (O == p).
Мои объекты не являются многоугольными объектами, но строками с радиусом (я думаю, что термин капсула иногда используется для этого, но я не знаю, принят ли этот термин универсально).
4 ответа
Там может быть более эффективным способом, но наивный подход будет просто найти ближайшую точку p на каждая поверхность , затем выберите один с наименьшим расстоянием. С p P находится внутри взаимного пересечения всех объектов, эта точка гарантирована на поверхности пересечения.
Я думаю, вам придется рассчитать ближайшие точки на поверхности все отдельные объекты (дает вам n точек), то проверьте на каждую точку, если его внутри все остальные Объекты (поэтому его часть поверхности пересечения ), а чем находить ближайшую к P .
Этот алгоритм использует тот факт, что точка находятся на поверхности пересечений n выпуклых объектов, если это на поверхности одного из этих объектов и Внутри Все остальные объекты (поверхность пересечения выполнена из небольших частей поверхностей пересеченных объектов ...)
Я не знаю инструмента и структуру данных, над которой вы работаете, но, например, в MatLab при пересечении N многоугольников, результатом является новым полигоном пересечения, и если вы можете легко Найдите ближайшую точку на поверхности одного выпуклого объекта, затем, если многоугольник пересечения вогнута, вы можете треугольствовать для получения ваших выпуклых объектов.
(для версии Union)
Каждая вогнутая точка объединения находится на пересечении границы два ваших объекта. Таким образом, вы можете просто вычислить все такие точки пересечения, проверить, находятся ли они на границе вашего объединения, и выбрать ближайшую к p.
Вам нужно больше, чем это, однако, как в следующей ситуации (объединение 2 прямоугольников)
+--------------------+
| |
+--------------------+
| p |
| |
| |
| |
| |
+--------------------+
Требуемый результат не является точкой пересечения границы, и это не ближайшая точка к p для любого прямоугольника по отдельности. . Я не знаю, как вести себя с этим делом.