Rooster (wiskunde)

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
Een driehoekig gelijkzijdig rooster in het Euclidische vlak.

Een rooster in de wiskunde is 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.

In de oorspronkelijke betekenis liggen de punten in een rooster op gelijke afstanden van elkaar. 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.

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[bewerken]

Een rooster verdeelt dat, waar het rooster overheen is gelegd, in cellen. Dit maakt het mogelijk om 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[bewerken]

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

Roosters worden onderscheiden in twee categorieën:

  • Uniforme roosters - In deze roosters liggen de roosterpunten op gelijke afstanden van elkaar zitten.
  • Niet-uniforme roosters - Dit zijn roosters waar op sommige plaatsen de roosterpunten dichter op elkaar liggen dan op andere plaatsen.

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[bewerken]

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[bewerken]

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

Voronoi-diagram[bewerken]

Een veelgebruikte methode is het Voronoi-diagram. Bij de Voronoi-diagram is ieder roosterpunt het midden van een cel. Alle punten die dichterbij 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[bewerken]

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[bewerken]

Bronnen[bewerken]