Eu tenho uma figura representada através de uma matriz de bytes (matriz semelhante a bitmap). Exemplo A figura é mostrada no Picture 1.
O objetivo é encontrar o melhor ângulo de rotação de alguma figura . Quando a Figura é girada pelo melhor ângulo, o retângulo paralelo aos eixos X e Y e inscreve a Figura possui a menor área.
Os retângulos que inscrevem a figura são mostrados em cinza claro nas figuras. No Picture 2, você pode ver que a rotação ideal da figura é de cerca de 30 graus no sentido horário.
Agora, eu sei algoritmo como encontrar esse ângulo, mas parece-me que é muito ineficiente. É assim:
- Faça um loop pelos ângulos de 0 a 45.
- Para o ângulo atual, para cada ponto da figura, calcule o novo local girado
- Encontre os limites do retângulo que contém a figura (mínimo e máximo x, y) e registre-o se for a melhor correspondência até o momento
- Próximo ângulo
Esse é um tipo de método de força bruta e funciona bem e razoavelmente rápido para as pequenas figuras. No entanto, preciso trabalhar com números que contenham até 10 milhões de pontos e meu algoritmo se torna lento.
Qual seria um bom algoritmo para esse problema?
fonte
O primeiro passo da sua abordagem é falho - há um número infinito de valores reais entre 0 e 45, portanto, não faz sentido "percorrê-los". No entanto, seu algoritmo pode ser reparado:
encontre o casco convexo do polígono
loop através do número finito (!) de ângulos dados pelas arestas externas do casco convexo
agora aplique as etapas 2 a 4 usando esses ângulos.
Isso funciona porque pode ser demonstrado que o retângulo mínimo envolvente deve tocar uma das arestas externas do casco convexo.
fonte