Группировка перекрывающихся фигур (x, y)
Мои алгоритмы поиска перекрывающихся прямоугольников (областей) с использованием координат x-y (нижний левый угол, верхний правый угол) работают нормально. Но мой алгоритм группировки перекрывающихся друг с другом не работает. Может кто-нибудь сказать, пожалуйста, что я делаю не так?
Моя программа читает в координатах x-y из файла .txt, такого как этот …
0 5 3 6 (0,5 is bottom left corner and 3,6 is top right corner)
2 7 8 9 (2,7 is bottom left corner and 8,9 is top right corner)
а затем выясняет, какие все группы имеют перекрывающиеся прямоугольники, и распечатывает группы.
т.е. прямоугольник 0 перекрывает 2, 2 перекрывает 1 и 1 перекрывает 5. Это означает, что прямоугольники 0, 2, 1 и 5 все находятся в 1 группе, так что я могу распечатать эту группу # 1.
то есть прямоугольники 4 и 3 перекрываются, что означает, что прямоугольники 4 и 3 находятся в группе № 2.
то есть прямоугольник 10 перекрывает 11, а прямоугольник 11 перекрывает прямоугольник 12. Это означает, что все прямоугольники 10, 11 и 12 находятся в группе № 3, так что я могу аккуратно распечатать это.
Решение
Из того, что я понимаю, вам нужно реализовать структуру данных union-find для хранения связанных компонентов. Это именно то, что вы намерены. Для более подробного объяснения вы должны прочитать этот вопрос: Объединение найти структуру данных
Используя упомянутый код, вам нужно сделать следующее:
UF uf( n ); // create and initialize a UF. n is the number of rectangles you have
if ( two rectangles overlap ){
if ( ! connected( rectangleId1, rectangleId2 ) ){ // if they aren't already in the same component
merge( find(rectangleId1), find(rectangleId2) ); // put them in the same component
}
}
После этого каждый прямоугольник с тем же значением для find( rectangleId ) принадлежат к одному и тому же компоненту.
Другие решения
Других решений пока нет …