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

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

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

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

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

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

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

Аналогично: Вычислить центроид ВНУТРИ / ВНУТРИ пространственного многоугольника

Аналогично: Как найти две самые далекие точки?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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