Como desenhar o contorno de um grupo de vários retângulos?

Question

Preciso desenhar um polígono envolvente de um grupo de retângulos colocados um ao lado do outro.

Vamos pensar em campos de texto que compartilham pelo menos uma aresta (ou parte dela) com pelo menos um dos outros retângulos.Posso obter as coordenadas dos pontos dos retângulos e, basicamente, tenho todos os dados necessários sobre eles.

Você consegue pensar em um algoritmo/procedimento simples para desenhar um polígono (caminhos retos conectados) em torno desses objetos.

Aqui está uma demonstração de diferentes casos potenciais (A, B, C, etc...).No exemplo A também desenhei um polígono azul que é o caminho que preciso desenhar, delineando o grupo de retângulos.

Eu li aqui sobre casco convexo e coisas assim, mas na verdade, isso parece um problema muito mais simples.Uma solução (início) que pensei foi que os pontos que realmente preciso desenhar são apenas aqueles que não são compartilhados por nenhum par de retângulos, o que significa que pontos que são vértices de mais de um retângulo são redundantes.O que não consegui descobrir foi a ordem pela qual preciso traçar linhas de uma para a outra.

Atualmente trabalho no objetivo c, mas qualquer outra linguagem ou algoritmo seria apreciado, incluindo pseudo.

Obrigado!

Answer 1

IMHO Deve ser assim.Faça uma lista de gumered e veja se alguns estão sobrepostos: isso deve ser simples se os retângulos estiverem alinhados com o eixo X, Y.Você acabou de encontrar as bordas que têm os vértices no mesmo x ou y e as outras coordenadas precisam estar entre.Depois disso, as bordas restantes devem formar o contorno.

Outro método para encontrar arestas comuns é quebrar todos os retângulos ao longo de cada eixo X e Y, onde você tem vértices.Isso deve parecer como se você estivesse crescendo todas as linhas para o infinito.Depois disso, todas as bordas comuns terão vértices comuns e podem ser eliminados.

Answer 2

Você tem duas linhas e três diferentes y-valores.Digamos y0 é o topo da coisa, y2 é a extremidade inferior e y1 marca o meio entre as duas linhas.
Cada linha tem um valor x máximo e mínimo, digamos que a linha superior vai de x0_min para x0_max, e a linha inferior de x2_min para x2_max.Dados esses valores, você apenas desenha em torno da coisa:

(x0_min,y0)->
(x0_max,y0)->
(x0_max,y1)->
(x2_max,y1)->
(x2_max,y2)->
(x2_min,y2)->
(x2_min,y1)->
(x0_min,y1)->
(x0_min,y0)