Как найти самый большой круг между непересекающимися многоугольниками, заключенными в квадрат?
Пусть P1, .,,, Pk - набор попарно непересекающихся простых многоугольников с общим количеством ребер n, заключенных в данный квадрат. Найдите самый большой диск, который можно вписать в этот квадрат так, чтобы он не пересекался со всеми внутренностями многоугольников Pi.
думал об использовании диаграммы Вороного отрезков линии...
1 ответ
Рассмотрим поле расстояния d(x, y) на площади, которая определяет для каждой точки (x, y) расстояние до ближайшего полигона. Ваша цель - найти максимум этого поля расстояния.
Очень простой подход - дискретизировать поле расстояний на сетке и найти вершину с максимальным значением. Вы также можете разделить сетку вокруг точек-кандидатов.
Но вы также можете включить непрерывный шаг оптимизации. Для этого рассчитайте поле дискретизированного расстояния и используйте верхние вершины в качестве начальных чисел для непрерывной оптимизации. В этой оптимизации переместите точку так, чтобы расстояние увеличивалось до тех пор, пока вы не сможете больше двигаться. Это найдет локальные максимумы. При правильной инициализации один из этих максимумов, скорее всего, является глобальным максимумом.
Чтобы найти направление движения, найдите пересечения текущего диска со всеми многоугольниками. Если есть одно пересечение, движение в противоположном направлении определенно увеличит расстояние. Если есть больше пересечений, вы можете усреднить направления. Вы можете использовать предварительно определенную длину шага или оценку. Чтобы оценить длину шага, найдите расстояние до следующих пересечений (исключая уже найденные примитивы пересечения, а не целые полигоны), назовем это расстояние d_next, Вы можете безопасно двигаться (d_next - d_current) / 2 не вызывая нового пересечения. Там может быть умнее способ расчета длины шага.