Czy istnieje skuteczny algorytm standardowy rastrowe wielokąt tym jego wewnętrznej powierzchni

Question

Powiel możliwe:
Rasterizing a 2D polygon

muszę rastrowe wielokąt tym jego wewnętrznej powierzchni (określić wszystkie płytki z siatka leżąca wewnątrz wielokąta). Obecnie wyznaczam płytki graniczne za pomocą prostego Bresenhama, ale nie mam do tej pory skutecznej metody rastowania "wnętrza" wielokąta (który również może być wklęsły). Dotychczasowe podejście polega na ograniczeniu zakresu kafelków do prostokąta, w tym wieloboku, a następnie określeniu dla każdego centrum płytki, czy leży on wewnątrz, czy na zewnątrz, za pomocą algorytmu uzwojenia wielokąta. Jest to nieefektywne, ponieważ wymaga sprawdzenia każdego segmentu granicy wielokąta dla każdego pola. Od pierwszego widoku zdecydowanie powinno być szybsze podejście, np. sth. jak nawijanie za pomocą rastrowanej granicy. Czy istnieje standardowy algorytm, który rozwiązuje ten problem, a może nawet implementacja biblioteki w C++?

Answer 1

Istnieje sporo zasobów w sieci, na przykład:

• Efficient Polygon Fill Algorithm With C Code Sample;