Bresenham-algoritme

Het Bresenham-algoritme is een algoritme voor het tekenen van rechte lijnen en cirkels op matrixdisplays. Dit algoritme werd in 1962 door (destijds programmeur bij IBM), ontwikkeld. Al in 1963 werd het gepresenteerd in een voordracht op de ACM National Conference in Denver. Het bijzondere aan dit algoritme is, dat afrondingsfouten die ontstaan door het afronden van continue grootheden geminimaliseerd worden, terwijl het eenvoudig te implementeren is. De moeilijkste berekening die gebruikt wordt is het optellen van gehele getallen, dus vermenigvuldigen, delen en drijvende-komma-notatie zijn niet nodig. Met een kleine uitbreiding is het oorspronkelijke algoritme, dat was ontwikkeld voor het tekenen van rechte lijnen, ook voor cirkels te gebruiken. Zelfs de kwadratische termen die in de vergelijking van een cirkel voorkomen kunnen recursief zonder vermenigvuldigingen afgeleid worden uit de voorgaande pixel volgens , waarin de term niet voor een vermenigvuldiging telt, omdat die op binair niveau als een schuifoperatie geïmplementeerd kan worden. Op basis van de bovenstaande eigenschappen is de betekenis van het Bresenham-algoritme tot op heden behouden gebleven. Het wordt onder meer toegepast in plotters en grafische kaarten. Het algoritme is bovendien zo eenvoudig, dat de toepassing niet beperkt is gebleven tot firmware, en ook implementatie in hardware heel goed mogelijk is. Voor de volledigheid dient vermeld te worden, dat de naam „Bresenham“ tegenwoordig gebruikt wordt voor een groot aantal grafische algoritmen die eigenlijk later door anderen ontwikkeld zijn, maar gebaseerd zijn op het werk van Bresenham en berusten op hetzelfde principe.