Russian Qt Forum

Здравствуйте.

Подскажите пожалуйста, каким образом можно получить уменьшенный полигон, "сжав" исходный? Масштабирование (scale) тут не подходит. Картинку для понимания сути приложил.

Кое как реализовал через QLineF::normalVector() (https://qt-project.org/doc/qt-5.0/qtcore/qlinef.html#normalVector), но во многих полигонах у меня получаются "петли", от которых не могу никак избавиться (на второй картинке вложения).

Функциональность называется offset (https://www.google.ru/search?client=opera&q=polyline+offset&sourceid=opera&ie=utf-8&oe=utf-8&channel=suggest). В Qt такой точно нет, нужно брать откуда-то или самому реализовывать. Правда для реализации оффсета от кубической безье (а внутри QPainterPath только такие могут быть кроме отрезков) придется постараться, т.к. этот оффсет уже не будет сам по себе кривой безье.

Эта операция называлась "эквидистанта" в старом AutoCAD :) Да, она  нелинейна и масштабом не делается. Нужно самому считать точки. Данные

QPointF old_Pt  - точка полигонв
QPointF  dir - единичный вектор направления  (внутрь/наружу)
qreal delta - величина сжатия
qreal angle - угол изгиба полигона в точке pt (в радианах)

Тогда новая точка

QPointF new_Pt = old_Pt + dir * (delta / sin((M_PI - angle) / 2));

Про название - буду знать, спасибо. Мне высокая точность повторения полигона-оригинала не нужна, просто хотел избавиться от "петель". У некоторых полигонов имеются довольно узкие "отростки" (вот как на втором рисунке), и из-за них получаю вот такие "лассо", которые портят конечный результат. Надо как-то анализировать ширину таких узких мест, а я совсем не силён в геометрии.

В инете подсказывают, что, например, CGAL решает эту проблему, но из-за одного только этого неудобства отдельную библиотеку цеплять совсем не хочется. Подумал, что может кто писал свой самопальный алгоритм или натравит на путь истинный, чтобы решить проблему средствами Qt.

Ого! Спасибо большое, попробую. Это явно лучше, чем то, что я понаписал ))

Та какая там либа, тем более CGAL (которому нужен дуст)???  Тут просто теорема Пифагора - и все дела. На всякий случай сообщаю как взять угол

C++ (Qt)
qreal PolyAngle( const QPolygonF & poly, int index )
{
 int count = poly.size();
 assert(count > 2);
 const QPointF & nxt = poly[(index + 1) % count];
 const QPointF & prv = poly[(index - 1 + count) % count];
 QVector2D v1 = QVector2D(poly[index] - prv).normalized();
 QVector2D v2 = QVector2D(nxt - poly[index]).normalized();
 return acos(QVector2D ::dotProduct(v1, v2));
}

Хреново у них операции с векторами сделаны, получается длинно и мутно. 

Мне, к сожалению, не так всё очевидно.

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

Это в Qt или в CGAL?

А это прямой результат бесконечного использования готовых тулзов :) Такие задачи решаются рисованием чертежа на бумажке - лучше покрупнее

В Qt

Рисовал. И в общем-то решил с оговорками. Ну и конечно не столь лаконично. Третий день сижу :) Ну а что касаемо готовых тулзов, то не всегда есть время разбираться во всём досконально. Естественно, многое используешь не глядя. В этом есть плюс того, что сильно экономится время. Хотя безусловно, когда припрёт, тут уж "хошь не хошь".

Igors, а как вычислить dir? Я видимо что-то не правильно делаю. Контуры сжатого полигона разъезжаются.

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

Ууу.. Чёт как то сложно всё тут у вас для простого масштабирования.. Всякие скалярные произведения, acos и т.д..
Должно быть проще)

А где здесь "простое масштабирование"?

Да, вроде так и делал.

Приложил.

Пока разберусь куда там вставлять - проще самому простой проект сделать  :)  Attach

На простом полигоне это работает. Я просто добавил свой полигон в Ваш код. Взгляните.

С помощью функции во вложении я получил результат как на скриншоте. Но есть проблема, что получаются "петли" в узких местах полигона (отметил красным) и соприкосновение линий "сжатого" полигона с полигоном-источником (отметил зелёным). Вторая проблема менее критична, а вот первая надо как-то устранить, но не могу придумать как.

