0 E se houver uma definição de um perímetro sem interseção de..."/>

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

9

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 "α=0 0α>0 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.α

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.α=0 0α=1 1

naufraghi
fonte
Você já olhou para o conceito de conjuntos fortemente convexos ?
Deathbreath
Você poderia esclarecer o propósito de ? Que finalidade serve? α
Paul
Seria permitido propor um algoritmo que funcione mais à medida que cresce? Ou você esperava que o aumento de diminuísse a complexidade "esperada"? αα
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:

3

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
1

α

α

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