Поиск центра полигона.
От: ssvSerge  
Дата: 25.06.23 07:51
Оценка:
Добрый всем день.

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

Задача: найти точку для установки надписи — названия участка. При этом точка должна быть гарантированно в теле полигона и как можно ближе к "логическому центру" фигуры.

Перепробовал массу решений, но что-то ни одно не нравится. Тем не менее, на всех картах как-то этот вопрос решён.
Re: Поиск центра полигона.
От: Нomunculus Россия  
Дата: 25.06.23 08:02
Оценка:
Здравствуйте, ssvSerge, Вы писали:

Если взять квадрат с круглой дыркой в центре, то где должна быть эта точка?
Если точка нужна именно на полигоне и не в дырках, то смотри «центроид». Но он не всегда визуально центрирован.
Re[2]: Поиск центра полигона.
От: ssvSerge  
Дата: 25.06.23 08:31
Оценка:
Здравствуйте, Нomunculus, Вы писали:

Н>Если взять квадрат с круглой дыркой в центре, то где должна быть эта точка?

Н>Если точка нужна именно на полигоне и не в дырках, то смотри «центроид». Но он не всегда визуально центрирован.

Положение текста не очень важно. Мы выдумали понятие "логический центр", которых может быть несколько.

Что же касается "квадрата с вырезом", то в любом месте на теле квадрата, но не близко к границе выреза.
Re: Поиск центра полигона.
От: kov_serg Россия  
Дата: 25.06.23 08:46
Оценка:
Здравствуйте, ssvSerge, Вы писали:

S>Задача следующая: рисуется карта, на которой могут быть полигоны любой сложности. Возможны вырезы, тонкие как стилеты участки, их комбинации и т.д.


S>Задача: найти точку для установки надписи — названия участка. При этом точка должна быть гарантированно в теле полигона и как можно ближе к "логическому центру" фигуры.


S>Перепробовал массу решений, но что-то ни одно не нравится. Тем не менее, на всех картах как-то этот вопрос решён.


Так явно задавайте ваш логический центр. Или путь вдоль которого можно размещать текст.
Re[2]: Поиск центра полигона.
От: ssvSerge  
Дата: 25.06.23 08:57
Оценка:
Здравствуйте, kov_serg, Вы писали:

_>Так явно задавайте ваш логический центр. Или путь вдоль которого можно размещать текст.


Не в ручную же это делать! Путь тоже устраивает.
Re[3]: Поиск центра полигона.
От: Нomunculus Россия  
Дата: 25.06.23 09:00
Оценка:
Здравствуйте, ssvSerge, Вы писали:

Накидывайте сетку, ищите по узлам, которые внутри полигона и не внутри дырок наиболее удаленные от краев, ну и выбирайте среди результатов наиболее близкие к центру масс, или центру инерции или к центроиду — какой больше устроит
Re[4]: Поиск центра полигона.
От: ssvSerge  
Дата: 25.06.23 09:26
Оценка:
Здравствуйте, Нomunculus, Вы писали:

Н>Накидывайте сетку.


Сетку — можем. Текущая идея — сканирующий горизонтальный луч и сбор статистики по срезам. Но что-то берёт сомнение, что это оптимальный вариант. По крайней мере, графические приложения решают эту задачу раз эдак в 1000 быстрее нас.
Re[3]: Поиск центра полигона.
От: kov_serg Россия  
Дата: 25.06.23 12:46
Оценка:
Здравствуйте, ssvSerge, Вы писали:

S>Здравствуйте, kov_serg, Вы писали:


_>>Так явно задавайте ваш логический центр. Или путь вдоль которого можно размещать текст.


S>Не в ручную же это делать! Путь тоже устраивает.

Зачем вручную. Смотрите топологические операции, суммы Миньковского и построение скелета.

https://arxiv.org/pdf/2110.05805.pdf
https://resources.mpi-inf.mpg.de/departments/d1/teaching/ss10/Seminar_CGGC/Slides/07_Bock_MS.pdf
https://www.sthu.org/code/stalgo
https://www.cosy.sbg.ac.at/~held/projects/wsk/wsk.html
Re: Поиск центра полигона.
От: T4r4sB Россия  
Дата: 25.06.23 14:24
Оценка:
Здравствуйте, ssvSerge, Вы писали:

Ну типа определить все точки, где можно разместить надпись, чтоб она не вылазила, множество таких точек это тоже полигон, так что оно определяется за линейное время.
И найти центр масс этого "допустимого" полигона.
Re: Поиск центра полигона.
От: Nuzhny Россия https://github.com/Nuzhny007
Дата: 25.06.23 19:10
Оценка: 1 (1)
Здравствуйте, ssvSerge, Вы писали:

S>Перепробовал массу решений, но что-то ни одно не нравится. Тем не менее, на всех картах как-то этот вопрос решён.


В компьтерном зрении обычно применяют Distance transform, например из OpenCV. А потом ищут максимум внутри контура.
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.