Jak efektywnie obliczyć obrót figury?

Mam figurę reprezentowaną przez macierz bajtów (macierz bitmapowa). Przykładowy rysunek pokazano na Picture 1.

Celem jest znalezienie najlepszego kąta obrotu danej figury . Kiedy rysunek jest obracany o najlepszy kąt, prostokąt, który jest równoległy do ​​osi X i Y i wpisuje rysunek, ma najmniejsze pole.

Prostokąty opisujące figurę są pokazane jako jasnoszare na zdjęciach. Na ekranie Picture 2widać, że idealny obrót figury wynosi około 30 stopni w prawo.

Teraz znam algorytm, jak znaleźć ten kąt, ale wydaje mi się, że jest bardzo nieefektywny. Wygląda to tak:

1. Pętla przez kąty od 0 do 45.
2. Dla bieżącego kąta dla każdego punktu figury oblicz nową, obróconą lokalizację
3. Znajdź granice prostokąta zawierającego figurę (minimum i maksimum x, y) i zarejestruj go, jeśli do tej pory najlepiej pasował
4. Następny kąt

Jest to rodzaj metody brutalnej siły, która działa dobrze i dość szybko w przypadku małych postaci. Jednak muszę pracować z liczbami zawierającymi do 10 milionów punktów, a mój algorytm działa powoli.

Jaki byłby dobry algorytm dla tego problemu?

Wygląda na to, że można znaleźć dowolnie wyrównaną minimalną ramkę graniczną za pomocą algorytmu suwmiarki z czasem liniowym .

Po utworzeniu obwiedni wystarczy określić kąt obrotu, obliczając nachylenie jednego z boków.

Pierwszy krok twojego podejścia jest wadliwy - istnieje nieskończona liczba rzeczywistych wartości od 0 do 45, więc nie ma sensu „przechodzić przez nie”. Twój algorytm można jednak naprawić:

• znajdź wypukły kadłub wielokąta

• przejść przez skończoną (!) liczbę kątów podanych przez zewnętrzne krawędzie wypukłego kadłuba

• teraz zastosuj kroki od 2 do 4, używając tych kątów.

Działa to, ponieważ można wykazać, że minimalny prostokąt otaczający musi dotykać jednej z zewnętrznych krawędzi wypukłego kadłuba.