Qual é a vantagem de usar o Half Edge sobre o Winged Edge?

Para representação de malha, qual é o benefício de usar a meia borda sobre a estrutura de dados do Winged Edge?

Entendo as duas representações de malha, a única diferença é que a meia borda usa a borda direcional e a borda com asas usa a borda não-direcional. Até agora, não consigo pensar em qual é a utilidade de usar a borda direcional, mas isso apenas fornece mais consumo de memória.

Até onde eu sei, a principal vantagem da meia borda é que a travessia pode ser um pouco mais simples devido à garantia de que as bordas tenham uma orientação consistente em cada face.

Considere o problema de iterar sobre todos os vértices ou arestas de uma determinada face, no sentido anti-horário. Na estrutura de meia borda, isso pode ser feito iniciando com uma meia borda arbitrária dessa face e simplesmente seguindo os ponteiros "próximos" até voltar ao ponto em que começou.

Por outro lado, fazer isso em uma estrutura de borda alada é um pouco chato, porque as bordas são orientadas arbitrariamente; qualquer borda que você encontrar pode apontar no sentido horário ou anti-horário em relação à face que você está tentando percorrer, portanto, você deve fazer uma verificação condicional extra a cada etapa para ver se deve atravessar a borda atual para frente ou para trás.

Outros tipos de consultas de conectividade se comportam de maneira semelhante: a versão de meia borda permite seguir os links em uma sequência consistente, enquanto a versão de ponta alada exige verificações de orientação a cada etapa.

Se os condicionais são realmente um problema de desempenho para borda alada provavelmente dependerá de outros fatores. Para uma implementação "ingênua" com ponteiros de todas as formas e dados espalhados pela memória, eu esperaria que a sobrecarga da falta de cache inundasse qualquer efeito dos condicionais. Por outro lado, se você tiver uma estrutura de dados compactada com tudo quente no cache, poderá ver alguns efeitos dos condicionais devido a previsões incorretas de ramificações etc. É difícil dizer.

Deixando o desempenho sozinho, eu preferiria o meio-fio apenas porque parece mais fácil pensar e escrever o código correto, mesmo que isso resulte em uma leve sobrecarga de memória.

A propósito, existem algumas outras opções de design com estruturas de dados de malha que geralmente parecem confundidas com essa. Um comentarista mencionou a vinculação simples versus dupla, mas, naturalmente, você pode fazer a vinculação única ou dupla com a borda meia ou a borda alada. (Embora eu não veja como a vinculação única com a borda com asas funcionaria, já que, como mencionado acima, você pode precisar atravessar as bordas para trás ou para frente no decorrer de uma consulta.)

Além disso, há a questão de saber se as estruturas de vértice e face armazenam uma lista de todas as suas arestas, ou apenas uma (e requer que você as atravesse para encontrar o restante). Ter uma lista de arestas de comprimento variável por vértice / face complica consideravelmente a lógica se você deseja fazê-lo com eficiência (por exemplo, não ter uma alocação de heap separada por vértice / face), mas, novamente, isso é independente de as arestas serem de meia aresta ou borda alada.