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

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

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

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

Answer 2

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

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

Answer 3

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

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

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

Answer 4

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

РЕДАКТИРОВАТЬ: этот метод не будет работать, если полигон имеет "дыры"