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

Разговоры на любые темы: вы можете обсудить здесь какой-либо сайт, найти единомышленников или просто пообщаться...
alibek
Большой Человек
Большой Человек
 
Сообщения: 14205
Зарегистрирован: 19.04.2002 (Пт) 11:40
Откуда: Russia

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

Сообщение alibek » 08.02.2022 (Вт) 21:54

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

Mikle
Изобретатель велосипедов
Изобретатель велосипедов
Аватара пользователя
 
Сообщения: 4147
Зарегистрирован: 25.03.2003 (Вт) 14:02
Откуда: Туапсе

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

Сообщение Mikle » 08.02.2022 (Вт) 22:50

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

alibek
Большой Человек
Большой Человек
 
Сообщения: 14205
Зарегистрирован: 19.04.2002 (Пт) 11:40
Откуда: Russia

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

Сообщение alibek » 09.02.2022 (Ср) 0:42

Хотелось бы центр получить внутри дома.
Lasciate ogni speranza, voi ch'entrate.

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16473
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

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

Сообщение Хакер » 10.02.2022 (Чт) 8:45

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

Где должен быть центр у такого дома?
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

alibek
Большой Человек
Большой Человек
 
Сообщения: 14205
Зарегистрирован: 19.04.2002 (Пт) 11:40
Откуда: Russia

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

Сообщение alibek » 10.02.2022 (Чт) 9:14

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

alibek
Большой Человек
Большой Человек
 
Сообщения: 14205
Зарегистрирован: 19.04.2002 (Пт) 11:40
Откуда: Russia

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

Сообщение alibek » 10.02.2022 (Чт) 9:16

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

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

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

Mikle
Изобретатель велосипедов
Изобретатель велосипедов
Аватара пользователя
 
Сообщения: 4147
Зарегистрирован: 25.03.2003 (Вт) 14:02
Откуда: Туапсе

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

Сообщение Mikle » 10.02.2022 (Чт) 9:55

alibek писал(а):мне нужно разделить фигуру на прямоугольники

Это выполнимо только для строений со всеми прямыми углами.
alibek писал(а):У меня маршруты не проездов, а подвесных воздушных линий

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

alibek
Большой Человек
Большой Человек
 
Сообщения: 14205
Зарегистрирован: 19.04.2002 (Пт) 11:40
Откуда: Russia

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

Сообщение alibek » 10.02.2022 (Чт) 10:21

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

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

alibek
Большой Человек
Большой Человек
 
Сообщения: 14205
Зарегистрирован: 19.04.2002 (Пт) 11:40
Откуда: Russia

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

Сообщение alibek » 10.02.2022 (Чт) 10:22

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

Не понял фразы, можно пояснить?
Lasciate ogni speranza, voi ch'entrate.

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16473
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

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

Сообщение Хакер » 10.02.2022 (Чт) 10:47

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

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

Т.е. это нормально, что линии трасс будут пересекать контур здания?
Вложения
crossing.png
crossing.png (14.94 Кб) Просмотров: 1688
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

Mikle
Изобретатель велосипедов
Изобретатель велосипедов
Аватара пользователя
 
Сообщения: 4147
Зарегистрирован: 25.03.2003 (Вт) 14:02
Откуда: Туапсе

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

Сообщение Mikle » 10.02.2022 (Чт) 11:06

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

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

Разбиение фигуры на треугольники:
https://gamedev.ru/community/bycircle/forum/?id=140797
Вложения
building.PNG
building.PNG (3.83 Кб) Просмотров: 1687

alibek
Большой Человек
Большой Человек
 
Сообщения: 14205
Зарегистрирован: 19.04.2002 (Пт) 11:40
Откуда: Russia

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

Сообщение alibek » 10.02.2022 (Чт) 12:14

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

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

alibek
Большой Человек
Большой Человек
 
Сообщения: 14205
Зарегистрирован: 19.04.2002 (Пт) 11:40
Откуда: Russia

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

