Rooster (wiskunde)

In de wiskunde is een rooster een discrete verzameling punten, roosterpunten genoemd, in een euclidische ruimte.

In de oorspronkelijke betekenis liggen de punten in een zekere regelmaat in het rooster. zo, dat het optellen of aftrekken van twee roosterpunten weer een roosterpunt oplevert. Voor praktische doeleinden kan ervoor worden gekozen een rooster te kiezen waarin de punten niet noodzakelijk op dezelfde afstanden liggen. Roosters hebben bijvoorbeeld vooral praktisch nut bij het gebruik van computers, zoals in de numerieke wiskunde en bij computergraphics.

De punten in een regelmatig rooster zijn lineaire combinaties met gehele coëfficiënten van basisvectoren. De determinant van deze basisvectoren wordt ook de determinant van het rooster genoemd.

Roosters vormen een meetkundig hulpmiddel om continue entiteiten af te beelden op discrete roosterpunten. Roosters laten zich het beste aan de hand van voorbeelden beschrijven. Een bekend voorbeeld is het rooster gevormd door de punten met gehele coördinaten. De elementen van een rooster worden vaak aangeduid als de roosterpunten. De figuur hiernaast toont een driehoekig rooster.

Een entiteit kan een lijn, een tweedimensionaal oppervlak of een figuur, een driedimensionaal oppervlak of een driedimensionale ruimte of lichaam zijn. Theoretisch zou het ook mogelijk zijn roosters voor entiteiten met hogere dimensies te bedenken. Een rooster bestaat uit een verzameling roosterpunten die in de entiteit worden geplaatst. Vervolgens wordt van ieder punt in de entiteit bepaald tot welk roosterpunt dit behoort.

Doel van een rooster

Een rooster verdeelt datgene, waar het rooster overheen is gelegd, in cellen. Dit maakt het mogelijk een coördinatenstelsel op te zetten, waarna ieder punt door middel van een coördinaat kan worden bepaald. Bijvoorbeeld, de lengte- en breedtegraden op het aardoppervlak zijn een rooster dat om de Aarde heen is gelegd.

Indien de afmetingen van het rooster eindig zijn, ontstaat een eindig aantal cellen. Dit maakt het mogelijk per cel gegevens over dat object te verzamelen. Bijvoorbeeld, over een landkaart wordt een rooster gelegd. Vervolgens meten we voor iedere cel de hoogte boven NAP. Vervolgens vormt het rooster een hoogtemap, die we zouden kunnen gebruiken om een visualisatie van het terrein te maken.

In een roostercel kunnen meerdere meetpunten voorkomen, het gemiddelde, hoogste of laagste meetpunt kun je beschouwen als significant voor die cel worden opgeslagen.

Voordelen van het gebruik van roosters zijn:

Reductie van de hoeveelheid data die moet worden verzameld en opgeslagen
Filtering van gemeten data
Makkelijker zoeken en vergelijken

Uniforme en niet-uniforme roosters

Uniform verdeelde roosterpunten met daarnaast de Dirichlettesselatie en Delaunay-triangulatie ervan

Roosters worden onderscheiden in twee categorieën:

Uniforme roosters
Niet-uniforme roosters - Dit zijn roosters waar op sommige plaatsen de roosterpunten dichter op elkaar liggen dan op andere plaatsen.

Een uniform rooster is een rooster waarbij de verschilvectoren van de positievectoren van alle tweetallen roosterpunten een groep vormen. Als de oorsprong een roosterpunt is, vormen de positievectoren van de roosterpunten een groep. In het algemene geval is een uniform rooster dus een verschoven versie van zo'n rooster. Een uniform rooster heeft translatiesymmetrie met als translatievectoren de genoemde groep, en minstens ook puntsymmetrie ten opzichte van elk roosterpunt.

In het bijzonder vormt een discrete translatiegroep een uniform rooster. Per ruimte kunnen uniforme roosters worden ingedeeld naar hun extra symmetrie. In 2D zijn er vijf soorten (zie ook 2D translatieroosters), met, afgezien van isometrie en schaling:

