Какой самый быстрый способ найти "визуальный” центр многоугольника неправильной формы?
https://stackoverflow.com/questions/1203135
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Мне нужно найти точку, которая является визуальным центром многоугольника неправильной формы.Под визуальным центром я подразумеваю точку, которая визуально кажется находящейся в центре большой области многоугольника.Приложение предназначено для размещения метки внутри многоугольника.
Вот решение, которое использует внутреннюю буферизацию:
Если это необходимо использовать, то каков эффективный и быстрый способ найти буфер?Если следует использовать какой-либо другой способ, то какой именно?
Хорошим примером действительно жестких полигонов является гигантская толстая буква U (написанная Arial Black, Impact или каким-то подобным шрифтом).
Решение
Если вы можете преобразовать полигон в двоичное изображение, то вы можете использовать основу, существующую в области обработки изображений, например: Быстрый Скелетный алгоритм на блочно Представленных двоичных изображениях.
Но в общем случае это не совсем разумно из-за ошибок дискретизации и дополнительной работы.
Однако, возможно, вы сочтете это полезным:
- Прямой скелет простого многоугольника
- Определение скелета простого многоугольника за (почти) Линейное время
Редактировать:Возможно, вы хотите найти точку, которая является центром самого большого круга, содержащегося в многоугольнике.Это не обязательно всегда происходит в наблюдаемом центре, но в большинстве случаев, вероятно, дало бы ожидаемый результат, и только в слегка патологических случаях что-то совершенно не так.
Другие советы
Я нашел очень хорошее решение для этого в MapBox, которое называется Polylabel . Полный исходный код также доступен на их Github .
По сути, он пытается найти визуальный центр многоугольника, как сказал Т. Остин.
Некоторые детали предполагают, что это может быть практическим решением:
К сожалению, вычисление [идеального решения] является сложным и медленно. Опубликованные решения проблемы требуют либо Ограниченная триангуляция Делоне или вычисление прямого скелета как этапы предварительной обработки - & # 8202; & # 8202; оба шага медленные и подвержены ошибкам.
Для нашего случая использования нам не нужно точное решение - & # 8202; & # 8202; & # 8217; мы готовы обменять некоторую точность, чтобы получить больше скорости. Когда мы размещаем ярлык на карта, для нее более важно вычислить ее за миллисекунды, чем быть математически совершенным.
Краткое примечание об использовании. Исходный код прекрасно работает для Javascript из коробки, однако, если вы намереваетесь использовать его с «нормальной» полигон, тогда вы должны обернуть его в пустой массив, так как функции здесь принимают GeoJSONPolygons , а не обычные полигоны, т. е.
var myPolygon = [[x1, y1], [x2, y2], [x3, y3]];
var center = polylabel([myPolygon]);
Вы изучали формулу центроида?
Как насчет:
Если центроид многоугольника находится внутри многоугольника, используйте его, иначе:
1) Протяните линию от центроида через многоугольник, разделяя многоугольник на две половины равной площади
2) «Визуальный центр»; это точка на полпути между ближайшей точкой, где линия касается периметра, и следующей точкой, пересекающей периметр в направлении, отходящем от центроида
Вот несколько фотографий, чтобы проиллюстрировать это:
Вычислите центральную позицию (x, y) каждого ребра многоугольника. Вы можете сделать это, найдя разницу между положениями концов каждого края. Возьмите среднее значение каждого центра в каждом измерении. Это будет центр многоугольника.
Метод центроида уже предлагался несколько раз. Я думаю, что это отличный ресурс, который описывает процесс (и многие другие полезные трюки с полигонами) очень интуитивно:
http://paulbourke.net/geometry/polygonmesh/centroid.pdf
Кроме того, для размещения простой метки пользовательского интерфейса может быть достаточно просто вычислить ограничивающий прямоугольник многоугольника (прямоугольник, определяемый самой низкой и самой высокой координатами x и y любой вершины в многоугольнике) и получить его центр по адресу:
{
x = min_x + (max_x - min_x)/2,
y = min_y + (max_y - min_y)/2
}
Это немного быстрее, чем вычисление центроида, что может быть важно для реального времени или встроенного приложения.
Также обратите внимание, что если ваши многоугольники статичны (они не меняют форму), вы можете оптимизировать, сохранив результат вычисления центра / центра масс BB (например, относительно первой вершины многоугольника) в структура данных многоугольника.
Я не говорю, что это самый быстрый, но он даст вам точку внутри многоугольника. Рассчитайте прямой скелет . Точка, которую вы ищете, находится на этом скелете. Например, вы можете выбрать тот, который имеет самое короткое нормальное расстояние до центра ограничительной рамки.
Как насчет поиска " вписанной окружности " многоугольника (самый большой круг, который умещается внутри него), а затем центрировать метку в центре этого? Вот несколько ссылок, с которых можно начать:
http://www.mathopenref.com/polygonincircle.html
https://nrich.maths.org/discus/messages/145082/ 144373.html? 1219439473
Скорее всего, это не будет работать идеально на каждом полигоне; у многоугольника, который выглядел как C, была бы метка в несколько непредсказуемом месте. Но преимущество заключается в том, что метка всегда будет перекрывать сплошную часть многоугольника.
Если я понимаю смысл статьи, на которую вы ссылались (кстати, довольно интересная проблема), это "внутренняя буферизация" Техника в некотором роде аналогична моделированию рассматриваемой формы из кусочка сахара, который растворяется кислотой с краев. (Например, при увеличении буферного расстояния остается меньше исходной формы). Последний оставшийся бит является идеальным местом для разместить ярлык.
Как это сделать в алгоритме, к сожалению, мне не очень понятно ....
Я думаю, что если вы разбили многоугольник обратно на его вершины, а затем применили функцию для нахождения наибольшего выпуклого корпуса, а затем нашли центр на этом выпуклом корпусе, он бы близко совпадал с "видимым". центр.
Поиск наибольшего выпуклого корпуса с учетом вершин: Посмотрите под абзацем Простой многоугольник.
Усредните вершины выпуклой оболочки, чтобы найти центр.
Не могли бы вы поместить метку в наивном центре (возможно, ограничительной рамки), а затем переместить ее, основываясь на пересечениях локальных краев многоугольника и BB метки? Перемещение по нормали пересекающихся ребер, и, если несколько ребер пересекаются, суммировать их нормали для движения?
Просто угадай здесь; в такой ситуации я, вероятно, попытался бы решить итеративно, если производительность не слишком важна.
Сейчас не так много времени, чтобы разработать или проверить это, но я постараюсь сделать больше, когда у меня будет шанс.
Используйте центроиды в качестве основного метода. Проверьте, находится ли центроид внутри многоугольника; если нет, проведите линию от до ближайшей точки и на другой стороне многоугольника. В средней части сечения этой линии, расположенного внутри многоугольника, разместите метку.
Поскольку точка, ближайшая к центроиду, вероятно, ограничивает довольно большую область, я думаю, что это может дать результаты, аналогичные вкраплениям Киралессы. Конечно, это может привести в бешенство, если у вас есть многоугольник с отверстиями. В этом случае, окружности, вероятно, будут намного лучше. С другой стороны, по умолчанию используется метод центроида (быстрый?) Для типичных случаев.
Эта проблема, вероятно, будет аналогична поиску «центра масс». при условии равномерной плотности.
РЕДАКТИРОВАТЬ: этот метод не будет работать, если многоугольник имеет "отверстия"
Вы можете использовать метод Center of Mass (или Center of Gravity), который используется в гражданском строительстве, вот полезная ссылка из Википедии:
