Définition de la surface intérieur d'un polygone

[invitede91850a]

Bonjour,

Je voudrais savoir si vous connaissez une ou des définitions formelles de références de la notion de surface. À commencer par la surface intérieur d'un polygone.

Je m'explique pour un disque il est assez naturel de le définir comme l'ensemble des points qui ont une distance comprise entre 0 et un maximum donné (le rayon) avec un point de référence (le centre).

Mais pour un polygone, c'est un objet a priori plus simple donc la définition géométrique intuitive est évidente, mais je ne trouve pas de définition formelle évidente de la surface intérieure d'un polygone.

Le plus formel que je trouve c'est de définir la surface d'un triangle (plus simple car un triangle est toujours convexe) puis de dire qu'un polygone peut être trianguler et que sa surface est l'union des surfaces des triangles qui le composent. Je trouve que c'est une définition un peu complexe puisqu'elle nécessite de trianguler le polygone, et est-ce qu'on peut vraiment justifier la correction d'un algorithme de triangulation sans avoir défini ce qu'est la surface d'un polygone ?

Pour un polygone convexe, une définition qui me viendrait assez naturellement consisterait à dire que sa surface est l'ensemble des points qui sont «à gauche» de toutes ses arêtes en supposant définies la notion de «à gauche d'une arête» et que les arêtes soient orientées de façon consistante (dans l'ordre trigo des points disons).

Mais pour un polygone quelconque, qui n'est donc pas nécessairement convexe, ça ne marche plus. Sur un exemple donné on peut faire des choses semblables en disant des choses du type «est à gauche de .. et .. mais à droite de .. et ..» mais la définition générale ne saute pas aux yeux et il faut sans doute prendre en compte des «retournements de courbures» ou je ne sais pas comment ça s'appelle.

Alors plutôt que de me prendre la tête et comme je suis persuadé que c'est une question qui a déjà étudiée par plein de gens j'aimerai bien savoir ce que ça donne, mais je trouve rien avec google.

J'espère que certains auront plus de connaissances que moi.

Merci

PS: pour ceux qui se demandent pourquoi je demande ça c'est parce que je voudrais prouver la correction d'algos d'union de polygones (des algos assez classiques) et pour ça il faut que je définisse le résultat attendu; et la manière la plus naturelle qui m'est venue est de dire qu'un polygone union est le polygone dont la surface intérieure est l'union des surfaces intérieures des polgyones dont on veut faire l'union.
Évidemment plus la façon de définir ces surfaces intérieures sera simple, moins la preuve sera lourde.
-----

[invitede91850a]

Personne ne sait ?

[breukin]

Déjà, autorises-tu les polygones croisés ? (genre le polygone régulier à 5 côtés qu'est l'étoile à 5 pointes : dans ce cas, le petit pentagone intérieur fait-il ou ne fait-il pas partie de l'intérieur de l'étoile ?)
Sans ça, il y a le théorème de Jordan : http://fr.wikipedia.org/wiki/Th%C3%A...A8me_de_Jordan

[invitede91850a]

À terme oui, et aussi les polygones à trous et les polygones « inversés » (quand la liste des arêtes est données dans le sens inverse du sens trigo et que la surfarce interne est en fait la suface qui est à l'extérieur graphiquement), mais pour le moment je vais déjà travailler sur des polygones non croisés, sans trous, etc... juste pas forcément convexe (en fait les polygones à trous je serais obligé d'en tenir compte car l'union de deux polygones relativement simples peut porduire des polygones moins simples, à trou, etc.).

Mais pour le moment je cherche déjà une définition simple pour le cas non convexe, sans trou et non croisé et j'adapterai après, à moins que quelqu'un me propose une solution toute faite qui marche déjà avec les polygone croisés... je prend.

Sinon je me suis peut-être mal exprimé mais je vois pas le rapport entre ce que je veux fairr et le théorème de Jordan. Il y a bien des choses qui font pensés à l'algorithme d'union de deux poygone (croisement des arêtes et déterminser si un point d'intersection est entrant ou sortant), mais je vois pas le lien avec la définition de la surface intérieure d'un polygône.

Peut-être pour être clair, l'algorithme d'union de deux polygone j'en ai un assez classique récupéré sur le net. mon problème c'est d'en faire la preive de correction, et pour en faire d'abord la spécification (formaliser le résultat attendu en sortie), j'ai besoin de définir formellement la notion de surface intérieure. Intuitivement c'est simple, mais le faire formellement moins évdient, ou plus exactement je trouve que les solutions qui me viennent un peu compliquées (diviser la surface en polygones convexes... facile intuitivement et à faire à la main mais ça amène une défintion général complexe), et plus les définitions formelles sont complxes, plus les preuves que je ferais avec le seront.

Donc moi ce que je veux c'est juste définir formellent la notion de suface intérieure d'un poygone (disons non croisé, sans trou et avec des arêtes dans le sens trigo dans un premier temps) qui soit relativement simple. Comme je le disais sur des exemples, on arrive à faire des choses pas trop compliquées avec des « à droite » ou « à gauche de l'arête », mais le cas général ne saute pas forcément aux yeux.

Depuis mon premier post j'ai continué à chercher, persuadé que la définition d'une surface intérieure d'un polygone doit être quelquechose qui a été bien étudié, mais je trouve rien donc je commence avoir des doutes.

[A voir en vidéo sur Futura]

[breukin]

Le lien est pourtant clair : en cas de lacet simple (donc en cas de tracé de polygone d'un seul tenant et sans croisement), le complémentaire du tracé est composé de deux connexes (par arcs) dont un seul des deux est borné.
Donc la définition formelle de l'intérieur d'un polygone, c'est le connexe borné !
Une autre façon de voir les choses est présentée par un dessin : un point est intérieur au polygone si le nombre de points traversés par une demi-droite issue de ce point intersecte le polygone un nombre impair de fois (dès lors qu'aucun des points n'est un sommet, pour éviter les cas pathologiques).

[invitede91850a]

ok je comprend mieux ce que tu voulais dire avec ce lien, mais j'ai bien peur que ça ne concerne pas ce que je cherche car il faudrait définir formallement la notion de connexité... non pas que ce ne soit pas possible mais ça risque de rendre la défintion finale de la surface interieure d'un polygone encore plus complexe que la méthode qui consiste à partionner cette surface en surfaces convexes... Donc ça peut être sans doute utile au niveau théorique mais je pense que ça ne ferait que compliquer les preuves formelles dans mon cas précis.

J'ai pas mal réfléchi en utilisant uniquement des notions «simples» comme «à droite de» ou « à gauche de», j'ai pas encore trouvé le résulat général mais apparemment ça donne des définitions longues, mais assez simple (dans le sens ou c'est juste une longue, mais simple, composition d'éléments très simples).

En revanche l'approche utilisant la parité du nombre de points d'intersections des demi-droites est peut-être plus intéressante. Il faudra que je me penche là-dessus.

Merci.

[Jeanpaul]

Se baser sur le nombre de fois qu'une droite coupe le polynôme pose problème pour des polygones non convexes (genre étoile à 5 branches) où on peut avoir 1, 2 ou 3 intersections.
On pourrait baser une définition sur l'analogue d'une prison : partant de l'intérieur, il est impossible de trouver un chemin continu qui va à l'infini sans couper le polygone (le polygone est forcément fini). Pas évident à mettre en algorithme.

[breukin]

Non, cela ne pose pas de problème, c'est la parité du nombre de points (quand on considère un polygone qui ne se croise pas, l'étoile à 5 branches étant un polygone à 10 côtés -lacet simple-, et non un à 5 -lacet complexe avec croisements-).

[Jeanpaul]

Bien d'accord, si le polygone ne se croise pas c'est facile mais moins drôle.

[ansset]

Une autre façon de voir les choses est présentée par un dessin : un point est intérieur au polygone si le nombre de points traversés par une demi-droite issue de ce point intersecte le polygone un nombre impair de fois (dès lors qu'aucun des points n'est un sommet, pour éviter les cas pathologiques).

cette methode me semble d'une "génialité " imparable.
il suffit d'ailleurs d'une seule demi droite pour faire le dignostic.

pour prolonger, je proposerai de choisir le barycentre des sommets comme réference.
ensuite , pour n'importe quel point du plan le seule demi-droite rejoignant G suffit à dire si le point est interieur ou pas.

[breukin]

Non une seule demi-droite ne suffit pas si par malheur c'en est une qui passe par un sommet, alors que si elle était passée juste à côté on n'aurait eu soit aucun point à cet endroit, soit deux points.
Et comment fait-on pour savoir si le barycentre est intérieur ou pas ?

[breukin]

Bien d'accord, si le polygone ne se croise pas c'est facile mais moins drôle.

Le problème avec les polygones croisés, certains ne sont pas orientables, au sens de dire que l'intérieur c'est ce qui est à gauche dans le sens direct. Exemple polygone ABCD avec A=(1,1), B=(1,–1), C=(–1,1), D=(–1,–1).
On peut le transformer en polygone orientable avec intérieur, mais qui n'est plus croisé, en introduisant O : ABODCO.
Mais ce n'est plus le même polygone, en tant que suite de points.

[invite986312212]

bonjour,

le coup de la demi-droite est imparable, il n'est pas difficile à programmer: il faut chercher des intersections entre segments puisqu'on a affaire à un polygone et pas une courbe quelconque.

il y a une autre approche: l'indice du point par rapport à la courbe. voir ici: http://en.wikipedia.org/wiki/Winding_number (la page wiki en Français est moins détaillée).

[breukin]

Non, il n'est pas imparable, si on choisit n'importe comment la droite.
Soit le polygone OABCDE défini par :
O=(0,0), A=(–1,1), B=(1,1), C=(1,–2), D=(–2,–2) et E=(–2,0).
Soit le point P=(–1,–1). Est-il à l'intérieur ou à l'extérieur ?
Je choisis une demi-droite d'origine P, et, au hasard, de direction (0,1).
Je trouve deux points d'intersection : M=(–1,0) et A. Deux points, donc P est à l'extérieur, puisque c'est imparable.
Mais en tournant un peu la droite à gauche ou à droite, on comprend ce qui se passe. C'est de ce phénomène dont il faut se méfier.

[ansset]

il faut exclure les sommets qui peuvent être listés.

en cas de sommet croisé => trouver un e autre demi-droite.
mais mon histoire de G était trop complexe.

n=1
prendre juste 2 sommets Sn et Sn+1
envoyer la demi droite au milieu
si sommet croisé passer à Sn+1 et Sn+2
recommencer
si pas de sommet croisé , alors
calculer le nombre d'intersection avec l'ensemble des droites.