Задача следующая: рисуется карта, на которой могут быть полигоны любой сложности. Возможны вырезы, тонкие как стилеты участки, их комбинации и т.д.
Задача: найти точку для установки надписи — названия участка. При этом точка должна быть гарантированно в теле полигона и как можно ближе к "логическому центру" фигуры.
Перепробовал массу решений, но что-то ни одно не нравится. Тем не менее, на всех картах как-то этот вопрос решён.
Если взять квадрат с круглой дыркой в центре, то где должна быть эта точка?
Если точка нужна именно на полигоне и не в дырках, то смотри «центроид». Но он не всегда визуально центрирован.
Здравствуйте, Нomunculus, Вы писали:
Н>Если взять квадрат с круглой дыркой в центре, то где должна быть эта точка? Н>Если точка нужна именно на полигоне и не в дырках, то смотри «центроид». Но он не всегда визуально центрирован.
Положение текста не очень важно. Мы выдумали понятие "логический центр", которых может быть несколько.
Что же касается "квадрата с вырезом", то в любом месте на теле квадрата, но не близко к границе выреза.
Здравствуйте, ssvSerge, Вы писали:
S>Задача следующая: рисуется карта, на которой могут быть полигоны любой сложности. Возможны вырезы, тонкие как стилеты участки, их комбинации и т.д.
S>Задача: найти точку для установки надписи — названия участка. При этом точка должна быть гарантированно в теле полигона и как можно ближе к "логическому центру" фигуры.
S>Перепробовал массу решений, но что-то ни одно не нравится. Тем не менее, на всех картах как-то этот вопрос решён.
Так явно задавайте ваш логический центр. Или путь вдоль которого можно размещать текст.
Накидывайте сетку, ищите по узлам, которые внутри полигона и не внутри дырок наиболее удаленные от краев, ну и выбирайте среди результатов наиболее близкие к центру масс, или центру инерции или к центроиду — какой больше устроит
Здравствуйте, Нomunculus, Вы писали:
Н>Накидывайте сетку.
Сетку — можем. Текущая идея — сканирующий горизонтальный луч и сбор статистики по срезам. Но что-то берёт сомнение, что это оптимальный вариант. По крайней мере, графические приложения решают эту задачу раз эдак в 1000 быстрее нас.
Здравствуйте, ssvSerge, Вы писали:
S>Здравствуйте, kov_serg, Вы писали:
_>>Так явно задавайте ваш логический центр. Или путь вдоль которого можно размещать текст.
S>Не в ручную же это делать! Путь тоже устраивает.
Зачем вручную. Смотрите топологические операции, суммы Миньковского и построение скелета.
Ну типа определить все точки, где можно разместить надпись, чтоб она не вылазила, множество таких точек это тоже полигон, так что оно определяется за линейное время.
И найти центр масс этого "допустимого" полигона.
Нет такой подлости и мерзости, на которую бы не пошёл gcc ради бессмысленных 5% скорости в никому не нужном синтетическом тесте