Что самый быстрый путь состоит в том, чтобы найти “визуальным” центром полигона неправильной формы?

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

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

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

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

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

48
задан Mark Fisher 20 August 2019 в 18:04
поделиться

10 ответов

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

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

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

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

10
ответ дан 26 November 2019 в 19:05
поделиться

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

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

-1
ответ дан 26 November 2019 в 19:05
поделиться

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

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

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

0
ответ дан 26 November 2019 в 19:05
поделиться

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

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

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

7
ответ дан 26 November 2019 в 19:05
поделиться

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

1
ответ дан 26 November 2019 в 19:05
поделиться

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

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

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

-1
ответ дан 26 November 2019 в 19:05
поделиться

Представления CouchDB не поддерживают фасетный поиск, полнотекстовый поиск или пересечение результатов.

-2
ответ дан 26 November 2019 в 19:05
поделиться

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

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

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

-1
ответ дан 26 November 2019 в 19:05
поделиться

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

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

-1
ответ дан 26 November 2019 в 19:05
поделиться

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

2
ответ дан 26 November 2019 в 19:05
поделиться
Другие вопросы по тегам:

Похожие вопросы: