Я нашел некоторые решения, но они слишком грязные.
Существует ли простой алгоритм вычисления максимальной вписанной окружности в выпуклый многоугольник?
Ответ 1
Да. Чебышевский центр, x *, множества C является центром наибольшего шара, лежащим внутри C. [ Бойд, с. 416]. Если C - выпуклое множество, то эта задача является выпуклой задачей оптимизации.
Еще лучше, когда C - многогранник, тогда эта задача становится линейной программой.
Предположим, что m-сторонний многогранник C определяется набором линейных неравенств: ai ^ T x <= bi, для я в {1, 2,..., m}. Тогда проблема становится
maximize R
such that ai^T x + R||a|| <= bi, i in {1, 2, ..., m}
R >= 0
где переменными минимизации являются R и x, а ||a|| - евклидова норма a.
Ответ 2
Резюме: Это не тривиально. Поэтому маловероятно, что он не станет беспорядочным. Но есть некоторые слайды лекций, которые могут оказаться полезными.
Источник: http://www.eggheadcafe.com/software/aspnet/30304481/finding-the-maximum-inscribed-circle-in-c.aspx
Ваша проблема не тривиальна, и там не является кодом С#, который делает это прямо из коробки. Вам придется писать твой собственный. Я нашел проблему интригуя, и сделал некоторые исследования, поэтому вот несколько подсказок, которые могут помочь.
Во-первых, здесь ответ на "простой Английский" с сайта 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
Дальнейшие исследования в диаграммах Ворни дал следующий сайт:
На этом сайте много информации, код на разных языках и ссылки к другим ресурсам.
Наконец, вот URL-адрес Математика и вычислительные науки Отдел Национального института Стандарты и технологии (США), богатство информации и ссылок относительно математики всех видов:
- HTH,
Кевин Спенсер Microsoft MVP
Ответ 3
Возможно, эти "слишком грязные" решения - это то, что вы на самом деле ищете, а более простых нет?
Я могу предложить простое, но потенциально неточное решение, которое использует численный анализ. Предположим, у вас есть упругий шар, и вы его раздуваете, начиная с радиуса ноль. Если его центр находится не в том центре, который вы ищете, он будет двигаться, потому что стены будут "толкать" его в правильном направлении, пока он не достигнет точки, откуда он не сможет двигаться куда-либо еще. Я предполагаю, что для выпуклого многоangularьника шар в конечном итоге переместится в точку, где он имеет максимальный радиус.
Вы можете написать программу, которая имитирует процесс инфляции по кругу. Начните с произвольной точки и "надувайте" круг, пока он не достигнет стены. Если вы продолжите раздувать его, он будет двигаться в одном из направлений, которые не приближают его к тем стенам, с которыми он уже сталкивается. Вы можете определить возможные пути его перемещения, нарисовав линии, параллельные стенам, через центр, в котором вы находитесь.
В этом примере шар будет двигаться в одном из направлений, отмеченных зеленым:
(источник: coldattic.info)
Затем слегка переместите свой шар в одном из этих направлений (возможно, вам лучше двигаться вдоль деления угла на angular) и повторите шаг. Если новый радиус будет меньше того, который у вас есть, отступите и уменьшите скорость его перемещения. Когда вам нужно сделать темп меньше, скажем, 1 дюйма, тогда вы нашли центр с точностью до 1 дюйма. (Если вы собираетесь рисовать его на экране, точность 0,5 пикселя было бы достаточно хорошо, я думаю).
Если вам достаточно неточного решения, я думаю, это достаточно просто.
Ответ 4
Самый большой вписанный круг (я предполагаю, что он уникален) пересечет некоторые грани тангенциально и может не пересекать других. Позвольте называть лицо "релевантным", если наибольшая вписанная окружность пересекает его, и "нерелевантно" в противном случае.
Если ваш выпуклый многоугольник на самом деле является треугольником, то проблема может быть решена путем вычисления треугольника инсертера путем пересечения угловых биссектрис. Это может показаться тривиальным, но даже если ваш выпуклый многоугольник сложный, вписанная окружность всегда будет касаться как минимум трех граней (доказательство? кажется геометрически очевидным), и поэтому его центр можно вычислить как центр трех соответствующих граней (протянутый наружу, чтобы создать треугольник, который ограничивает оригинал полигон). Здесь мы предполагаем, что две такие грани параллельны. Если два параллельны, мы должны интерпретировать "биссектрису угла" двух параллельных линий, чтобы означать, что третья параллельная линия между ними.
Это сразу предлагает довольно страшный алгоритм: рассмотрите все n-select-3 подмножества граней, найдите стимулы всех треугольников, как указано выше, и проверьте каждый круг для сдерживания в исходном многоугольнике. Максимизируйтесь среди тех, кто является законным. Но это кубический по n, и мы можем сделать намного лучше.
Но вместо этого возможно определить лица, которые не имеют значения заранее: если грань касательна к некоторой вписанной окружности, то есть область точек, ограниченных этой гранью, и двумя угловыми биссектрисами на своих концах, где центр окружности должен лежать. Если даже круг, центр которого лежит в самом дальнем конце треугольной области, является "законным" (полностью содержащимся в многоугольнике), то само лицо не имеет значения и может быть удалено. Два лица, прикоснувшиеся к нему, должны быть расширены за его пределами, чтобы они встретились.
Итеративно удаляя лица, которые в этом смысле неактуальны, вы должны иметь возможность уменьшить многоугольник к треугольнику или, возможно, трапеция, в этот момент проблема будет легко решена, и ее решение по-прежнему будет находиться в исходном многоугольнике.