Potrzebuję utworzyć binarną bitmapę z zamkniętego wieloboku 2D przedstawionego jako lista punktów. Czy mógłbyś wskazać mi wydajne i wystarczająco proste algorytmy, aby to zrobić, lub, jeszcze lepiej, trochę kodu C++?Rasteryzacja wieloboku 2D
Wielkie dzięki!
PS: Chciałbym uniknąć dodania zależności do mojego projektu. Jeśli jednak sugerujesz bibliotekę otwartego źródła, zawsze mogę popatrzeć na kod, więc może być przydatny.
Magiczna fraza google to "reguła uzwojeń niezerowych" lub "nieparzyste wypełnienie wielokątów".
Zobacz wpisy Wikipedii:
Oba są bardzo łatwe do wdrożenia i wystarczająco szybki dla większości zastosowań. Przy odrobinie sprytu mogą zostać również zlikwidowane.
złożoność wynosi O (Area w pikselach)
W jaki sposób byś rasteryzował powstałe trójkąty? Jeden po drugim, przechodząc cały obraz za każdym razem? Czy to nie będzie bardzo powolne? –
@static_rtti: co masz na myśli przechodząc cały obraz za każdym razem? – yairchu
@static_rtti: Dodałem wyjaśnienie, w jaki sposób rasteryzować trójkąt – yairchu
Możesz sprawdzić rutynę wielokąt wypełnienia w Pygame. Spójrz na funkcję draw_fillpoly.
Algorytm jest dość prosty. Znajduje wszystkie pozycje, które każdy segment przecina wzdłuż osi Y. Te przecięcia są sortowane, a następnie poziomo wypełnia każdą parę przecięć.
To będzie obsługiwać złożone i przecinające się kształty, ale oczywiście można zmiażdżyć ten algorytm z dużą ilością segmentów.
niezbyt spokrewniony ale btw Pete jesteś świetny do robienia pygame :) – yairchu
solidnego implimentation z "even-odd rule"
Zobacz Darel Rex Finley's Efficient Polygon Fill lub Blender's version go.
to jest parzyste/nieparzyste napełniania sposób, który wspiera siebie przecinających się linii, bez potrzeby złożonego kodu wykrywania takich sytuacjach, i nie zależy od uzwojenia (wielokąta może być odwrócone i dają takie same wyniki).
Update, zrobiłem zoptymalizowaną wersję metody DAREL Rexa że unika zapętlenie nad wszystkie współrzędne dla każdego y piksela.
Samodzielne implementacje:
Choć przyspieszenie będzie prawdopodobnie wykładniczy, Od szybkiego testu, jego około 7,5x szybszy (11x przy usuwaniu round połączenia), używając dowolnej wyciągnąć rękę bazgroły na obszarze 2540x1600, YMMV.
@plinth: czy to nie nadmierne zabójstwo dla prostych wielokątów? – yairchu
Co to jest prosty wielokąt? @static_rtti nie określa ile punktów lub jeśli wielokąty zawsze będą wypukłe, dlatego ogólne rozwiązanie jest poprawną odpowiedzią. NZW i EO są proste w obsłudze i nadają się do skanowania zorientowanych rozwiązań, itp. Itp. – plinth
@plinth: Dzięki, właśnie tego szukałem! Przeszukiwanie go może być trudne, gdy nie masz tego magicznego wyrażenia :-) –