Найти центр фигуры

[alibek]

Есть замкнутая фигура (это контур дома), образованная тремя и более точками, заданными парами GPS-координат.
В простейшем случае это будет прямоугольник, но могут быть и более сложные фигуры.
Для упрощения можно считать, что в фигуре нет взаимных пересечений.
Подскажите, как найти центр фигуры?
Хотелось бы более качественный алгоритм, чем например центр bbox.

[Mikle]

Что такое "центр"? Центр тяжести годится? А если он не внутри дома? Как пример - "П"-образное строение.

[alibek]

Хотелось бы центр получить внутри дома.

[Хакер]

Хотелось бы центр получить внутри дома.

Где должен быть центр у такого дома?

[alibek]

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

[alibek]

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

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

Вообщем, буду пока использовать центр bbox. Как ни странно, но глазу он кажется более правильным, чем барицентр.

[Mikle]

мне нужно разделить фигуру на прямоугольники

Это выполнимо только для строений со всеми прямыми углами.

У меня маршруты не проездов, а подвесных воздушных линий

Как понимаю, это значит, что годятся все точки внутри строения, в т ч на самом краю, над стеной?
Может тогда искать точку, от которой расстояние до самого дальнего угла строения минимально? Расстояние не по прямой линии, а по маршруту в пределах силуэта строения.

[alibek]

Поправлюсь — разделить фигуру на выпуклые многоугольники.

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

[alibek]

Может тогда искать точку, от которой расстояние до самого дальнего угла строения минимально? Расстояние не по прямой линии, а по маршруту в пределах силуэта строения.

Не понял фразы, можно пояснить?

[Хакер]

А какие ограничивающие требования по сложности алгоритма?

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

Т.е. это нормально, что линии трасс будут пересекать контур здания?

[Mikle]

Не понял фразы, можно пояснить?

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

Разбиение фигуры на треугольники:
https://gamedev.ru/community/bycircle/forum/?id=140797

[alibek]

Т.е. это нормально, что линии трасс будут пересекать контур здания?

Да. Линия приходит на объект, который размещается внутри дома. Если точные координаты этого объекта неизвестны, то считаем, что он находится в центре дома.

[alibek]

А какие ограничивающие требования по сложности алгоритма?

Чтобы я мог его легко написать на PHP, не тратя слишком много времени.

Но, если на краю здания тебя не устраивает, этот подход тоже не годится.

Да, не подходит.
У меня была мысль "утоньшать" контур здания вовнутрь, пока он не сведется к линии. И просто выбрать по расстоянию середину этой линии, игнорируя "отводы" (для зданий в форме Ш).
Но пока не сообразил, как делать контур.

[alibek]

То есть что-то вроде такого.

[Хакер]

Чтобы я мог его легко написать на PHP, не тратя слишком много времени.

Я имел в виду вычислительную сложность. О-большое.

У меня вот такая идея: ввести понятие функции F(x,y) — такой, что из точки (x;y) выпускаются в разные стороны лучи (скажем, 16—20 лучшей с равным угловым шагом) до пересечения с ближайшей «стенкой», и функция возвращает сумму отрезков, образованных этими лучами (один конец отрезка — начальная точка, другой — точка пересечения луча с контуром).

Затем нужно найти в фигуре точку, где F(x,y) принимает максимальное значение.

[alibek]

Разве это будет отличаться от центра масс (где масса распределена по всей фигуре)?

[Хакер]

Разве это будет отличаться от центра масс (где масса распределена по всей фигуре)?

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

[alibek]

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

[alibek]

Если не ошибаюсь, то барицентр это центр масс, сосредоточенных в вершинах. А центры масс, сосредоточенных в каркасе и фигуре, могут отличаться.

[Хакер]

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

Оптимизировать путём использование барицентра для полностью выпуклых объектов.

Много ли всяких П-, Г- и Ж-образных зданий?

Если это какой-то оффлайн экспорт, то может и нет никакой проблемы? Другое дело, если центры надо искать real-time.

то барицентр это центр масс, сосредоточенных в вершинах.

Нет, распределённых по всей фигуре или контуру. В целом, само определение не включает в себя оговорок о том, как именно распределены массы. Греческое «бари-» это просто «тяже-» или «тяжести-».

[alibek]

Много ли всяких П-, Г- и Ж-образных зданий?

Да как в любом городе. Основное количество это прямоугольные здания или L-образные.
Но и другие формы встречаются, и не настолько мало, чтобы ими пренебречь.
При этом нельзя ориентироваться, что противоположные ребра будут параллельны, или углы на вершинах будут ровно 90 градусов.

[Хакер]

и не настолько мало, чтобы ими пренебречь.

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

или углы на вершинах будут ровно 90 градусов.

Ну так вроде бы предложенный аглоритм с этим не конфликтует.

Ещё есть мысль о другом алгоритме, попробую подумать и описать.

[alibek]

Тогда возникает отдельная задача — классифицировать фигуры.
И еще пожалуй более сложная — как разбить фигуру на выпуклые многоугольники (от центра которых делать трассировку).
У меня возникла мысль попробовать максимально "распрямить" фигуру в линию и центр взять просто по середине получившейся линии.
Правда это все "на пальцах", нужно будет попробовать порисовать, что получится.

[Хакер]

Тогда возникает отдельная задача — классифицировать фигуры.

Это легко: у неё все углы при вершинах одного знака.

И еще пожалуй более сложная — как разбить фигуру на выпуклые многоугольники (от центра которых делать трассировку).

А я не говорил разбивать и искать центр — это ставит саму идею трассировки под вопрос. Я имел в виду наложить на фигуру некую сетку и делать трассировку для всех точек этой сетки, а потом выбирать максимум. Или искать этот максимум каким-нибудь методом, где сначала делаются крупные шаги, а затем с каждым шагом более мелкие поправки. Что-то вроде метода Монте Карло / алгоритма отжига.

У меня возникла мысль попробовать максимально "распрямить" фигуру в линию и центр взять просто по середине получившейся линии.

Как распрямить Ш-образное или Ж-образное здание?


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

Само по себе «рентгеновское» проецирование, если подумать, очень простое: не требуется никакой трассировки лучей, потому что толщина фигуры при рассечении произвольной линией в произвольном месте может быть получена простой линейной интерполяцией между толщинами, подсчитанными для прохождения секущей через вертексы, а подсчитать толщины для 4—16 вертексов дело очень быстрое.

[Mikle]

еще пожалуй более сложная — как разбить фигуру на выпуклые многоугольники

Я выше давал ссылку на триангуляцию.