Найдите самую длинную прямую линию между двумя точками на поверхности многоугольника

8

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

Есть ли общий алгоритм для этого?

В моем случае меня интересует 2D. Мои фигуры - это опухоли на медицинских снимках. Таким образом, мы также можем предположить: 1 центроид всегда находится внутри многоугольника. 2 высокая плотность вершин, т.е. следующая вершина всегда близка к предыдущей.

mathematics computational-geometry polygon jiggunjer
источник
1
Есть вращающиеся суппорты, но это работает только для выпуклых многоугольников. В противном случае вы можете использовать его в качестве основы для решения грубой силы.
фрик с трещоткой
3
Хорошо, если O (n ^ 2) не проблема, тогда протестируйте все пары точек
joojaa
2
На самом деле это немного сложнее: представьте себе 2 комнаты, соединенные узким коридором. Наибольший диаметр заканчивается на стенах в разных комнатах и ​​не заканчивается ни в одной точке.
фрик с трещоткой
1
Вы ищете алгоритм, который работает в самом общем случае или он может быть ограничен, например, 2D случаем? Это может быть легче решить с помощью дополнительной информации или ограничений относительно ввода. Вы используете слово многоугольник, которое может указывать только на 2D, а также связанный с вами вопрос предлагает случай 2D. Кроме того, достаточно ли учитывать расстояния между вершинами и вершинами или вам нужны правильные результаты для случаев, подобных описанному в его комментарии ?
Нерон
2
Кроме того, меня беспокоит форма С, которая имеет очень узкую толщину, но большую открытую внутреннюю часть; и так большой радиус кривизны. Его диаметр (как вы его определили) был бы очень маленьким, потому что это было бы только короткое замыкание, которое следует за изгибом C. Тем не менее, узелок рака размером с внутренний размер был бы весьма проблематичным. Так что, возможно, вы хотите вычислить диаметр выпуклой оболочки.
Wyck

Ответы:

1

У меня нет точного ответа на это, поскольку ответ далеко не тривиален. Я бы посоветовал вам взглянуть на вычислительную геометрию, так как это явно проблема видимости - я думаю, что решение уже существует. Моя собственная идея заключается в следующем: для каждого отрезка линии в многоугольнике найдите видимые части других отрезков, а затем выберите пару точек, которые находятся дальше друг от друга. Вдохновенная ссылка: Википедия о «многоугольнике видимости» .

за
источник