Ear clipping
En enkel algoritm som trianguläriserar en polygon genom att upprepat klippa bort "öron" — konvexa hörn vars triangel är tom.
Ett öra är tre på varandra följande hörn där mitthörnet är konvext och triangeln de bildar inte innehåller någon annan av polygonens vertexar. Algoritmen letar upp ett öra, klipper bort det som en triangel och upprepar tills bara en triangel återstår.
Den är O(n²) men enkel att implementera och klarar godtyckliga enkla polygoner, även konkava och med hål (via broar). Namnet myntades av Gary Meisters 1975. Den är standardvalet för att göra om 2D-konturer — teckensnitt, UI-former, navigeringspolygoner — till trianglar en GPU kan rita.