Existe um algoritmo para encontrar um casco quase convexo, dado um ângulo de tolerância?

Gostaria de saber se existe um algoritmo que, dado um conjunto de pontos e um ângulo, calcule o casco convexo se o ângulo for e se calcule um envelope que segue mais de perto o "perímetro " $\alpha = 0$ $\alpha > 0$

$Ilustração do efeito de tamanho $ \ alpha $$

E se houver uma definição de um perímetro sem interseção de um conjunto de pontos, nesse caso, o polígono resultante quando for grande. $\alpha$

Outra visão do problema pode ser encontrar um algoritmo que possa ser parametrizado para encontrar para a solução de perímetro mínimo (casco convexo) e para (normalizado) a polilinha de área mínima envolvendo todos os pontos. $\alpha = 0$ $\alpha = 1$

algorithms computational-geometry naufraghi
fonte

Você já olhou para o conceito de conjuntos fortemente convexos ?

Deathbreath

Você poderia esclarecer o propósito de ? Que finalidade serve?

α

$\alpha$

Paul

Seria permitido propor um algoritmo que funcione mais à medida que cresce? Ou você esperava que o aumento de diminuísse a complexidade "esperada"?

α

$\alpha$

α

$\alpha$

hardmath

Eu pretendia isso como o ângulo em que o algoritmo pode se afastar do casco convexo. E não, acho que não diminuirá a complexidade.

23412 naufraghi

Respostas:

Você pode investigar o chamado casco alfa , por exemplo: pacote CRAN , Wikipedia sobre formas alfa :
insira a descrição da imagem aqui
_{[Imagem deste link .]}

O casco alfa tem propriedades geométricas muito agradáveis e tem sido muito estudado, mas ainda pode não servir a seus propósitos.

Joseph O'Rourke
fonte

Obrigado, as formas alfa são muito interessantes, elas têm um superconjunto das propriedades que eu estava procurando (estou interessado apenas em um único envelope) e a implementação não é comparável à do casco convexo. Vou esperar um pouco mais, se alguém puder sugerir algo mais simples; caso contrário, eu aceito esta resposta.

naufraghi

$\alpha$

Gostaríamos de pensar um pouco na estrutura de dados que tornaria eficiente a localização dos pontos especificados. Uma idéia seria calcular uma caixa delimitadora para cada segmento e compará-la com uma lista classificada dos pontos.

hardmath
fonte