Найти дырки

[Igors]

Добрый день

Есть замкнутая полилиния (аттач), напр std::vector<QPointF>, сегменты которой могут совпадать но не само-пересекаться. Tребуется найти все контура дырок в виде индексов точек в исходной, напр

Код

C++ (Qt)
std::vector<std::vector<size_t>> FindHoles( const std::vector<QPointF> & poly );
 

Да, и вот интересно как (или насколько) "современный С++" здесь поможет, а то я делаю по-старинке, на индексах. Ну может там крутые хвункторы и все такое..

Текстовичок полилинии прикрепляю

Спасибо

[ssoft]

Вроде, не сложная задача).

Если заданы точки 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

То есть повторяющиеся точки - начало нового контура или линии между контурами.
Расставляем "скобки". Всё что внутри извлекаем, оставляя только одну точку.
В результате две точки - линия между контурами, больше двух - контур.

[ssoft]

Реализация может быть такой.

::std::unordered_map< Point, size_t > поможет! Только нужно определить ::std::hash для типа QPointF.

1. Для каждой точки посчитать количество вхождений в последовательность (сформировать ::std::unordered_map< QPointF, size_t >).
2. Итерировать одновременно справа и слева до точек с количеством включений больше 1.
    - если точки совпали, то контур или линию получили
    - если не совпали -- есть самопересечение!

[Igors]

Если заданы точки p1,p2,p3,p4,p5,p6,p4,p7,p8,p3,p9,p1 то контуры будут следующими

p1,p2,(p3,(p4,p5,p6,p4),p7,p8,p3), p9,p1

А где (злополучная) p1 - неизвестно. Напр она может принадлежать контуру дырки...

Вроде, не сложная задача).

Я тоже так думал 

[ssoft]

А где (злополучная) p1 - неизвестно. Напр она может принадлежать контуру дырки...

Не получается уловить контекст вопроса). Точка может быть сразу в нескольких контурах одновременно.

Исходная то задача какая? Сформировать контуры для отображения полигонов с дырами? Или просто независимые контуры получить?
Если контуры для отображения полигонов с дырами, то там ещё немного с ребрами поработать нужно, тогда можно будет определить, когда контур будет дыркой, а когда нет.

[Igors]

Не получается уловить контекст вопроса). Точка может быть сразу в нескольких контурах одновременно.

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

Исходная то задача какая?

Триангулировать "комплексные полигоны", т.е. с числом вертексов >= 5, задаются такой полилинией 

[RedDog]

Вот это не подойдет: https://libspatialindex.org/en/latest/

[Igors]

Вот это не подойдет: https://libspatialindex.org/en/latest/

Спасибо за ссылку, но что такое "spatial indexing", и чему это посвящено - хз

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

[ssoft]

Триангулировать "комплексные полигоны", т.е. с числом вертексов >= 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

[Igors]

А в чем трудность в триангуляции такого полигона? Вроде, никаких артефактов для таких форм не замечал.

Ну в как Вы триангулируете полигон на картинке выше ? Здесь как раз надо "искать готовые", велики типа "откусывания ушей" уже не катят. Я использую Шевчука (Джонатана Ричарда), когда-то смотрел и другие, но они тоже требуют указания "дырок".

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

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

И это будет работать если напр первая точка - правая нижняя на картинке. А вот если первая первая = верхней, то может и нет, внешний контур будет найден как дырка, а остаток (верхняя дырка) будет внешним. Анализировать все найденные контура чтобы убедиться какой же внешний - вероятно возможное решение, но выглядит длинным и мутным. Нет ли чего  попроще/получше ?

[ssoft]

Ну в как Вы триангулируете полигон на картинке выше?

Пользуюсь средствами GLUtessellator.

[Igors]

Пользуюсь средствами GLUtessellator.

Насколько помню, и там контура дырок надо задавать, внешний CCW, дырки CW (или наоборот). Указание дырок так или иначе неизбежно, иначе это могут быть просто ребра.

Как я сделал. Собсно все как Вы и сказали, только еще выбор стартовой точки:

1) Нахожу 4 точки max/min X/Y. Они точно лежат на внешнем контуре. Убираю повторы, остается минимум 2 точки

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

Правда это не учитывает 3 и более совпадений (для одной точки), на это забил, не хватило терпения 

Кстати в триангуляторе Шевчука дырка задается одной точкой, поэтому потом еще требуется найти точку внутри дырки. Для этого привлекается пресловутый дуст - объективно страшно избыточное решение 

[qtkoder777]

Как-то так
1) Стороны потенциальной дырки не пересекают какой-нибудь контур. Их может быть несколько.
2) Из точки, лежащей заведомо внутри контура дырки, выпускаем луч. Найденный в 1) контур луч пересечёт нечётное число раз. Всё.