Название: Найти дырки Отправлено: Igors от Июнь 09, 2021, 10:33 Добрый день
Есть замкнутая полилиния (аттач), напр std::vector<QPointF>, сегменты которой могут совпадать но не само-пересекаться. Tребуется найти все контура дырок в виде индексов точек в исходной, напр Код
Да, и вот интересно как (или насколько) "современный С++" здесь поможет, а то я делаю по-старинке, на индексах. Ну может там крутые хвункторы и все такое.. Текстовичок полилинии прикрепляю Спасибо Название: Re: Найти дырки Отправлено: ssoft от Июнь 09, 2021, 12:00 Вроде, не сложная задача).
Если заданы точки p1,p2,p3,p4,p5,p6,p4,p7,p8,p3,p9,p1 то контуры будут следующими p1,p2,(p3,(p4,p5,p6,p4),p7,p8,p3), p9,p1 p4,p5,p6,p4 p3,p4,p7,p8,p3 p1,p2,p3,p9,p1 То есть повторяющиеся точки - начало нового контура или линии между контурами. Расставляем "скобки". Всё что внутри извлекаем, оставляя только одну точку. В результате две точки - линия между контурами, больше двух - контур. Название: Re: Найти дырки Отправлено: ssoft от Июнь 09, 2021, 12:13 Реализация может быть такой.
::std::unordered_map< Point, size_t > поможет! Только нужно определить ::std::hash для типа QPointF. 1. Для каждой точки посчитать количество вхождений в последовательность (сформировать ::std::unordered_map< QPointF, size_t >). 2. Итерировать одновременно справа и слева до точек с количеством включений больше 1. - если точки совпали, то контур или линию получили - если не совпали -- есть самопересечение! Название: Re: Найти дырки Отправлено: Igors от Июнь 09, 2021, 12:46 Если заданы точки p1,p2,p3,p4,p5,p6,p4,p7,p8,p3,p9,p1 то контуры будут следующими А где (злополучная) p1 - неизвестно. Напр она может принадлежать контуру дырки...p1,p2,(p3,(p4,p5,p6,p4),p7,p8,p3), p9,p1 Вроде, не сложная задача). Я тоже так думал :)Название: Re: Найти дырки Отправлено: ssoft от Июнь 09, 2021, 13:49 А где (злополучная) p1 - неизвестно. Напр она может принадлежать контуру дырки... Не получается уловить контекст вопроса). Точка может быть сразу в нескольких контурах одновременно. Исходная то задача какая? Сформировать контуры для отображения полигонов с дырами? Или просто независимые контуры получить? Если контуры для отображения полигонов с дырами, то там ещё немного с ребрами поработать нужно, тогда можно будет определить, когда контур будет дыркой, а когда нет. Название: Re: Найти дырки Отправлено: Igors от Июнь 09, 2021, 14:15 Не получается уловить контекст вопроса). Точка может быть сразу в нескольких контурах одновременно. Вы исходите из предположения что (стартовая) p1 - точка "внешнего" контура, тогда последующие совпадающие точки обозначат дырки. Но такое предположение часто оказывается неверным, т.е. Вы можете просто "начвть с дырки"Исходная то задача какая? Триангулировать "комплексные полигоны", т.е. с числом вертексов >= 5, задаются такой полилинией Название: Re: Найти дырки Отправлено: RedDog от Июнь 09, 2021, 14:31 Вот это не подойдет: https://libspatialindex.org/en/latest/
Название: Re: Найти дырки Отправлено: Igors от Июнь 09, 2021, 14:42 Вот это не подойдет: https://libspatialindex.org/en/latest/ Спасибо за ссылку, но что такое "spatial indexing", и чему это посвящено - хз :)Понимаю что использовать накопленный опыт - это правильно, иначе человечество и сейчас ютилось бы в пещерах. Но елы-палы, все же все хорошо в меру. Почему "поиски готового" начинаются даже без всяких попыток шевельнуть (слабеющей) мозгой? Может "просто сделать" намного проще и быстрее чем чего-то искать, а потом еще "прикручивать" ? Название: Re: Найти дырки Отправлено: ssoft от Июнь 09, 2021, 14:56 Триангулировать "комплексные полигоны", т.е. с числом вертексов >= 5, задаются такой полилинией А в чем трудность в триангуляции такого полигона? Вроде, никаких артефактов для таких форм не замечал. Разве что если специальное сглаживание границ производится. В любом случае, если решать "в лоб", то определить, находится ли один контур внутри другого, можно с помощью простой проверки - находится ли любая точка одного контура внутри геометрии другого. Можно ещё через анализ ребер определить, но тут подумать нужно)... А если кидаться ссылками, то можно здесь что-то полезное почерпнуть https://doc.cgal.org/latest/Manual/packages.html#PartPolygons https://doc.cgal.org/latest/Straight_skeleton_2/Straight_skeleton_2_2Create_skeleton_and_offset_polygons_2_8cpp-example.html Название: Re: Найти дырки Отправлено: Igors от Июнь 10, 2021, 11:10 А в чем трудность в триангуляции такого полигона? Вроде, никаких артефактов для таких форм не замечал. Ну в как Вы триангулируете полигон на картинке выше ? Здесь как раз надо "искать готовые", велики типа "откусывания ушей" уже не катят. Я использую Шевчука (Джонатана Ричарда), когда-то смотрел и другие, но они тоже требуют указания "дырок".В любом случае, если решать "в лоб", то определить, находится ли один контур внутри другого, можно с помощью простой проверки - находится ли любая точка одного контура внутри геометрии другого. Так контура-то надо иметь, т.е. сначала выделить. Вы предложили простой и естественный способ - ищем контур по совпадению точек. Каждая пара - дырка, они могут быть вложены друг в друга. То что осталось - внешний контур. И это будет работать если напр первая точка - правая нижняя на картинке. А вот если первая первая = верхней, то может и нет, внешний контур будет найден как дырка, а остаток (верхняя дырка) будет внешним. Анализировать все найденные контура чтобы убедиться какой же внешний - вероятно возможное решение, но выглядит длинным и мутным. Нет ли чего попроще/получше ? Название: Re: Найти дырки Отправлено: ssoft от Июнь 11, 2021, 07:36 Ну в как Вы триангулируете полигон на картинке выше? Пользуюсь средствами GLUtessellator. Название: Re: Найти дырки Отправлено: Igors от Июнь 11, 2021, 11:00 Пользуюсь средствами GLUtessellator. Насколько помню, и там контура дырок надо задавать, внешний CCW, дырки CW (или наоборот). Указание дырок так или иначе неизбежно, иначе это могут быть просто ребра.Как я сделал. Собсно все как Вы и сказали, только еще выбор стартовой точки: 1) Нахожу 4 точки max/min X/Y. Они точно лежат на внешнем контуре. Убираю повторы, остается минимум 2 точки 2) Каждую из найденных проверяю - есть ли совпадающая с ней. Если нет, точка сразу считается стартовой. Иначе из 2 возможных контуров выбирается тот на котором лежит вторя внешняя точка. Ну и совпадение для стартовой дыркой не считаем - это внешний контур Правда это не учитывает 3 и более совпадений (для одной точки), на это забил, не хватило терпения :) Кстати в триангуляторе Шевчука дырка задается одной точкой, поэтому потом еще требуется найти точку внутри дырки. Для этого привлекается пресловутый дуст - объективно страшно избыточное решение :) Название: Re: Найти дырки Отправлено: qtkoder777 от Сентябрь 27, 2021, 12:50 Как-то так
1) Стороны потенциальной дырки не пересекают какой-нибудь контур. Их может быть несколько. 2) Из точки, лежащей заведомо внутри контура дырки, выпускаем луч. Найденный в 1) контур луч пересечёт нечётное число раз. Всё. |