Каков самый быстрый способ найти "визуальный" центр многоугольника неправильной формы?

Ответ 1

Если вы можете преобразовать многоугольник в двоичное изображение, вы можете использовать основу, существующую в области обработки изображений, например: Быстрый скелет Алгоритм на бинарных изображениях, представляемых блоком.

Но это не очень разумно в общем случае из-за ошибок дискретизации и дополнительной работы.

Однако, может быть, вы найдете их полезными:

• Прямой скелет простого многоугольника
• Определение скелета простого многоугольника в (почти) линейном времени

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

Ответ 2

Я нашел очень хорошее решение для этого из MapBox под названием Polylabel. Полный исходный код также доступен на их Github.

По сути, он пытается найти визуальный центр многоangularьника, как сказал Т. Остин.

Некоторые детали предполагают, что это может быть практическим решением:

К сожалению, вычисление [идеального решения] является сложным и медленно. Опубликованные решения проблемы требуют либо Ограниченная триангуляция Делоне или вычисление прямого скелета как этапы предварительной обработки - оба они медленные и подвержены ошибкам.

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

Краткое примечание об использовании, хотя. Исходный код отлично работает для Javascript из коробки, однако, если вы собираетесь использовать его с "нормальным" многоangularьником, вам следует заключить его в пустой массив, поскольку функции здесь принимают GeoJSONPolygons вместо обычных многоangularьников, т.е.

var myPolygon = [[x1, y1], [x2, y2], [x3, y3]];
var center = polylabel([myPolygon]);

Ответ 3

Вы изучали использование формулы центроида?

http://en.wikipedia.org/wiki/Centroid

http://en.wikipedia.org/wiki/K-means_algorithm

Ответ 4

Как насчет:

Если центроид многоугольника находится внутри многоугольника, тогда используйте его, иначе:

1) Протяните линию от центра тяжести через многоугольник, разделяющий многоугольник на две половины равной области

2) "Визуальный центр" - это точка на полпути между ближайшей точкой, где линия касается периметра, а следующая точка разрезает периметр в направлении, удаляющемся от центра тяжести.

Вот несколько иллюстраций для иллюстрации:

Ответ 5

Вычислите центральное положение (x, y) каждого ребра многоугольника. Вы можете сделать это, найдя разницу между положениями концов каждого края. Возьмите среднее значение каждого центра в каждом измерении. Это будет центр многоугольника.

Ответ 6

Метод Centroid уже был предложен несколько раз. Я думаю, что это отличный ресурс, который описывает процесс (и многие другие полезные трюки с полигонами) очень интуитивно:

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 (относительно, например, первой вершины многоугольника), до структура данных многоугольника.

Ответ 7

Я не говорю, что это самый быстрый, но он даст вам точку внутри полигона. Вычислите Прямой скелет. Точка, которую вы ищете, находится на этом скелете. Например, вы можете выбрать тот, у которого самое короткое нормальное расстояние до центра ограничительной рамки.

Ответ 8

Как насчет поиска "обводки" многоугольника (самого большого круга, который входит в него), а затем центрирования метки в центре этого? Вот несколько ссылок, которые помогут вам начать:

http://www.mathopenref.com/polygonincircle.html
https://nrich.maths.org/discus/messages/145082/144373.html?1219439473

Это не будет работать отлично на каждом полигоне, скорее всего; многоугольник, который выглядел бы как C, имел бы метку в несколько непредсказуемом месте. Но преимущество в том, что метка всегда будет перекрывать твердую часть многоугольника.

Ответ 9

Я думаю, что если вы сломали многоугольник обратно в его вершины, а затем применили функцию, чтобы найти самую большую выпуклую оболочку, а затем найти центр от этой выпуклой оболочки, она будет близка к "очевидному" центру.

Нахождение наибольшей выпуклой оболочки, заданной вершинами: Посмотрите в параграфе Simple Polygon.

Средние вершины выпуклой оболочки, чтобы найти центр.

Ответ 10

Если я понимаю суть статьи, с которой вы связались (довольно интересная проблема, кстати), эта техника "внутренней буферизации" несколько аналогична моделированию рассматриваемой фигуры из куска сахара, который растворяется кислотой из (например, при увеличении расстояния до буфера, меньше прежней формы). Последний бит остается идеальным местом для размещения метки.

Как это сделать в алгоритме, к сожалению, мне не очень понятно....

Ответ 11

Не могли бы вы поместить ярлык в наивный центр (возможно, в ограничительную рамку), а затем переместить его на основе пересечений ребер локального многоугольника и метки BB? Двигайтесь вдоль нормалей пересекающихся ребер, а если несколько краев пересекаются, суммируйте их нормали для движения?

Просто угадай здесь; в этой проблеме я, вероятно, попытаюсь решить итеративно, пока производительность не слишком важна.

Ответ 12

Не так много времени, чтобы разработать или проверить это прямо сейчас, но я постараюсь сделать больше, когда у меня появится шанс.

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

Поскольку точка, ближайшая к центроиду, скорее всего, свяжет довольно большую площадь, я думаю, что это может привести к результатам, подобным кругам Киральсы. Конечно, это может быть неистово, если у вас есть многоугольник с отверстиями. В этом случае, по всей видимости, внутренности будут намного лучше. С другой стороны, для типичных случаев по умолчанию используется метод (быстрый?) Центроид.

Ответ 13

Эта проблема, вероятно, будет аналогична поиску "центра масс", предполагающего однородную плотность.

EDIT: этот метод не будет работать, если многоугольник имеет "отверстия"

Ответ 14

вы можете использовать метод центра масс (или центра тяжести), который используется в гражданском строительстве, вот полезная ссылка из википедии:

http://en.wikipedia.org/wiki/Center_of_mass