Какой самый быстрый способ найти «визуальный» центр многоугольника неправильной формы?
Мне нужно найти точку, которая является визуальным центром многоугольника неправильной формы. Под визуальным центром я подразумеваю точку, которая визуально находится в центре большой области многоугольника. Приложение должно поместить метку внутри многоугольника.
Вот решение, которое использует внутреннюю буферизацию:
Если это нужно использовать, каков эффективный и быстрый способ найти буфер? Если какой-либо другой путь должен быть использован, что это за путь?
Хорошим примером действительно жестких многоугольников является гигантская буква U (написанная Arial Black или Impact или другим подобным шрифтом).
12 ответов
Я нашел очень хорошее решение для этого в MapBox, которое называется Polylabel . Полный исходный код также доступен на их Github .
По сути, он пытается найти визуальный центр многоугольника, как сказал Т. Остин.
Некоторые детали предполагают, что это может быть практическим решением:
К сожалению, вычисление [идеального решения] является сложным и медленно. Опубликованные решения проблемы требуют либо Ограниченная триангуляция Делоне или вычисление прямого скелета как этапы предварительной обработки — оба из которых медленные и подвержены ошибкам.
В нашем случае нам не нужно точное решение — мы готовы обменять некоторую точность, чтобы получить больше скорости Когда мы размещаем ярлык на карта, более важно, чтобы она была вычислена в миллисекундах, чем быть математически совершенным.
Краткое примечание об использовании. Исходный код прекрасно работает для Javascript из коробки, однако, если вы собираетесь использовать его с «нормальным» многоугольником, вам следует заключить его в пустой массив, так как функции здесь принимают GeoJSONPolygons , а не нормальные полигоны, т.е.
Вы изучали формулу центроида?
Если центроид многоугольника находится внутри многоугольника, используйте его, иначе:
1) Протяните линию от центроида через многоугольник, разделяя многоугольник на две половины равной площади
2) «Визуальный центр» — это точка на полпути между ближайшей точкой, где линия касается периметра, и следующей точкой, пересекающей периметр в направлении, удаляющемся от центроида
Вот несколько фотографий, чтобы проиллюстрировать это:
Вычислите центральную позицию (x, y) каждого ребра многоугольника. Вы можете сделать это, найдя разницу между положениями концов каждого края. Возьмите среднее значение каждого центра в каждом измерении. Это будет центр многоугольника.
Я не говорю, что это самый быстрый, но он даст вам точку внутри многоугольника. Рассчитайте прямой скелет . Точка, которую вы ищете, находится на этом скелете. Например, вы можете выбрать тот, который имеет наименьшее нормальное расстояние до центра ограничительной рамки.
Как насчет нахождения «вписанной окружности» многоугольника (самого большого круга, который в нем помещается), а затем центрирования метки в центре этого? Вот несколько ссылок, с которых можно начать:
Скорее всего, это не будет работать идеально на каждом полигоне; у многоугольника, который выглядел как C, была бы метка в несколько непредсказуемом месте. Но преимущество заключается в том, что метка всегда будет перекрывать сплошную часть многоугольника.
Если я понимаю смысл статьи, на которую вы ссылались (кстати, довольно интересная проблема), эта техника «внутренней буферизации» в некоторой степени аналогична моделированию рассматриваемой формы из куска сахара, который растворяется кислотой края в. (например, при увеличении буферного расстояния остается меньше исходной формы) Последний оставшийся бит является идеальным местом для размещения метки.
Как это сделать в алгоритме, к сожалению, мне не очень понятно .
Я думаю, что если вы разбили многоугольник обратно на его вершины, а затем применили функцию для нахождения наибольшего выпуклого корпуса, а затем нашли центр на этом выпуклом корпусе, он бы близко совпадал с «кажущимся» центром.
Поиск наибольшего выпуклого корпуса с учетом вершин: посмотрите под абзацем Простой многоугольник.
Усредните вершины выпуклой оболочки, чтобы найти центр.
Не могли бы вы поместить метку в наивном центре (возможно, ограничительной рамки), а затем переместить ее на основе пересечений локальных ребер многоугольника и BB метки? Перемещение по нормали пересекающихся ребер, и, если несколько ребер пересекаются, суммировать их нормали для движения?
Просто угадай здесь; в такой ситуации я, вероятно, попытался бы решить итеративно, если производительность не слишком важна.
Сейчас не так много времени, чтобы разработать или проверить это, но я постараюсь сделать больше, когда у меня будет шанс.
Используйте центроиды в качестве основного метода. Проверьте, находится ли центроид внутри многоугольника; если нет, проведите линию от до ближайшей точки и на другой стороне многоугольника. В средней части сечения этой линии, расположенного внутри многоугольника, разместите метку.
Поскольку точка, ближайшая к центроиду, скорее всего, ограничивает довольно большую область, я думаю, что это может дать результаты, аналогичные вкраплениям Киралессы. Конечно, это может привести в бешенство, если у вас есть многоугольник с отверстиями. В этом случае, окружности, вероятно, будут намного лучше. С другой стороны, по умолчанию используется метод центроида (быстрый?) Для типичных случаев.
Эта проблема, вероятно, была бы аналогична нахождению «центра масс» в предположении равномерной плотности.
РЕДАКТИРОВАТЬ: этот метод не будет работать, если у многоугольника есть «дыры»
Вы можете использовать метод Center of Mass (или Center of Gravity), который используется в гражданском строительстве, вот полезная ссылка из Википедии:
Как найти центр многоугольника
Понятие «центр тяжести многоугольника» можно интерпретировать тремя различными способами:
- Масса находится только в вершинах, причем каждая вершина «весит» одинаково
- Масса равномерно распределена по границе многоугольника
- Масса равномерно распределена по области, ограниченной многоугольником.
Рассмотрим все три интерпретации в порядке возрастания сложности алгоритма.
1. Масса находится только в вершинах, причем каждая вершина весит одинаково
В этом случае координаты центра тяжести выражаются по формулам:
Таким образом для нашего частного случая имеем:
2. Масса равномерно распределена по границе многоугольника
В этом случае масса ребра пропорциональна его длине. Таким образом каждое ребро мы можем заменить на точечную массу (пропорциональную длине ребра). Затем применяя те же формулы для определения центра тяжести получаем:
Ниже представлена программа, реализующая описанный алгоритм:
3. Масса равномерно распределена по области, ограниченной многоугольником.
Этот случай уже не является столь тривиальным, как два предыдущих. Для построения алгоритма понадобится следующий факт:
Предложение 1
Пусть фигура Ф есть объединение двух других фигур Ф1 и Ф2 (пересекающихся только по границе).
Тогда центр тяжести фигуры Ф выражается так:
(Это утверждение очевидно следует из определения центра тяжести произвольной фигуры и свойства аддитивности интеграла)
Кроме того для треугольника центр тяжести определяется так:
Разобьем наш многоугольник на треугольники. Для каждого треугольника найдем его центр тяжести (Xci, Yci) и площадь (Si). После этого, согласно Предложению 1, координаты центра тяжести многоугольника можно найти следующим образом:
Остается вопрос, как разбить многоугольник на треугольники. Если многоугольник выпуклый, а вершины перечислены в порядке обхода по или против часовой стрелки, то достаточно просто найти одну точку внутри многоугольника (Xm,Ym), а затем разбить многоугольник на N следующих треугольников:
Если же многоугольник выпуклый, но вершины перечислены не в порядке обхода, то их придется упорядочить. Сделать это можно, например, отсортировав вершины по углу между положительной полуосью ОХ и вектором (Xi-Xm, Yi-Ym).
Невыпуклый многоугольник всегда можно разбить на несколько выпуклых. А затем, применив описанный алгоритм для каждой выпуклой части, и используя Предложение 1, найти центр тяжести всего многоугольника. Задача о разбиении произвольного многоугольника на выпуклые части является самостоятельной задачей, которая рассмотрена в соответствующем разделе. Поэтому представленная ниже реализация алгоритма работает только для выпуклых многоугольников.
Ниже представлен пример реализации описанного алгоритма на языке С для нахождения центра тяжести выпуклого многоугольника, вершины которого перечислены в порядке обхода по или против часовой стрелки:
Алгоритмы поиска объема и центра масс многогранника
Наверное, все знают этот алгоритм, но от меня «власти скрывали». Нашел его словесное описание на третьей странице поисковика в архиве автопереводов англоязычного форума. Мне кажется, его подробное описание (и с кодом) достойно хабростатьи.
Итак, например вам надо генерировать мобов для игрушки и где-то в процессе отсеивать тех, кто не стоит на ногах. Для этого нужно найти центр масс моба (а это почти то же самое, что найти его объем) и убедиться, что он находится где-то над ногами моба.
Моб — это многогранник, для простоты считаем, что многогранник состоит только из треугольников (в алгоритме внутри сидит формула площади Гаусса, так что можно расширить его для любого многогранника, но зачем. ). Кроме того, многогранник должен не иметь самопересечений и ограничивать замкнутый объем, как и положено приличным многогранникам.
(ну типа такого)
Маленький UPD, поясняющий, почему на КДПВ правый моб Не Ок, а левый Ок:
Правая картинка не Ок потому что моб завалится вперед, т.к. его центр масс вынесен за площадь опоры. Площадь опоры стоящего на поверхности многоугольника определяется как минимальный многоугольник, внутри которого окажутся все точки, находящиеся на поверхности. В левом случае площадь опоры сдвинута под центр масс и больше (т.к. динозаврские лапы больше), а на правой картинке сама площадь меньше и ближе к хвосту.
Соотношение опорной площади и центра масс будет примерно такое: 
Сразу начну с кода поиска объема (Python, входные данные — список точек и матрица переходов):
Суть алгоритма — считаем объемы фигур, которые образуют «падающие» на плоскость xy грани многогранника. Для этого надо знать площадь проекции треугольника и знак, с которым надо суммировать объем фигуры (усеченнной призмы). На самом деле, если заранее упорядочить треугольники, и объем и знак сводятся к одному вычислению.
Поэтому первым делом рекурсивная функция собирает треугольники из входных данных. Собирает таким образом, чтобы при взгляде «снаружи» на многогранник, направления обхода треугольников были одинаковыми (в идеале против часовой стрелки; если взять направления по часовой стрелке, то результат получится правильным, но отрицательным — поэтому в ретурн отдается модуль объема).
Добиться этого очень просто — берем какой-то треугольник (точки a1, a2, a3), ищем его соседей и перечисляем две совпавшие вершины в обратном порядке (например, так: a2, a1, b1).
Получается что-то вроде этого:
Теперь, если мы спроецируем такой треугольник на плоскость xy, то порядок обхода для проекции «верхнего» треугольника будет совпадать с изначально выбранным, а порядок обхода для проекци «нижнего» треугольника поменяет свое направление. Как следствие, поменяет знак и площадь этого треугольника, вычисленная по формуле Гаусса. Здесь «нижний» треугольник — понятие условное — имеется ввиду, что объем непосредственно под ним не входит в объем многогранника. «Нижний» треугольник у невыпуклого многогранника может быть выше «верхнего».
После этих предварительных действий, чтобы вычислить полный объем многогранника, надо просто сложить (с учетом знака, который получается «сам собой») все объемы усеченных призм, собранных из граней и проекций этих граней на плоскость xy. А объемы призм считаются как произведение площади (по Гауссу, со знаком) и среднего арифметического z-координат вершин треугольника.
Если многогранник пересекается плоскостью xy, то при вычислении объема, все знаки скомпенсируют друг друга и результат остается правильным (надо только брать высоты призмы без модуля).
(как-то так выглядит «верхняя» усеченная призма)
С поиском центра масс все приблизительно также. Аналогично надо найти центры масс для каждой усеченной призмы и просуммировать покоординатно, умножая на объем призмы (предполагается, что масса распределена равномерно по объему и можно одно заменить другим). Чтобы найти центр масс усеченной призмы, придется посчитать центры масс двух тетраэдеров (+1 функция) и одной обычной призмы. Алгоритм так же «не портится», если многогранник пересекает плоскость xy (а здесь могла бы быть репродукция Магритта).
(вот эти два тетраэдера, обозначены красным и рыжим, вместе с треугольной призмой (ниже красного тетраэдера) образуют искомую усеченную призму. Нам надо найти центры масс и объемы всех трех фигур. Обозначения примерно соответствуют обозначениям в коде)
Код, который считает то и то:
Кусок алгоритма, где считаются направления треугольников и используются для понимания внешнего и внутреннего объема — это очень сильный ход, его много как можно применить при работе с многогранниками. Например, если надо посчитать направление нормалей «наружу» — достаточно знать направление «против часовой стрелки» для одной грани — и вуаля!
(угадай фильм!)