Método para combinar quadrados de azulejos definidos como pontos em vetores

Question

Se eu tile os quadrados e os quadrados podem ser definidos por suas coordenadas, como posso simplificar as formas feitas de vários quadrados em vetores que definem cada borda de toda a forma? Pseudo-código ou termos gerais estão bem.

Answer 1

A primeira coisa que consigo pensar é (provavelmente não é a maneira mais eficiente):

1) Obtenha a caixa delimitadora de todo o seu ladrilho - que é min (x), min (y) para max (x), max (y) para todos os x e y de seus ladrilhos

2) Para cada linha, comece com o estado == vazio, itera sobre cada coluna: o estado muda para cheio quando você acertar um quadrado e vazio quando encontrar um orifício. Toda vez que o estado vai de vazio para cheio, salve o segmento de linha esquerda daquele quadrado e, toda vez, o estado vai de cheio a vazio, salve o segmento da linha direita daquele quadrado.

3) Repita acima no eixo y

Agora você tem um conjunto contendo apenas os segmentos de linha mais externos, você pode combinar aqueles que são co-lineares etc. e obter a forma geral.

Isso funcionará para formas não convexas e também se você tiver orifícios em seu ladrilho.