- Polygone simple
-
En géométrie, un polygone simple est un polygone dont les arêtes ne se croisent pas. Plus précisément, la frontière d'un tel polygone est une ligne polygonale fermée du plan, formée de segments de droite qui n'ont pas d'autres points en commun que les intersections de deux segments consécutifs. Un polygone simple est topologiquement équivalent à un disque.
Les polygones simples sont aussi appelés polygones de Jordan, en relation avec le théorème de Jordan qui établit que toute courbe fermée du plan qui ne se recoupe pas divise le plan en deux régions : l'intérieur et l'extérieur.
Sommaire
Polygone faiblement simple
Si une ligne polygonale fermée du plan divise celui-ci en deux domaines tous les deux équivalents à un disque, alors la ligne polygonale est appelée un polygone faiblement simple. De manière moins formelle, un polygone faiblement simple peut avoir des côtés qui se touchent, mais qui ne se croisent pas. Le dessin en mode texte ci-dessous montre un exemple d'un tel polygone (ici le polygone ABCDEFGHJKLM), avec les "x" marquant l'intérieur.
A----------B |xxxxxxxxxx| |xH-----Gxx| |x| |xx| |x| |xx| |xJ-K,E-Fxx| |xxxx|xxxxx| M---L,D----CLes polygones faiblement simples (et non simples) sont utilisés en infographie, ainsi qu'en CAO, pour représenter des régions polygonales avec des trous : pour chaque trou dans la région, une "coupe" est créée, qui le relie à la frontière extérieure. Dans le dessin ci-dessus, ABCM est la frontière extérieure d'une région polygonale ayant un trou représenté par FGHJ. Le coupe ED connecte le trou avec l'extérieur, et est parcourue deux fois, ce qui résulte en une représentation par polygone faiblement simple.
Applications en géométrie algorithmique
En géométrie algorithmique, certains problèmes calculatoire impliquent des entrées sous la forme de polygones simples. Dans chacun de ces problèmes, la distinction entre intérieur et extérieur est cruciale pour la définition du problème[1].
- Point dans un polygone (en) : test permettant de déterminer si un point P du plan se trouve à l'intérieur ou à l'extérieur du polygone.
- Des formules simples sont connues pour calculer l'aire d'un polygone, c'est-à-dire l'aire de l'intérieur du polygone.
- Triangulation d'un polygone : algorithme qui consiste à diviser un polygone simple en un nombre fini de triangles.
- L'enveloppe convexe d'un polygone simple peut être calculé plus facilement que celle d'un ensemble quelconque de points.
Note
- (en) La FAQ comp.graphics.algorithms, qui référence des solutions à des problèmes impliquant des polygones 2D et 3D.
Voir aussi
Article connexe
Liens externes
- (en) Eric W. Weisstein, « Simple Polygon », MathWorld
- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Simple polygon » (voir la liste des auteurs)
Wikimedia Foundation. 2010.