Ну так у Вас длины отрезков примерно 1.0, а величина выдавливания 20 - конечно перехлестнет. Используйте разумную амплитуду - напр 0.5

Вникнуть в текст (засоренный модными итераторами) трудновато. Покажите исходную одним цветом а построенный контур другим - и будет ясно

По поводу возможных само-пересечений. Это типовая проблема если исходная поли-линия слишком "зубатая" и/или амплитуда слишком велика. Пока на Ваших картинках такого не видел. Чаще всего эту проблему "никак не решают" (т.е. отдают на откуп пользователю считая что он задаст разумные значения). По-настоящему хорошего/нормального решения там нет, надо так или иначе латать. Это можно долго обсуждать, но сначала давайте разберемся чего не хватает и откуда перехлесты.

Да, точно, Вы правы, использовал неподходящую амплитуду. Отрисовало также как у меня.

QVectorIterator, что в нём модного? С итераторами очень удобно, если индексы особо не нужны.

Нарисовал. Чёрный цвет - исходный полигон. Красный - "сжатый". Видна петля у красного контура в нижней части изображения с левой стороны.

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

Ну как же. На всех скриншотах я жирным маркером красного цвета обвёл места, где петли выводятся.

Перехлёсты (петли) получаются в узких местах полигона, когда вектор нормали (или как его правильно назвать) получается длиннее чем половина ширины узкого места полигона. Тут наверное надо как-то определять ширину узкого места, чтобы выводить точки для сжатого полигона на расстоянии от исходной, вычисляемого по коэффициенту, а не на основе постоянной величины. Либо найти способ, как удалить точки петель, скажем, вторым каким-нибудь проходом по точкам сжатого полигона. Я пробовал добавлять метод вырезания точек, расстояние между которыми меньше задаваемого минимума. Часть точек петли конечно вырезается, но опять же не все.

Определимся с постановкой. Вот место где будет перехлест (аттач). Очевидно что при достаточной амплитуде повторить контур "справа" просто не удастся, не влезет. Возможные решения

- "пропускать" такие места, красный будет гладким но потеряет детали
- автоматычно сужать размер "дорожки"
- Ваш вариант?

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

Ну резать так резать :) Можно напр сделать метод "удалить само-пересечения", потом (если понадобится) подгладить эти места. Тут надо (немного) подумать, до завтра сделаю

Хм... спасибо большое! Я над этим уже три дня бьюсь. Единственное, что смог придумать - это выполнять свою offset-функцию совместно с функцией вырезания точек по минимально допустимой длине линии в несколько итераций. Но с каждой такой итерацией сжатый полигон естественно всё больше сужается и "огрубляется" (меньше следует форме исходного полигона). Да, петли удаляются полностью, но конечный результат "не вставляет", т.к. у меня есть совсем уж аляпистые полигоны, у которых узкие и широкие области могут понескольку раз перемежаться.

P.S. Контуры берутся из векторного SVG изображения, которое в свою очередь создаётся векторным редактором из растровой картинки.

Igors, подскажите хоть суть метода "удалить само-пересечения". Каким образом это можно сделать?

А что вы хотите делать с отделяющимися и исчезающими островками вроде таких:
(http://i46.tinypic.com/wmf4o.gif)
?

Круто! А как Вы так сделали?! Островки оставить конечно, я их отдельным полигоном оформлю. Поделитесь, если не жалко алгоритмом.

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

Проект не open source, так что кодом поделиться не могу. А алгоритм брали и реализовывали по статьям вроде этой (http://hal.inria.fr/docs/00/51/80/05/PDF/Xu-ZhengLiu2007a.pdf) и других, которые ищутся в google.

Так что предлагаю подождать решение от Igors, интересно будет посмотреть на выбранный им алгоритм...

Делаю, скоро будет  :)

Нашёл в инете на C# (или типа того, их хрен разберёшь) пример. Переписал на C++, но тоже самое - петли в узких местах. Хоть сам полезай в оную ))

(из послания к окруженной в Сталинграде армии)

Ну в общем сделал (аттач). Довольно трудно, в каких-то случаях остаются "пипсики" которые формально корректны, но конфузят.

Ну да, легко смеяться над глупыми велосипедистами, а припрет - и где же оно, то "готовое решение" которое так экономит время и силы ?  :)

