Estou trabalhando em um problema de otimização para encontrar uma região que maximize uma certa função objetivo, estou usando um conjunto de coordenadas de pixel para manter o controle da região, e para cada passo adicionarei ou removerei um pixel no limite para ver se a função objetivo aumenta ou não. Espero que a região seja conectada, há alguma estrutura de dados que possa decidir rapidamente se remover um pixel tornaria a região desconectada? Aqui, assumimos que um pixel está conectado a seus quatro vizinhos.
E uma pergunta paralela: e se eu esperar que a região seja sempre simplesmente conectada? Por simplesmente conectada, quero dizer que não há buraco, e adicionar um pixel pode criar um buraco.
Você pode olhar para a configuração de uma vizinhança 3x3 antes e depois de remover um pixel (ou adicionar um pixel) e decidir se essa ação mudará a característica de Euler do objeto ao qual está conectado. A característica de Euler informa quantos objetos e quantos buracos existem.
Se houver entre 1 e 7 pixels definidos na vizinhança 3x3, excluindo o pixel central, e eles estiverem simplesmente conectados, adicionar ou remover esse pixel central não alterará a característica de Euler (ou seja, não adicionará/removerá um buraco ou adicionará/removerá um objeto), assumindo um objeto com 8 conexões (para um objeto com 4 conexões, há menos configurações para as quais isso é verdade, é fácil resolvê-las).
Normalmente, você teria uma tabela com as 256 configurações possíveis desses 8 pixels, você codifica a configuração como um índice na tabela (por exemplo, indo no sentido horário começando no pixel superior esquerdo, lendo os pixels como um número binário de 8 dígitos). Então é muito rápido verificar se você pode remover (ou adicionar) um pixel em um determinado local.
Procure uma implementação padrão do algoritmo de esqueletização ou do afinamento morfológico. Essas duas operações realizam exatamente essa mesma verificação em cada pixel antes de removê-lo, ambas precisam preservar a característica de Euler. Por exemplo, veja esta tabela em scikit-image .