Verticale celdecompositie

Verticale celdecompositie is een algoritme voor celdecompositie, voor het opdelen van een ruimte in kleinere ruimten, de cellen. De techniek wordt ook trapezoïdale decompositie genoemd aangezien de verkregen cellen de vorm van een trapezoïde hebben.^[1] Het is dus een meetkundig algoritme.

Techniek

Het algoritme deelt op basis van de objecten in een ruimte die ruimte in cellen op. Deze objecten worden gerepresenteerd als veelhoeken met de hoekpunten en zijden daarvan. Zij worden op een vlak geprojecteerd. Voor ieder hoekpunt van een object wordt een halve lijn naar beneden en naar boven toegevoegd, naar het projectievlak en van het projectievlak af, tot aan het projectievlak, een ander object of de grens van de ruimte. Er zijn hiervoor vier mogelijkheden:

de halve lijn kan zowel naar boven als naar onder worden toegevoegd
de halve lijn kan alleen naar boven worden toegevoegd, naar onder is niet mogelijk door een object
de halve lijn kan alleen naar onder worden toegevoegd, naar boven is niet mogelijk door een object
de halve lijn kan naar geen van beide kanten worden toegevoegd, zowel boven als onder bevindt zich een object

Op deze manier worden eendimensionale halve lijnen en tweedimensionale trapezoïden verkregen.

Toepassingen

Een toepassing van deze techniek kan men vinden in bewegingsplanning, waarbij verticale celdecompositie kan worden gebruikt om een configuratieruimte in cellen op te delen. Voor het plannen van een beweging is het vaak nodig om een pad te vinden in de configuratieruimte en het opdelen van deze ruimte in cellen kan helpen om dit probleem op te lossen. Door van elke cel het middelpunt te nemen en deze met elkaar te verbinden, heeft men een graaf geconstrueerd die kan worden gebruikt voor de navigatie door de ruimte.

Websites

(en) SM Lavalle. Vertical Cell Decomposition. hoofdstuk 6, Planning Algorithms
(en) Washington-universiteit te Saint Louis. Lecture 14: Trapezoidal Decompositions. gearchiveerd

Bronnen, noten en/of referenties

↑ De methode kan eventueel ook driehoeken opleveren, deze worden als misvormde trapezoïden gezien.

[1] De methode kan eventueel ook driehoeken opleveren, deze worden als misvormde trapezoïden gezien.

[1]