Problème Logicomathématiques

[Sarc]

Bonjour à tous !

J'ai les coordonnées des points d'un polygône en base de données, et j'aimerais avoir les coordonnées d'un point contenu dans ce polygône, à une distance raisonnable des bords... En gros, il me faudrait un point plus ou moins central.

J'aurais pensé à un isobarycentre de tous les points, mais vu que mon polygône n'est pas forcément convexe... la méthode est à oublier.

C'est un problème archi-simple visuellement, mais pour passer en mathématiques, mouerf.

Vous auriez une idée ?

[Jeanluc]

Peut-être ceci.

Soit que le polygone est inscrit dans le rectangle parallèle aux axes et passant par (x1,y1) et (x2,y2). Tu prends un point au hasard dans le rectangle et tu vérifies s'il est ou pas à l'intérieur du polygone et à quelle distance il se trouve des côtés. S'il convient, c'est gagné; s'il ne convient pas, tu recommences avec un autre point et ainsi de suite, si nécessaire.

Tu penses que c'est jouable ?

Jean-Luc

[Sarc]

Salut Jeanluc

Merci de ta réponse.

Le problème c'est bien pour savoir si le point est à l'intérieur du polygône... Je ne connais pas de méthode simple, avec les coordonnées des sommets, pour savoir si un point est à l'intérieur d'un polygône. Parce que si le polygône a une forme un peu bizarre, le point pourra avoir son abscisse comprise entre deux sommets, et son ordonnée entre deux sommets, sans pour autant être à l'intérieur du polygône !

Bon pour l'instant j'ai testé avec un barycentre de tous les sommets, et ça a l'air de marcher sur un échantillon restreint des polygônes que j'utilise, mais si y'a une meilleure idée je suis preneur

[Jeanluc]

C'est clair que le barycentre n'est pas une solution sûre.

Il y a un article dans Wikipedia sur une méthode simple pour savoir si un point est à l'intérieur d'un polygone. En fait, il suffit de tracer une demi-droite quelconque à partir de ce point et de compter le nombre d'intersections avec les côtés du polygone: si le nombre d'intersections est impair, c'est que le point est à l'intérieur. L'article comprend aussi des liens vers des programmes qui mettent ça en pratique. J'ai trouvé l'article grâce à Algorithmes géométriques - Inclusion dans un polygone .

Jean-Luc

[Sarc]

Merci bien pour tes recherches ! Si j'ai un souci je pourrai utiliser tout ça.. Et puis même pour ma culture, ça fait pas de mal de connaître ce genre de résultats

Le barycentre c'est dangereux, c'est sûr, mais l'avantage c'est que je travaillerai toujours sur les 2000 mêmes polygônes, donc je vais peut-être faire un test global avec les barycentres et si ça marche pour tous les polygônes, je m'embêterai pas à programmer quelque chose de plus complexe.

J'aurais pu stocker aussi les coordonnées de 2000 points, mais la flemme de faire ça manuellement :/

Encore merci pour tes recherches

[Jeanluc]

Encore merci pour tes recherches

C'est avec plaisir. Les maths, c'est super-amusant.

Jean-Luc