Trouver le milieu d'un polygone rapidement ?

Bonjoir !

Quel rapport avec python ? Peu voire pas du tout, j'avoue... :oops:

Dans une image contenant des polygones de 3, 4 ou 5 côtés (triangle équilatéral, carré, octogone équilatéral) à la rotation aléatoire, j'aimerais trouver rapidement le centre de celui sur lequel je clique.

J'ai songé à une méthode (et très certainement réinventé la roue) qui me semble facile à mettre en œuvre en python :

Pièce jointe 628960

Le premier point noir (en bas du polygone) est l'endroit où j'ai hypothétiquement cliqué, ensuite avec PIL (pix = im.load()) je peux obtenir un tableau 2D des pixels et donc établir ma première droite verticale (while pixel is blue y+1 / idem avec y-1), je peux calculer facilement le centre de cette droite (second point noir) et recommencer à l'horizontale pour déterminer le centre du polygone.

Mon raisonnement vous parait juste ? Y a-t-il plus mieux en terme pythonesque (plus rapide que PIL par ex) ou algorithmique ?

(Vive photoshop)

Merci et bonne joirée !

Bonjour

Citation:

---

Envoyé par LeNarvalo

Quel rapport avec python ? Peu voire pas du tout, j'avoue... :oops:

---

Ben oui, ton topic est un topic d'algo...

Citation:

---

Envoyé par LeNarvalo

Dans une image contenant des polygones de 3, 4 ou 5 côtés (triangle équilatéral, carré, octogone équilatéral)

---

Oui, l'octogone, bâtiment à 5 côtés bien connu abritant le QG du Ministère de la Défense américaine... 8-)

Citation:

---

Envoyé par LeNarvalo

ou algorithmique ?

---

Pour les octogones impairs ce serait le point d'intersection des médianes (et 2 suffisent) et pour les octogones pairs le point d'intersection des diagonales. Reste les octogones à 1 côté...:mrgreen:

Citation:

---

Ben oui, ton topic est un topic d'algo...

---

Oui je sais. C'est un petit entracte ! ;)

Citation:

---

Pour les octogones impairs ce serait le point d'intersection des médianes (et 2 suffisent) et pour les octogones pairs le point d'intersection des diagonales...

---

C'est surement pas facile ni rapide à calculer depuis une image... Faudrait que je me fasse quelques croquis avec des rotations différentes pour voir si ma proposition tiens la route.


Vive la république ! Vive l'octogone ! :france:

je croyais qu'un octogone avait toujours 8 côtés (étymologiquement 8 angles, donc 8 sommets) :mrgreen: donc un nombre pair de côtés

Citation:

---

Envoyé par umfred

je croyais qu'un octogone avait toujours 8 côtés (étymologiquement 8 angles, donc 8 sommets) :mrgreen: donc un nombre pair de côtés

---

C'était une moquerie sur le premier post, où le PO cites des figures à 3, 4 et 5 côtés qu'il nomme respectivement triangle, carré et octogone...

j'ai pas bien tilté sur le comique de répétition :mrgreen:

Pièce jointe 629002

Citation:

---

Envoyé par LeNarvalo

je peux obtenir un tableau 2D des pixels et donc établir ma première droite verticale (while pixel is blue y+1 / idem avec y-1

---

oui je pense qu'il faut partir sur cette méthode là.
La méthode serait la suivante:
*parcourir chaque point de l'écran ligne par ligne afin de définir les sommets x,y des polygones en testant si chaque pixel PixelX,PixelY est bleu : une ligne d'écran c'est la largeur de l'image mettons 640 pixels.
Le premier sommet sera donc la première ligne horizontale ne comprenant qu'un seul point bleu
*les sommets suivants seront la ligne comprenant le plus de points bleus
*le sommet le plus bas sera la dernière ligne ne comprenant qu'un seul point
*ranger ces sommets dans un tableau.
*avec ces points définir les droites /vecteurs entre ces points.
*en obtenant ces points on peut avoir le milieu de ces droites.


Sinon la méthode la plus simple c'est de définir les sommets du polygone.
En obtenant les sommets du polygone trouver l'équation du cercle passant par ces sommets.
Au boulot :mouarf:

Citation:

---

Envoyé par Sve@r

Pièce jointe 629002

---

Code:

---

1 2 3 4 5 6 7 8 9 10 11

$ chuck ________________________________________ / Chuck Norris doesn t need a debugger, he \ | just stares down the bug until the code | \ confesses. / ---------------------------------------- \ ^__^ \ (oo)\_______ (__)\ )\/\ ||----w | || ||

