Я знаю, как вычислить центроид многоугольника и его площадь, исходя из этого я могу рассчитать радиус круга с центром в центроиде, который охватывает 100% многоугольника: это расстояние от центроида до самой дальней вершины.
Мой вопрос: как найти радиус R круга, который охватывает X процентов круга (где X% составляет ‹ 100%)?
Вот несколько примеров геометрий, которые, я думаю, будут хорошими тестами: Геометрии L, Square, U и Star Test< /а>
Метод грубой силы, который у меня есть на данный момент, заключается в следующем:
1) Начните с радиуса R, равного половине размера, необходимого для охвата 100% полигона.
2) Аппроксимируйте круг 16-сторонним правильным шестиугольником (площадь = 97% круга того же радиуса)
3) Используйте один из методов отсечения (например, Weiler-Atherton), чтобы найти пересечение двух многоугольников.
4) Вычислить площадь многоугольника(ов) пересечения
5) Повторяйте значение радиуса R до тех пор, пока площадь пересечения, деленная на площадь многоугольника, не окажется в пределах E% от (1,0262 * X%), где E% — допустимая ошибка площади, а множитель 1,0262 учитывает разницу между используя круг и шестиугольник.
Сначала разложите многоугольник как набор треугольников с одной вершиной в центре тяжести и двумя другими, образующими ребро, с положительной или отрицательной ориентацией (в зависимости от ориентации ребра). Сумма алгебраических площадей треугольника будет равна площади многоугольника.
Затем рассмотрим площадь пересечения одиночного треугольника с окружностью растущего диаметра. Сначала он растет квадратично с коэффициентом, равным центральному углу, пока не встретится первая вершина. Затем площадь растет все медленнее и медленнее, пока не встретится вторая вершина, и не достигнет всей площади треугольника.
Добавляя эти функции для всех треугольников, вы построите глобальную кривую площади пересечения, которая определяется кусочно как функция расстояния между вершинами. Сначала вы определите, между какими вершинами функция достигает X% от общей площади. Тогда, зная аналитическое выражение участка кривой, вы найдете точное значение радиуса. Можно ли это сделать аналитически или численно, зависит от выражения хвоста площади треугольника.