Сообщение alibek » 10.02.2022 (Чт) 12:20

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

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

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

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

alibek
Большой Человек
Большой Человек
 
Сообщения: 14205
Зарегистрирован: 19.04.2002 (Пт) 11:40
Откуда: Russia

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

Сообщение alibek » 10.02.2022 (Чт) 12:37

То есть что-то вроде такого.
Вложения
sample.jpg
sample.jpg (27.34 Кб) Просмотров: 1677
Lasciate ogni speranza, voi ch'entrate.

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16473
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

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

Сообщение Хакер » 10.02.2022 (Чт) 13:36

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

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

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

Затем нужно найти в фигуре точку, где F(x,y) принимает максимальное значение.
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

alibek
Большой Человек
Большой Человек
 
Сообщения: 14205
Зарегистрирован: 19.04.2002 (Пт) 11:40
Откуда: Russia

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

Сообщение alibek » 10.02.2022 (Чт) 13:54

Разве это будет отличаться от центра масс (где масса распределена по всей фигуре)?
Lasciate ogni speranza, voi ch'entrate.

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16473
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

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

Сообщение Хакер » 10.02.2022 (Чт) 14:42

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

Да, конечно, ведь барицентр (красная точка) букву «П» находится вне буквы П, а точка с максимумом длин исходящих лучей (зелёная точка) — в фигуре и и самом визуально «жирном» месте.
Вложения
bari_vs_raytraced.png
bari_vs_raytraced.png (10.47 Кб) Просмотров: 1672
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

alibek
Большой Человек
Большой Человек
 
Сообщения: 14205
Зарегистрирован: 19.04.2002 (Пт) 11:40
Откуда: Russia

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

Сообщение alibek » 10.02.2022 (Чт) 14:48

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

alibek
Большой Человек
Большой Человек
 
Сообщения: 14205
Зарегистрирован: 19.04.2002 (Пт) 11:40
Откуда: Russia

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

Сообщение alibek » 10.02.2022 (Чт) 14:51

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

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16473
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

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

Сообщение Хакер » 10.02.2022 (Чт) 15:06

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

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

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

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

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

Нет, распределённых по всей фигуре или контуру. В целом, само определение не включает в себя оговорок о том, как именно распределены массы. Греческое «бари-» это просто «тяже-» или «тяжести-».
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

alibek
Большой Человек
Большой Человек
 
Сообщения: 14205
Зарегистрирован: 19.04.2002 (Пт) 11:40
Откуда: Russia

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

Сообщение alibek » 10.02.2022 (Чт) 16:15

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

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

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16473
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

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

Сообщение Хакер » 10.02.2022 (Чт) 17:15

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

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

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

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

Ещё есть мысль о другом алгоритме, попробую подумать и описать.
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

alibek
Большой Человек
Большой Человек
 
Сообщения: 14205
Зарегистрирован: 19.04.2002 (Пт) 11:40
Откуда: Russia

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

Сообщение alibek » 10.02.2022 (Чт) 22:32

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

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16473
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

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

Сообщение Хакер » 10.02.2022 (Чт) 22:44

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

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

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

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

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

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


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

Само по себе «рентгеновское» проецирование, если подумать, очень простое: не требуется никакой трассировки лучей, потому что толщина фигуры при рассечении произвольной линией в произвольном месте может быть получена простой линейной интерполяцией между толщинами, подсчитанными для прохождения секущей через вертексы, а подсчитать толщины для 4—16 вертексов дело очень быстрое.
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

Mikle
Изобретатель велосипедов
Изобретатель велосипедов
Аватара пользователя
 
Сообщения: 4147
Зарегистрирован: 25.03.2003 (Вт) 14:02
Откуда: Туапсе

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

Сообщение Mikle » 10.02.2022 (Чт) 22:46

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

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


Вернуться в Народный треп

Кто сейчас на конференции

Сейчас этот форум просматривают: AhrefsBot и гости: 12

    TopList