Определение, будет ли удаление вокселя разбивать группу

У меня следующая ситуация: у меня есть 3d сетка вокселей (вкл / выкл, максимальный размер, вероятно, 128x128x128). Я заранее знаю, что внутри сетки все включенные воксели взаимосвязаны, образуя единую группу.

Теперь мне нужно определить: когда я удаляю воксель (выключаю его), он разрушит группу?

Моя первоначальная идея состояла в том, чтобы посмотреть на соседей удаляемого вокселя и определить, связаны ли они через другие воксели (см. Мой другой вопрос: алгоритм, чтобы увидеть, связаны ли два вокселя ). Но могут быть и другие / лучшие способы сделать это.

Итак, что будет хорошим способом определить, разрушит ли удаление вокселя группу, в которую он входил?

Я несколько об этом рассказал в своем другом комментарии, но я думаю, что здесь вы думаете о внешней / внутренней классификации. Удаляя воксель, вы превращаете воксели вокруг него в «крайние» воксели (если они еще не были). Это должно сводиться к трем фактическим случаям (симметрия дает вам остальные из них) - в приведенном ниже примере числа - это идентификаторы группы, - - удаляется воксель

11      2    
1-     1-     1-2

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

• Второй случай: это угол, и удаленный воксель отключил вышеупомянутые и оставленные воксели, которые были ранее подключены

• Третий случай: это линия, и удаленный воксел отключил ранее подключенные левый и правый воксели.

Если вы определили, что 2-й или 3-й случаи произошли, вам нужно выполнить поиск пути, чтобы увидеть, все ли 1 и 2 все еще связаны через другие смежные воксели.

Вы можете получить некоторую эффективность здесь, хотя. Если воксель является полностью внутренним по отношению к группе (то есть все 8 его соседей являются частью одной и той же группы), то его можно сбрасывать со счетов. Почему? Это топология. Представьте себе 2D-случай - есть только две возможности. Либо есть единственное ребро, которое, независимо от того, как оно крутится и поворачивается, все еще образует кольцо вокселей. Или есть два кольца, одно из которых содержит один воксел, а другое содержит другое. Например:

 xxx xxx
 x x-x x
 xxx xxx

или

 xxxxxxx
 x     x
 xxx xxx
   x-x 
 xxx xxx

Это должно распространяться и на 3D, за исключением того, что вместо граничного кольца у вас будет граничная поверхность. Поэтому, когда вы пытаетесь определить, все ли два недавно отключенных вокселя все еще связаны, вы можете исключить все внутренние воксели из своего обхода, потому что по определению, если воксел подключен к любому из граничных вокселей группы, это также подключен ко всем внутренним вокселям в этой группе.

Это своего рода обратный эффект вокселей-концентраторов, о которых я говорил в своем ответе на другой вопрос - вам не нужно искать путь от каждого вокселя до каждого другого вокселя, вам нужно только найти путь к интересным вокселям.

Если вы используете A *, вы можете использовать его здесь.

Начиная со списка вокселей, которые были подключены к удаленному вокселю. Начните с первого в списке, используйте A *, чтобы найти путь ко второму в списке. Если путь существует, найдите путь со второго по третий, с третьего по четвертый и так далее.

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

Это должно быть довольно легко реализовать, если у вас уже реализована функциональность A *.