Primeiramente, até que enfim um tópico mais algorítmico!
“Segundamente”, oi.
[quote=Jokabeludoido]Olá…
Essa semana implementei um algoritmo intuitivo para determinar o envelope convexo de uma determinada nuvem de pontos dispotos sobre um plano bidimensional…Para quem não está familiarizado com o problema, o envelope convexo de uma nuvem de pontos é o meno conjunto de pontos que descreve um polígono convexo cuja área contém todos os outros pontos da nuvem…Esse algoritmo tem diversas aplicações. Pode ser usado, inclusive na otimização linear, para determinar o limites de um determinado conjunto de soluções de uma função de otimização…[/quote]
Existem maneira mais fáceis de se calcular o limite. No plano 2D, é mais fácil determinar a região de factibilidade e calcular o vértice da solução otima. Essa é a melhor solução. As outras, que são boas, mas não as ótimas, podem ser determinadas usando a equação da reta - basta você saber quais retas estão formando um vértice.
Isso não responde a sua dúvida, mas se você está tentando fazer esse negócio do polígono, o que falei acima acredito que já resolva (não tenho certeza).
[quote=Jokabeludoido]Bem…Meu algoritmo já está funcionando. De uma menira pouco otimizada ainda, mas já estou trabalhando nisso…Minha dúvida é a seguinte. Meu algoritmo já devolve o conjunto de pontos que forma esse envelope convexo, só que eu gostaria de plotar esse envelope, ligando os pontos através de retas, de modo que eu pudesse apresentar um polígono. Só que eu esbarrei em um problema aparentemente trivial, mas cuja resolução me escapa completamente. Dado um conjunto de pontos que descreve um polígono convexo, como ordenar tais pontos de modo que, se eu desenhar uma reta entre dois pontos em sequência, eu obtenha no final um polígono?
Obrigado, desde já…[/quote]
Eu resolvi um problema que achei bastante parecido com o que você precisa. É assim: dado um plano e um conjunto de pontos, determinar o tamanho máximo do lado de um quadrado quando se expande todos os pontos para os lados direito e esquerdo e para cima e para baixo. Eu tinha bolado uma solução de simulação, mas ficaria pouco eficiente. O que você pode fazer (que foi o que cheguei a fazer depois): ordenar pelo “x” e depois pelo “y”. Depois disso, você liga o primeiro ponto com o último.
Não tenho ideia se isso funciona. Mas para resolver o problema que falei, bastou. Se você tiver alguma outra ideia (ou se o que falei pode ter clareado um pouco mais a sua mente), fala aí que nós podemos trabalhar em cima dela.
Além disso, eu aconselho você a dar uma lida em Convex Hull. Não acredito que seja a resposta, mas pode dar algumas novas ideias.
Abraço.
