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

Question

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

Вот решение, которое использует внутреннюю буферизацию:

https://web.archive.org/web/20150708063910/http://proceedings.esri.com/library/userconf/proc01/professional/papers/pap388/p388.htm

Если это нужно использовать, каков эффективный и быстрый способ найти буфер? Если какой-либо другой способ будет использоваться, что это за путь?

Хорошим примером действительно жестких многоугольников является гигантский толстый U (написанный Arial Black или Impact или каким-либо другим подобным шрифтом).

Answer 1

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

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

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

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

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

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

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

Answer 2

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

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

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

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

РЕДАКТИРОВАТЬ: Может быть, вы хотите найти точку, которая является центром самого большого круга, содержащегося в многоугольнике. Это не обязательно всегда в наблюдаемом центре, но большую часть времени, вероятно, дало бы ожидаемый результат, и только в слегка патологических случаях что-то, что было полностью отключено.

Answer 3

Как насчет:

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

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

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

Вот несколько фотографий, чтобы проиллюстрировать это:

Answer 4

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

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

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

Answer 5

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

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

Answer 6

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

Answer 7

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

Answer 8

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

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

Answer 9

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

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

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

Answer 10

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

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

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