Ближайшая точка на вогнутой поверхности от точки

Question

Учитывая объединение выпуклых объектов и точку p внутри этого объединения, как найти ближайшую точку на (вогнутой) поверхности объединения из p ?

Для чего бы это ни стоило, я легко могу найти ближайшую точку на поверхности одного выпуклого объекта, это объединение нескольких, что доставляет мне проблемы.

РЕДАКТИРОВАТЬ: I 'Мне ужасно жаль, я имел в виду объединение объектов, а не пересечение :( Извинения всем, кто ответил.

EDIT2: Вот небольшое изображение, описывающее ситуацию любезно AakashM, является ближайшей точкой на поверхности A из O , b является ближайшей точкой на поверхности B из O и x - это точка, которую я на самом деле ищу ( O == p ).

Мои объекты - это не многоугольные объекты, а линии с радиусом (я думаю, что термин «капсула» иногда используется для этого, но я незнать, является ли этот термин общепринятым).

Answer 1

Возможно, существует более эффективный способ, но наивным подходом было бы просто найти ближайшую точку к p на каждой поверхности, а затем выбрать точку с наименьшим расстоянием. Поскольку p находится внутри взаимного пересечения всех объектов, эта точка гарантированно находится на поверхности пересечения.

Answer 2

(для версии Union)

Каждая вогнутая точка объединения находится на пересечении границы двух ваших объектов.Таким образом, вы можете просто вычислить все такие точки пересечения, проверить, находятся ли они на границе вашего объединения, и выбрать ближайший к р.

Однако вам нужно больше, чем, как в следующей ситуации (объединение2 прямоугольника)

+--------------------+
|                    |
+--------------------+
|         p          |
|                    |
|                    |
|                    |
|                    |
+--------------------+

Требуемый результат не является точкой пересечения границы и не является ближайшей точкой к p для каждого прямоугольника в отдельности.Я не уверен, как справиться с этим делом.

Answer 3

Я не знаю инструмент и структуру данных, над которыми вы работаете, но, например, в Matlab, когда вы пересекаете n многоугольников, результатом будет новый многоугольник пересечения, и если вы сможете легко найти ближайшую точку на поверхности одного выпуклого объекта, то, если многоугольник пересечения является вогнутым, вы можете триангулировать для получения ваших выпуклых объектов.

Answer 4

Полагаю, вам придется рассчитать ближайшие точки на поверхности всех отдельных объектов (дает вам n точек), а затем проверить для каждой точки, является ли ее внутри всех остальных объекты (таким образом, его часть поверхности пересечения ), а затем найти ближайший к p .

Этот алгоритм использует тот факт, что точка находится на поверхности пересечений n выпуклых объектов, если она на поверхности одного из этих объектов и внутри все остальные объекты (поверхность пересечения состоит из маленьких кусочков поверхностей пересекающихся объектов ...)