---

Chuck Norris n'a pas besoin d'un débogueur, il regarde juste le bogue jusqu'à ce que le code avoue son erreur.

Citation:

---

Envoyé par Mat.M

Sinon la méthode la plus simple c'est de définir les sommets du polygone.
En obtenant les sommets du polygone trouver l'équation du cercle passant par ces sommets.

---

Euh... pour trouver l'équation d'un cercle, équation de type (x-xC)²+(y-yC)²=r² (avec xC et yC les coordonnées du centre C), n'est-il pas nécessaire de connaitre au préalable le centre du cercle (donc ici le centre du polygone)? :oops:
Donc en résumé, la méthode la plus simple pour trouver le centre du polygone c'est d'avoir le centre du polygone. Ca se tient... :mrgreen:

Citation:

---

Envoyé par Sve@r

Donc en résumé, la méthode la plus simple pour trouver le centre du polygone c'est d'avoir le centre du polygone. Ca se tient... :mrgreen:

---

Pour les polygones réguliers (convexe)s l'intersection des médianes de 2 côtés donnera le centre du cercle inscrit.
Et pour avoir ces côtés, il faut avoir les coordonnées des points qui en sont les sommets.

Et si on prend le problème de départ, si à partir de la médiane d'un côté on récupère le segment qui va du milieu du coté au point opposé du cercle inscrit.
Si le milieu de ce segment était le centre de ce cercle, le cote serait de longueur nulle (et le prétendu polygone: un cercle).

- W

Euh vous êtes gentils mais c'est un truc prise de tête que vous me proposez là les pros !

Je rajoute à mon énoncé que le centre peut être approximatif. :aie:

Ma proposition n'est malheureusement pas aussi précise que je l'espérais mais ça n'est pas trop éloigné de la réalité :
Pièce jointe 629017
Vive Geogebra !

Citation:

---

Envoyé par LeNarvalo

Ma proposition n'est malheureusement pas aussi précise que je l'espérais mais ça n'est pas trop éloigné de la réalité

---

Reste à calculer les erreurs de cette méthode pour voir si sa précision est intéressante (et dans quels cas).

Citation:

---

Envoyé par LeNarvalo

Euh vous êtes gentils mais c'est un truc prise de tête que vous me proposez là les pros !

---

ah ben... mais si vous voulez de l'aide on a déjà mentionné que ce n'était pas (ici) le bon forum.

- W

Citation:

---

Envoyé par wiztricks

ah ben... mais si vous voulez de l'aide on a déjà mentionné que ce n'était pas (ici) le bon forum.

---

Oui, oui, c'est plus un topic de discussion qu'une vraie demande d'aide.
Le topic se prête à un ton plus léger qu'à l'accoutumé. C'est pourquoi je râle quand on me propose un truc en X étapes plutôt complexes à mettre en place. ;)

Pour revenir à mon sujet, je crois que je vais rester sur mon idée, ça me paraît simple à mettre en oeuvre.

Si je voulais optimiser la chose, je pourrais rajouter trois axes supplémentaires, à voir...
Pièce jointe 629031

En trouvant les 4 lignes (2 horizontales haut et bas, et 2 verticales droite et gauche en partant de la position de ton clic) qui délimitent un rectangle englobant ton polygone, et calculant le centre de ce rectangle, tu devrais tomber aussi sur le centre du polygone je pense.

Hello,
en tout cas pour calculer le centre d'un polygone en connaissant les coordonnées de ses sommets ce n'est pas très compliqué en python :

Code:

---

1 2 3 4 5 6 7 8 9 10

def calculCentre(coords): liste_x = [coord[0] for coord in coords] liste_y = [coord[1] for coord in coords] lenc = len(coords) x = sum(liste_x) / lenc y = sum(liste_y) / lenc return (x, y)   polygon_coords = ((-6.6, 0.12), (-4.05, 2.7), (-5.75, 5.95), (-9.3, 5.38), (-9.83,1.75)) print(calculCentre(polygon_coords))

---

Citation:

---

(-7.106, 3.1799999999999997)

---

Ami calmant, J.P

Le problème c'est de les trouver ces sommets ^^

Citation:

---

Envoyé par jurassic pork

Code:

---

