Wpis z mikrobloga

Cześć mirki!

Jest taki problem, że wczytujemy wielokąt, który nie jest wypukły. Może to być np. mapa gry. Chcemy zamienić to na jak najmniejszą ilość figur do systemu kolizji. Możemy teraz:

- Za pomocą algorytmu "marching squares" odnaleźć krawędzie planszy
- Za pomocą algorytmu Ramer-Douglas-Peuckera możemy zredukować liczbę punktów na krzywej
- Za pomocą algorytmu "ear clipping" zamienić wielokąt na trójkąty

Znacie lepsze podejście? Ten ostatni algorytm, to chyba nawet o O(n^3) zahacza.

#gamedev