geen vrijheidsgraden: vierkant (vierkant rooster), ruit met hoeken van 60° en 120° (hexagonaal rooster)
één vrijheidsgraad: rechthoek (rechthoekig rooster), ruit (rombisch rooster)
twee vrijheidsgraden: parallellogram (scheef rooster)

Uniforme roosters hebben als voordeel dat het bepalen van de roosterpunten een triviale zaak is. Bijvoorbeeld bij een vierkantvormig rooster, kunnen de roosterpunten op gelijke afstanden van elkaar gezet worden. Deze roosters zijn dan ook vanwege hun eenvoud erg prettig in gebruik.

Het nadeel van uniforme roosters is dat in veel praktijksituaties op sommige plaatsen een hoge resolutie gewenst is, terwijl op veel andere plaatsen een lagere resolutie acceptabel is. Bijvoorbeeld, als we een hoogtemap maken van een gebied dat vlak is, met twee heuvels erin, dan kunnen we op het vlakke gebied een lage resolutie gebruiken, immers, een vlakte blijft vlak, onafhankelijk van de resolutie. In de buurt van de heuvels zouden we echter behoefte hebben aan een hogere resolutie, omdat resolutie daar juist direct het detail bepaalt.

Niet-uniform verdeelde roosterpunten met daarnaast de Dirichlettesselatie en Delaunay-triangulatie ervan

In dit soort situaties kunnen niet-uniforme roosters gebruikt worden. Hierbij worden in de buurt van de heuvels meer roosterpunten geplaatst dan op de vlakte. Uit deze roosterpunten worden vervolgens roostercellen bepaald.

Door niet-uniforme roosters te gebruiken kan de hoeveelheid geheugen- en computerkracht die nodig is om het gewenste detail te bereiken sterk beperkt worden.

Bepaling van roosterpunten

De eerste stap in het genereren van een rooster is het genereren van de roosterpunten. Dit is voor uniforme roosters triviaal. Voor niet-uniforme roosters zijn een aantal technieken in gebruik, waaronder:

Willekeurige roosterpunten - Hierbij wordt het in te roosteren object in een aantal dichtheidszones verdeeld. Via een kanstrekking worden dan roosterpunten gegenereerd zodat in zones met een hogere dichtheid relatief meer punten terechtkomen dan in zones met een lage dichtheid.
Raycasting - Hier bij worden over het in te roosteren object horizontale roosterlijnen gelegd. Vervolgens worden op de horizontale roosterlijnen roosterpunten gegenereerd, waarbij een roosterpunt niet te dicht bij de objectrand en eventuele andere, al getekende punten mag liggen. De punten worden binnen deze beperking op minimale afstand van elkaar geplaatst.

Bepaling van roostercellen

Nadat de roosterpunten bepaald zijn, moeten de roostercellen nog worden bepaald. Dit kan op verschillende manieren.

Voronoi-diagram

Een veelgebruikte methode is het Voronoi-diagram. Bij de Voronoi-diagram is ieder roosterpunt het midden van een cel. Alle punten die dichter bij dat roosterpunt liggen dan bij een ander roosterpunt liggen in de cel. Hierbij ontstaan polygoonvormige cellen.

Deze techniek staat ook bekend als Dirichlettesselatie.

Delaunay-triangulatie

Indien een Dirichlettesselatie wordt gemaakt kan daaruit een Delaunay-triangulatie bepaald worden. Als alle roosterpunten waarvan de bijbehorende polygonen een punt gemeenschappelijk hebben met elkaar verbonden worden dan ontstaan driehoeken. Dit wordt het Delaunay-triangulatie genoemd. De Delaunay-triangulatie wordt gezien als de beste triangulatietechniek omdat hij de som van de kleinste hoeken over alle driehoeken maximaliseert, driehoeken met scherpe hoeken worden zo veel mogelijk vermeden.

Zie ook

Bronnen

W.F. Bronsvoort, A. Noort, F.H. Post. - Geometrisch modelleren - Technische Universiteit Delft, augustus 1999.