1 2 3

def calculCentre(coords): liste_x = [coord[0] for coord in coords] liste_y = [coord[1] for coord in coords]

---

---

T'ai-je déjà dit que j'adorais le map() ???

Code:

---

1 2 3

def calculCentre(coords): liste_x = map(lambda x:x[0], coords) liste_y = map(lambda x:x[1], coords)

---

:P

Citation:

---

Envoyé par jurassic pork

en tout cas pour calculer le centre d'un polygone en connaissant les coordonnées de ses sommets ce n'est pas très compliqué en python

---

Les coordonnées du centre du cercle inscrit moyenne des coordonnées des sommets?

- W

Citation:

---

Envoyé par umfred

En trouvant les 4 lignes (2 horizontales haut et bas, et 2 verticales droite et gauche en partant de la position de ton clic) qui délimitent un rectangle englobant ton polygone, et calculant le centre de ce rectangle, tu devrais tomber aussi sur le centre du polygone je pense.

---

Ca marche pour le pentagone mais pas le triangle équilatéral.
Pièce jointe 629081

Citation:

---

Envoyé par umfred;

Le problème c'est de les trouver ces sommets ^^

---

Exactement !
Si mon script doit faire 3000 opérations pour trouver les sommets pas sûr que se soit très rapide.

Une contrainte c'est que 2 polygones peuvent être proche sans se toucher par contre, ce qui rend la tâche compliquée pour délimiter un rectangle autour de celui sur lequel j'aurai cliqué.

---

Pour avoir la somme des x et y :

Code:

---

1 2 3 4 5 6 7 8

>>> coords = ((1,2),(10,20))   >>> sum([*coords][0])   3 >>> sum([*coords][1])   30

---

Mots clefs dans Google : "Python inverse of zip" :D

Citation:

---

Envoyé par LeNarvalo

Une contrainte c'est que 2 polygones peuvent être proche sans se toucher par contre, ce qui rend la tâche compliquée pour délimiter un rectangle autour de celui sur lequel j'aurai cliqué.

---

Trouver le centre d'un polygone régulier en connaissant ses sommets suppose qu'on part avec les sommets d'un polygone régulier.

Et si on trouve un brico. qui fonctionne pour les polygones réguliers décrits à partir de leur sommets, on ne va pas pouvoir appliquer ça à n'importe quelle figure (il va falloir montrer que c'est un polygone régulier qui passe par en trouver les sommets).

De même, cliquer sur un patatoïde et calculer un des rectangles qui le borne est encore un autre problème.

- W

Dans mon cas je ne connais pas les sommets, je suis contraint d'utiliser un algo de remplissage ou un algo qui trouve les contours pour déterminer ensuite les sommets. Je ne vois pas d'autres possibilités.

Reste donc à savoir si faire le tour d'un pentagone est plus rapide que de faire mes 5 traits. J'étais parti sur un script pour faire le tour mais je me suis rendu compte qu'il y avait pas mal de condition à mettre en oeuvre : quand je bute sur un bord, je dois aller en haut et/ou en bas et/ou à gauche et/ou à droite, je ne dois pas revenir sur mes pas, etc...

Citation:

---

De même, cliquer sur un patatoïde et calculer un des rectangles qui le borne est encore un autre problème.

---

Oui mais l'idée d'umfred était intéressante à tester.

Citation:

---

Envoyé par LeNarvalo

Une contrainte c'est que 2 polygones peuvent être proche sans se toucher par contre, ce qui rend la tâche compliquée pour délimiter un rectangle autour de celui sur lequel j'aurai cliqué.

---

Est-ce que tes polygones sont différenciés par des couleurs différentes?
si oui, il doit être assez facile de tracer le rectangle englobant en regardant la couleur
même de couleur identique, en regardant dans les 4 directions par rapport à la position du clic, on va tomber à un moment sur un bord (après il faut étendre et les choses se compliquent).

Sinon l'option d'utiliser opencv pour reconnaitre les contours peut-elle être envisager ?
https://geekyisawesome.blogspot.com/...th-opencv.html
Dans cet exemple, le centre est trouvé avec l'aide de cv2.moments(contour)

Code:

---

1 2 3 4

for contour in contours: m = cv2.moments(contour) x = round(m['m10']/m['m00']) y = round(m['m01']/m['m00'])

---

Impressionnant ! =)

Je me mets ça dans mes favoris, je testerais ça !