QPolygonF - сжатие (inflate)

[alexis031182]

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

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

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

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

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

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

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

[Igors]

Мне точно минимум неделю разбираться в коде, как оно там работает, но то что результат нужный - факт!

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

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

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

[alexis031182]

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

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

"В принципе" все довольно просто:

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

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

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

[Igors]

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

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

[alexis031182]

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

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

[Igors]

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

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

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

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

[alexis031182]

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

[Igors]

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

[alexis031182]

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

[kamre]

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

Плохо искали, для обычных полигонов есть как минимум Clipper.

[Igors]

Плохо искали, для обычных полигонов есть как минимум Clipper.

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

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

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

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

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

[kamre]

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

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

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

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

[alexis031182]

Плохо искали, для обычных полигонов есть как минимум Clipper.

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

[Igors]

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

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

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

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

[alexis031182]

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