Лучше "центральная точка", чем центроид

Question

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

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

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

Answer 1

Чтобы получить точку для маркера, я бы использовал метод Ива Дауста.

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

Если бы у меня было время на разработку и тестирование, и я хотел хорошей производительности, то я бы использовал гибридный метод: сначала используйте метод Ива Дауста, чтобы получить некоторыеОчки кандидатов, а затем проверить кандидатов, чтобы увидеть, находятся ли они в пределах многоугольника.Если все кандидаты терпят неудачу, то используйте более медленный надежный метод (например, GLUtesselator).

Answer 2

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

Найдите пересечение со сторонами и рассортируйте их по возрастанию абсциссы.Укажите точку в середине двух пересечений.

Это процесс O (N + K Log K), где K - количество пересечений (обычно очень маленькое четное число).Довольно просто написать.

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

Answer 3

Чтобы перефразировать комментарий ChristopheRoussy, мы можем искать самый большой круг внутри многоугольника.

Самый большой круг - это тот, который больше не может расти, потому что он касается трех вершин или ребер (если он касается только двух,он может увеличиваться или просто перемещаться, пока не достигнет третьей).

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

Но для этого потребуется создать четыре функции:

1. Круг (вершина, вершина, вершина)
2. Круг (вершина, вершина, ребро)
3. Круг (вершина, ребро, ребро)
4. Круг (ребро, ребро, ребро)

Все они возможны, но могут потребовать некоторых усилий.

Answer 4

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

Библиотека CGAL имеет модуль 2D Прямой скелет и смещение многоугольника , или вы могли бы используйте PostGIS , например.

Answer 5

for (int i = 0; i < n; /*++i*/) {
    p = RandomPointInsideConvexHull();
    if (IsInsidePolygon(p)) {
        ++i;
        d = DistanceToClosestEdge(p);
        if (d > bestD) {
            bestP = p;
        }
    }
}

После выполнения этого цикла вы приблизите решение к bestP.n - это параметр для выбора.Если вы хотите получить более точный результат, вы можете возобновить поиск, но теперь вместо выбора точки внутри выпуклой оболочки многоугольника вы можете выбрать точку в окрестности bestP, скажем, не дальше bestD / 5 (на этот раз вам не нужнопроверить, находится ли случайная точка внутри многоугольника).

Answer 6

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

https://en.wikipedia.org/wiki/Force-directed_graph_drawing

Эвристика : через некоторое время это может привести к разумному приближению

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

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

ИМХО спрашивает об этом на математическом форуме.

Аналог: Рассчитать центроид ВНУТРИ / ВНУТРИ SpatialPolygon

Похожие: Как найти две самые дальние точки?