Существует ли простой алгоритм вычисления максимального вписанного круга в выпуклый многоугольник?
Я нашел несколько решений, но они слишком грязные.
4 ответа
Да. Чебышевский центр x* множества C является центром наибольшего шара, лежащего внутри C. [Boyd, p. 416] Когда C - выпуклое множество, то эта задача является выпуклой оптимизационной задачей.
Еще лучше, когда C является многогранником, тогда эта задача становится линейной программой.
Предположим, что многогранный многогранник C определяется набором линейных неравенств: ai^T x <= bi, для i в {1, 2, ..., m}. Тогда проблема становится
maximize R
such that ai^T x + R||a|| <= bi, i in {1, 2, ..., m}
R >= 0
где переменные минимизации R а также x, а также ||a|| евклидова норма a,
Возможно, эти "слишком грязные" решения - это то, что вы на самом деле ищете, а более простых нет?
Я могу предложить простое, но потенциально неточное решение, которое использует численный анализ. Предположим, у вас есть упругий шар, и вы его раздуваете, начиная с радиуса ноль. Если его центр находится не в том центре, который вы ищете, он будет двигаться, потому что стены будут "толкать" его в правильном направлении, пока он не достигнет точки, откуда он не сможет двигаться куда-либо еще. Я предполагаю, что для выпуклого многоугольника шар в конечном итоге переместится в точку, где он имеет максимальный радиус.
Вы можете написать программу, которая имитирует процесс инфляции по кругу. Начните с произвольной точки и "надувайте" круг, пока он не достигнет стены. Если вы продолжите раздувать его, он будет двигаться в одном из направлений, которые не приближают его к тем стенам, с которыми он уже сталкивается. Вы можете определить возможные пути его перемещения, нарисовав линии, параллельные стенам, через центр, в котором вы находитесь в данный момент.
В этом примере шар будет двигаться в одном из направлений, отмеченных зеленым:
http://coldattic.info/pic/522403726925.pngЗатем слегка передвиньте мяч в одном из этих направлений (возможно, вам лучше двигаться вдоль деления угла на угол) и повторите шаг. Если новый радиус будет меньше того, который у вас есть, отступите и уменьшите скорость его перемещения. Когда вам нужно сделать темп меньше, скажем, 1 дюйма, тогда вы нашли центр с точностью до 1 дюйма. (Если вы собираетесь рисовать его на экране, точность 0,5 пикселя было бы достаточно хорошо, я думаю).
Если вам достаточно неточного решения, я думаю, это достаточно просто.
Резюме: это не тривиально. Таким образом, очень маловероятно, что это не станет грязным. Но есть несколько слайдов для лекций, которые могут оказаться полезными.
Источник: http://www.eggheadcafe.com/software/aspnet/30304481/finding-the-maximum-inscribed-circle-in-c.aspx
Ваша проблема не тривиальна, и нет кода C#, который делает это прямо из коробки. Вам придется написать свой собственный. Я обнаружил, что проблема заинтриговала, и провел некоторое исследование, поэтому вот несколько подсказок, которые могут помочь.
Во-первых, вот ответ на "простом английском" с сайта mathforum.org:
http://mathforum.org/library/drmath/view/67030.html
Ответ ссылается на диаграммы Вороного как на методологию повышения эффективности процесса. При исследовании диаграмм Вороного в связи с проблемой "максимально пустой круг" (та же проблема, другое название) я наткнулся на эту информативную статью:
http://www.cosy.sbg.ac.at/~held/teaching/compgeo/slides/vd_slides.pdf
Он был написан Мартином Хельдом, профессором вычислительной геометрии в университете Зальцберга в Австрии. Дальнейшее исследование работ доктора Хелда дало пару хороших статей:
http://www.cosy.sbg.ac.at/~held/projects/vroni/vroni.html http://www.cosy.sbg.ac.at/~held/projects/triang/triang.html
Дальнейшие исследования Vornoi Diagrams дали следующий сайт:
Этот сайт содержит много информации, код на разных языках и ссылки на другие ресурсы.
И, наконец, вот URL-адрес Отдела математики и вычислительных наук Национального института стандартов и технологий (США), множество информации и ссылок по математике всех видов:
- HTH,
Кевин Спенсер Microsoft MVP
Самый большой вписанный круг (я предполагаю, что он уникален) пересекает некоторые грани тангенциально и может не пересекать другие. Давайте назовем лицо "релевантным", если его пересекает самый большой вписанный круг, и "несущественным" в противном случае.
Если ваш выпуклый многоугольник на самом деле является треугольником, то проблему можно решить, вычислив стимулятор треугольника, пересекая уголки биссектрисы. Это может показаться тривиальным случаем, но даже когда ваш выпуклый многоугольник сложен, вписанный круг всегда будет касаться как минимум к трем граням (доказательство? Кажется геометрически очевидным), и поэтому его центр можно рассчитать как стимул для трех релевантных граней. (вытянутый наружу, чтобы сделать треугольник, который описывает исходный многоугольник). Здесь мы предполагаем, что нет двух таких граней, параллельных. Если две параллельны, мы должны интерпретировать "биссектрису угла" двух параллельных линий, чтобы обозначить третью параллельную линию между ними.
Это сразу наводит на мысль о довольно ужасном алгоритме: рассмотрите все n-выберите-3 подмножества граней, найдите стимуляторы всех треугольников, как указано выше, и проверьте каждый круг на предмет наличия в исходном многоугольнике. Максимизируйте среди тех, которые являются законными. Но это кубический по русски, и мы можем сделать намного лучше.
Но вместо этого можно идентифицировать грани, которые не имеют отношения к фронту: если грань касается некоторой вписанной окружности, то существует область точек, ограниченных этой гранью и двумя угловыми биссектрисами в ее конечных точках, где должен находиться центр окружности. Если даже круг, центр которого находится на самом дальнем конце этой треугольной области, является "законным" (полностью содержится в многоугольнике), то само лицо не имеет значения и может быть удалено. Два лица, соприкасающиеся с ним, должны быть расширены за его пределы, чтобы они встретились.
Путем итеративного удаления граней, которые не имеют значения в этом смысле, вы сможете уменьшить многоугольник до треугольника или, возможно, трапеции, после чего проблема будет легко решена, и ее решение все еще будет лежать в исходном многоугольнике.