Polígono no problema de generalização de polígono

9

Gostaria de me desculpar por todos os posts abaixo. Escolheu o fórum errado para postar isso originalmente. No entanto, em vez de tornar isso um desperdício completo, refiz a pergunta como um verdadeiro problema "Ciência da Computação Teórica".

Problema: Crie um algoritmo que utilize um conjunto de n pontos ordenados em um plano 2D que forma o contorno de um polígono simples A que pode ou não ser côncavo e cria um novo polígono B com m pontos, tais como:

  1. todos os pontos em A estão contidos em B
  2. 3 <= m <n
  3. B é o polígono no conjunto de todas as Bs com a menor área
  4. B deve ser um polígono simples (ou seja, sem auto-interseções).
  5. A entrada para o algoritmo é o polígono A e "m".
  6. A coincidência de segmentos em B com segmentos em A é permitida.

Alguns exemplos de entradas e saídas esperadas:

  1. Se A é um quadrado e m é 3, então B seria o triângulo com a menor área de superfície que contém A.
  2. Se A é um hexágono e m é 4, então B seria um quadrilátero com a menor área de superfície que contém A.

Boa sorte a todos que tentam esse problema. Posso prometer que isso será muito difícil, especialmente agora que a solução deve ser ótima.

ds.algorithms cg.comp-geom polygon Thirlan
fonte
11
@ Joe: Não é verdade: se A é um quadrado, Thirian está pedindo o triângulo da área mínima contendo A. Por outro lado, se A é um triângulo ( ), na verdade não há solução válida. n=3
Jeffε
3
Adicione 17 ao meu primeiro comentário, eu acho. Por que 20?
Jeffε
3
A FFT não é um limite baixo para "complicado"?
Sasho Nikolov
2
Eu não acho que seja totalmente verdade que o problema não mude se você (m) definir m = 3. O problema é que você pode exigir tempo exponencial em m, e isso é bom se m estiver fixo em algum número, mas não é bom se m fizer parte da entrada.
Suresh Venkat
5
"todo mundo sabe qual é o problema" não é verdade. Estamos perguntando porque as opções não especificadas fazem a diferença.
Suresh Venkat

Respostas:

10

Não sei como são os seus polígonos, mas talvez seja suficiente uma versão simplificada do algoritmo de Ramer-Douglas-Peucker :

  • para cada parte convexa , calcule a área dos triângulos P i P i + 1 PAj formados por três pontos consecutivos;PiPi+1Pi+2
  • para cada parte côncava , calcule a área dos dois triângulos P i P ′ i P i + 1 e P i + 1 P ′ i + 2 P i +BkPiPi′Pi+1 formada pelo prolongamento dos dois pontos P i , P i + 2 e o ponto do meioPi+1Pi+2′Pi+2Pi,Pi+2Pi+1
  • calcule o e exclua o ponto correspondente (e os pontos de mudança se a operação for realizada na parte côncava);min{Aj,Bk}
  • até que pontos sejam excluídos.n−m

insira a descrição da imagem aqui
A borda do polígono ( triângulos verdes, B k triângulos vermelhos). À direita, a fronteira após a eliminação de dois pontos.AjBk

Para algoritmos mais complexos, você pode procurar por " técnicas de generalização de polígonos ", embora sua primeira condição (os pontos A estejam contidos em B) implique algumas operações adicionais de dimensionamento.

Marzio De Biasi
fonte
@Suresh: Eu tenho certeza que os atuais 4 upvotes são para a transparência, não para o algoritmo (quase trivial) :)
Marzio De Biasi
11
Isso sofre do mesmo problema que os algoritmos de Ramer-Douglas-Peucker: Não é garantido que a saída seja um polígono simples!
Jeffε
11
@ Jeffe: você está certo, mas (longe de ser o ideal se o polígono for complexo), pode-se evitar simplificações que levam a um conflito . No final, se houver outros pontos a serem removidos, mas o polígono não simples não puder ser evitado, use um método de resolução de conflitos (por exemplo, calcule pontos de interseção e descarte completamente os "orifícios"). No entanto, eu gostaria de ver um exemplo real do OP.
Marzio De Biasi
11
@MarzioDeBiasi Isso pode funcionar. Mas talvez não. Eu acho que é possível que toda simplificação que você descreve cause uma auto-interseção. E "jogar loops" pode piorar as coisas, não melhorar. Esta é provavelmente uma boa solução na prática, mas lembre-se de onde estamos!
Jeffε
Obrigado Marzio, agora pelo menos sei como são chamados esses tipos de problemas agora! Infelizmente, a solução que você deu é o que (3) e (4) estão nas minhas soluções sugeridas e (4) tem um problema com isso. Elipses muito alongadas e, portanto, com pontas afiadas com ângulos de aproximadamente 30 graus ou menos, violam facilmente o requisito (1).
Thirlan #
6

Escrevi há muito tempo um artigo que detalhava um algoritmo de tempo linear para encontrar o menor triângulo de área envolvendo um conjunto de pontos (ou um polígono):

J. O'Rourke, Alok Aggarwal, Sanjeev Maddila, Michael Baldwin, "Um algoritmo ideal para encontrar triângulos de fechamento mínimos", J. Algorithms , 1986, 7 : 258--269. Link .

Nosso trabalho foi seguido por um algoritmo geral:

"Polígonos de circunscrição mínima de área", Alok Aggarwal, JS Chang e Chee K. Yap, O Computador Visual , Volume 1, Número 2 (1985), 112-117. Link .

Você pode usar o Google Scholar para rastrear os documentos posteriores que os citam para encontrar melhorias e trabalhos relacionados.

Joseph O'Rourke
fonte