Edit: удалил аттач чтобы был только последний (см ниже)

Урааа!!! Просто шикарно, Igors, спасибо огромное! Мне точно минимум неделю разбираться в коде, как оно там работает, но то что результат нужный - факт! Очень выручили :)

В отличие от Паулюса я помощи дождался ))

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

В большинстве случаев этот "смех" обоснован, тем более когда велосипедист заявляет, что сделает круче в сто тыщ мильёнов раз, но на деле ничего не выходит :)

Там (уже заметил) минимум 2 ошибки, будет время - подправлю. "В принципе" все довольно просто:

- создаем список всех точек
- создаем контейнер всех само-пересечений и сортируем его по длине "петель"
- убираем петли начиная с наименьшей. Петля удаляется из списка и точки петли помещаются в новый полигон (остров)

Однако технически трудновато  :)

Критические? Алгоритм Ваш, думаю, будет востребован. Поправьте по возможности, если не трудно.

Не могу с Вами не согласиться. Там совсем не просто. Вроде и логика ясна, что надо сделать, а как это в коде повторить - целая проблема.

Подрихтовал (там хотел было проскочить с поиском только по одной из осей - но это некорректно).

Edit: удалил аттач чтобы был только последний (см ниже)

Спасибо :) Это проверка расширения полигона по вертикали и горизонтали?

Нет. Каждый отрезок должен быть проверен на пересечение со всеми последующими. Схема

         * ...  *     
P(i)*--------------P(i+1)*    ось X

Я рассчитывал искать в сортированном списке от "левой" точки отрезка до "правой" - но так ловятся не все пересечения  :)

А почему? Массив ведь одномерный, какая разница, в какую сторону итерацию проводить?

Подумал еще раз - вроде изначально идея была правильной, все-таки можно обойтись одной осью. Вот последний вариант (attach)

Эта тема теперь больше для кладовой готовых решений подходит. Во всяком случае в инете нет решения этой задачи в открытом доступе. Я перерыл за последние несколько дней кучу ресурсов.

Плохо искали, для обычных полигонов есть как минимум Clipper (http://www.angusj.com/delphi/clipper.php).

А что понимается под "обычным"? В остальном хотелось бы отметить 2 момента

1) Расходы на поиск могут быть значительны, и не гарантируется что готовое решение будет найдено - а время идет. Даже если оно найдено - имеем затраты на изучение и освоение.

2) Конечно то что Вы показали в 100 раз мощнее того самопала что я написал - ну это нормально, чтобы достичь возможностей той либы нужны недели и больше (что я, Лубянку на приступ возьму? :)). Однако я потратил день (не так уж много) и, что важно, прекрасно знаю все детали своей реализации. А вот используя готовое - ну как-то "не очень". Да, достигается результат, да, эффективно, но.. реализация остается "черным ящиком", я "научился пользоваться", а как оно работает - да хз, работает. Это имеет свои минусы

Так что вопрос городить велосипед или нет всегда остается открытым

А за ссылочку конечно спасибо (чего раньше молчали?)

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

Да сам нашел ее в гугле минут за 10 до того как запостил. Просто помнил, что для обычных полигонов находили какие-то решения, но оно все нам не подходило. Сначала глядя на картинки здесь также подумал, что нужны ребра в виде дуг/безье....

Что же, тогда это говорит о том, что я просто просто не умею пользоваться поиском, т.к. на самом деле времени на поиск затратил очень много. Этот сайт мне не попадался.

Ну то уже "не совсем" полигоны. Было подобное (boolean фигур заданных кривыми Безье), решили расквантовать по отрезкам (с заданной пользователем точностью, выход все равно нужен был дискретный) а дальше дуст + свое творчество. Впрочем "малой кровью" все равно не вышло.

Не тот программист лучше кто лучше ищет :) Ну в данном случае - да, было, но стоит чуть-чуть изменить задачу - и запросто может не оказаться, это нормально

И всё же, имеет смысл опубликовать Ваше решение, Igors, в кладовой.

kamre, да, хорошо работает Clipper, спасибо.