SVG/Convex Hull

Este artigo é um ensaio para a elaboração de uma proposta de extensão ao padrão Svalable Vector Graphics, da W3C.

definição e premissas

A funcionalidade em questão é a habilidade de, dado um conjunto de geometrias vetoriais, computar geometria vetorial resultante da operação conhecida como Convex Hull, ou Envoltória Convexa.

Essa operação só se aplica a geometrias fechadas. Me parece natural que para o caso de geometrias definidas por curvas abertas seja considerada a geometria fechada resultante da adição de um segmento de reta unindo o ponto inicial ao ponto final da curva original.

TODO: adicionar uma imagem aqui representando a equivalência sugerida entre curvas abertas e curvas fechadas, para o cômputo de envoltórias convexas

A Envoltória Convexa de um conjunto de curvas fechadas, é definida como a curva convexa de menor área posível que contenha todas as curvas do conjunto.

A figura a seguir, contém a representação de (a) um conjunto arbitrário de curvas fechadas e (b) o resultado do cômputo da envoltória convexa deste conjunto de curvas.

TODO: adicionar uma imagem aqui

implementações existentes

OpenSCAD

O software CAD de modelagem algoritmica e paramétrica OpenSCAD implementa a operação de envoltória convexa por meio do módulo hull(){ ... }.

Exemplo

Segue abaixo um exemplo de uso desta funcionalidade. O script abaixo descreve uma geometria composta por um círculo de raio 50 posicionado na origem do sistema de coordenadas e um circulo maior, de raio=80, posicionado na coordenada x=160,y=0.

circle(r=50);
translate([160,0]) circle(r=80);

A imagem abaixo demonstra a renderização desta geometria inicial.

TODO: adicionar imagem.

O script abaixo computa a envoltória convexa dessa mesma geometria inicial.

hull(){
  circle(r=50);
  translate([160,0]) circle(r=80);
}

Pode-se ver na imagem a seguir o resultado gráfico da operação de envoltória convexa.

TODO: adicionar imagem.