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:
- Pętla przez kąty od 0 do 45.
- Dla bieżącego kąta dla każdego punktu figury oblicz nową, obróconą lokalizację
- Znajdź granice prostokąta zawierającego figurę (minimum i maksimum x, y) i zarejestruj go, jeśli do tej pory najlepiej pasował
- 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?
źródło
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.
źródło