Найти радиус наибольшей вписанной в полигон окружности

[badger]

Как можно подойти к решению такой задачи ? В полигональной шейп теме с n числом полигонов произвольной формы для каждого полигона нужно найти радиус вписанной в него наибольшей окружности. Под таковой окружностью понимается окружность, которая касается полигона в двух или более точках. (Любая окружность с бОльшим радиусом будет пересекать стороны полигона).
Если бы кто-то мог наметить возможные ходы решения..
Софт – думаю об ArcGIS как наиболее универсальном (может быть есть готовый скрипт или даже инструмент) или любой другой.

[gamm]

для вектора задача в общем случае решается крайне тяжело, и инструмент вряд ли есть. Для растра задача решается довольно просто: граница полигона сносится на растр нужной детальности, и строится дистанционное преобразование. Точка с максимальным расстоянием внутри полигона есть есть центр искомой вписанной окружности, а само расстояние - ее радиус.

Насчет Арки не в курсе, но в R это можно сделать без проблем, в пакете raster - задачка уровня задания для студентов на пол-занятия, нужно будет задать, спасибо за идею .

[trir]

http://doc.cgal.org/latest/Straight_ske ... index.html

[badger]

Для растра задача решается довольно просто: граница полигона сносится на растр нужной детальности, и строится дистанционное преобразование. Точка с максимальным расстоянием внутри полигона есть есть центр искомой вписанной окружности, а само расстояние - ее радиус. .

Дистанционное преобразование - имеется в виду такого рода операция:
Положили контур полигона на растр. Нужно найти точку максимально удаленную от всех ячеек, принадлежащих к границам контура? Как-то так?
Звучит просто. Может быть есть решение задачи в растре в ArcGIS, QGIS, поищу.

http://doc.cgal.org/latest/Straight_ske ... index.html

Вы не могли бы пояснить, какой алгоритм действий возможен для решения задачи в CGAL. С ее помощью можно решить задачу в векторе и перекинуть это в ГИС?

[trir]

этот алгоритм даёт линии равно удалённые от граней многоугольника, центр вписанной окружности находится на этих линиях, думаю в центре самой удалённой

[Иван Стрельников]

Могу предложить направление для решения в векторе и, возможно, в ArcGIS.

Здесь есть плагин для построения диаграмм Вороного на основе сегментов линий.

Примерное решение:
1. Разбить многоугольник на отрезки.
2. Построить по ним диаграмму Вороного.
3. Для вершин диаграммы построить таблицы расстояний до граней многоугольника.
4. Выбрать вершину с самым большим минимальным расстоянием до граней -- это и будет центр окружности, а минимальное расстояние до грани = радиус окружности.

Сомневаюсь, что это легко реализовать в ArcGIS -- просто, как возможное направление.

Может оказаться, что две или более точек имеют максимальное расстояние до граней (например в случае параллелепипеда), тогда Ваша задача имеет множество решений.

P.S. кажется ArcGIS умеет находить расстояние до ближайшего объекта (не помню на счет от точки до линии), если да, то задача упрощается в разы.

[badger]

Эта задача имеет разные решения. И здесь было предложено их несколько, и еще на их спектр можно выйти по ссылкам с моего вопроса:
http://gis.stackexchange.com/questions/ ... -i-e-the-r


Для ленивых самое простое решение - дает ET GeoWizards
Объяснение здесь (второй ответ)
http://gis.stackexchange.com/questions/ ... 030#148030)

В новой теме строит окружности для всех полигонов, в атрибутивной таблице выдает радиус и центр окружности.

Софт ET_GeoWizards платный, однако у меня посчитал (как в приложенном образце) и в демо версии. Ограничение в числе объектов за раз обработки (вроде бы до 100 или 200 нужно уточнить)

Не понято что он делает в случае наличия нескольких возможных окружностей (можно это проверить) и есть ли другие ограчения.

Но, тем не менее, готовое решение для ArcGIS сущесвует.

И третьим ответом по последней ссылке - решение в QGIS, также выглядит обещающим.