Bonsoir,

Je travaille actuellement sur un projet dans lequel je suis amené à utiliser des zones sur une carte :  (ici en bleu). J'aimerais pouvoir placer de manière "centrée" (i.e. pas sur une extrémité) dans chacune des zones un pointeur avec son nom.

Chaque zone étant représenté par les n coordonnés géographiques de ses sommets formant un polygone irrégulier convexe ou concave, je ne peux utiliser pour tous la notion de barycentre.

Existerait-il un autre point remarquable qui permettrait de placer le pointeur pour tous les polygones concaves ?

D'avance merci.

Salut. 
Calculer le barycentre (cad ici, faire la moyenne des coordonnées des sommets) devrait te donner un résultat intéressant, je pense.

Le problème avec le barycentre, c'est que parfois, il va se trouver en dehors de la zone (par exemple la zone en forme de L au milieu de la carte donnée en exemple, le barycentre va peut-être être dans la zone, mais peut-être pas)

Autre problème (mineur), c'est que parfois, ces contours de cartes peuvent-être irréguliers : sur le bord droit, on va avoir un point tous les 5 mètres, par exemple parce qu'on est en bord de mer, et que la côte est accidentée. Et sur un autre bord, pour la même zone, on aura un point tous les 100 mètres. Ce cas là n'est pas grave, le barycentre sera simplement très décalé vers un des cotés de la zone.

Salut, 

une manière d'envisager les choses serait peut-être de poser ça comme un problème d'optimisation sous contrainte. Dans la suite, j'appelle "point" l'endroit où tu souhaites placer ton label. Je pars du principe que les noeuds de ton polygone te sont donnés dans un ordre qui te permet d'obtenir la normale sortante à chaque côté. Si tu as la normale, tu peux définir la "hauteur" de ton point par rapport au côté correspondant. Si ta "hauteur" est positive, tu es en dehors du polygone; si elle est négative, tu peux être dehors comme dedans. Cela dit, si TOUTES les hauteurs sont négatives, tu es forcément à l'intérieur. La solution que je te propose est donc la suivante : tu cherches à maximiser la somme des valeurs absolues de tes hauteurs (rappel : elles peuvent être négatives; en gros, tu veux être le plus loin possible de tous tes côtés) avec la contrainte que toutes tes hauteurs DOIVENT être négatives (le plus loin possible, mais à l'intérieur !).

Je vais regarder de mon côté dès que j'ai le temps (j'suis au taf' là).

Edit: oublie ce que j'ai écris ci-dessus ! Il faudrait que le polygone soit convexe.

Edit 2 : pour vérifier que ton point est à l'intérieur du polygone, tu peux le mailler avec des triangles (voir triangulation de Delaunay par exemple), et vérifier qu'il appartient à au moins l'un d'eux.

-
Edité par Nozio 25 novembre 2019 à 11:37:19

tbc92 a écrit:

Le problème avec le barycentre, c'est que parfois, il va se trouver en dehors de la zone (par exemple la zone en forme de L au milieu de la carte donnée en exemple, le barycentre va peut-être être dans la zone, mais peut-être pas)

Autre problème (mineur), c'est que parfois, ces contours de cartes peuvent-être irréguliers : sur le bord droit, on va avoir un point tous les 5 mètres, par exemple parce qu'on est en bord de mer, et que la côte est accidentée. Et sur un autre bord, pour la même zone, on aura un point tous les 100 mètres. Ce cas là n'est pas grave, le barycentre sera simplement très décalé vers un des cotés de la zone.

ah oui; j'avais pas lu en entier le message. Mais du coups, tu mettrais ou le centre, à la main, dans le cas de la forme en L ?

A la main :

Pour un L qui aurait ces coordonnées : (0,0)(10,0)(10,1)(1,1)(1,10)(0,10), je mettrais son centre vers (0.9,0.9). Donc tout près de l'angle 'intérieur'.

Pour un L qui aurait ces coordonnées : (0,0)(10,0)(10,1)(1,1)(1,15)(0,15), je mettrais son centre vers (0.9,2). 

Concretement, on peut chercher le barycentre. Et si le barycentre est à l'extérieur de la zone, on cherche le sommet le plus proche du barycentre (ou le point-frontière le plus proche du barycentre, mais c'est un peu plus compliqué), et on retient ce point.

Mais même comme ça, on se retrouve avec un point 'centré' qui est sur la frontière, et esthétiquement, j'imagine que ça ne va pas plaire.

Une idée possible, mais peut-être coûteuse en temps de calcul, serait de choisir un point particulier, puis de balayer les milieux de tous les segments possibles (reliant ce point particulier à chacun des autres points) jusqu'à tomber sur un point intérieur au polygone. Je fais le postulat qu'il y a forcément un milieu de deux sommets qui est à l'intérieur, ce qui n'est peut-être pas toujours le cas (probablement rarement).

On pourrait même calculer tous les milieux possibles pour tous les sommets et calculer, pour chaque milieu appartenant au polygone, la distance entre ce point et le contour du polygone (distance égale à la somme des distances de chaque côté), et chercher le point qui a la plus grande distance (ainsi il y a de la place pour écrire quelque chose). (La distance entre un point et un côté n'est pas simple à calculer : c'est le minorant de la distance entre ce point et à la droite, la distance entre ce point et l'extrémité du segment, et la distance entre ce point et l'autre extrémité.)

Ce qui est coûteux, c'est de déterminer si le point est à l'intérieur du polygone. Pour ça, il faut balayer chaque côté dans un sens défini à l'avance et, pour chacun d'eux, regarder si on est à gauche ou à droite du côté (d'une demi-droite, en fait) par rapport au sens de parcours. Si on est du même côté (par exemple toujours à gauche), c'est qu'on est à l'intérieur. Dès que ça change, pas la peine de poursuivre le test : on est à l'extérieur.

Si on cherche le milieu le plus éloigné du contour, ça signifie qu'il faut tester N² milieux (où N= le nombre de points du polygone). (En fait plutôt N(N-1)/2 je crois.)

-
Edité par robun 27 novembre 2019 à 13:29:24

Moins coûteux, mais peut-être pas optimal : prendre 3 points consécutifs, voir s'ils forment un polygone convexe avec la bonne orientation, puis en rajouter un quatrième, vérifier, puis un cinquième, etc. Jusqu'à construire le plus grand possible. Ensuite on récupère le barycentre.

Au final, la solution que j'emploierais est la suivante 

- Triangulation du polygone (triangulation de Delaunay).

- Pour chaque triangle, on sait facilement calculer le centre de gravité et la surface. 

- Et du coup, on sait calculer un centre de gravité parfait pour le polygone ( moyenne pondérée des centres de gravités des triangles)

Si le point obtenu est dans le polygone, tout va bien.

Sinon étape supplémentaire. Parmi les centres de gravités des triangles, je retiens le point le plus proche du point obtenu à l'étape précédente.

Avantage : on est sûr de tomber sur un point 'intérieur', et pas sur un point frontière.

Inconvénient : Il y a plein de résultats possibles pour la triangulation de Delaunay, tous aussi valables les uns que les autres. Et donc, ce procédé n'est pas réellement déterministe.

Mais ça doit être bien couteux s'il faut faire tout ça instantanément pour les 20 ou 30 zones de la petite carte prise en exemple.

Non, en fait, ça va être très très rapide parce que la taille de triangle que tu vas choisir pour ta triangulation est très grande (au minimum la taille de la plus petite de tes arêtes) donc tu en auras peu par polygone.