Path: buffer2.nntp.dca1.giganews.com!buffer1.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Tue, 11 Jan 2022 16:34:16 -0600
Newsgroups: fr.comp.lang.python
Subject: Enveloppe convexe marche de jarvis problème
X-poster: PEAR::Net_NNTP v1.5.0 (stable)
From: ldrieu <nospam_loic.durieu@gmail.com.invalid>
Content-Type: text/plain; charset=windows-1252
Content-Transfer-Encoding: 8bit
Organization: !No_Organization!
Message-ID: <YaadnZ55Qo11mEP8nZ2dnUU7_83NnZ2d@giganews.com>
Date: Tue, 11 Jan 2022 16:34:16 -0600
Lines: 190
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-Q1XDwZeNdBEsWxkrpk+t95GDUGD5Cm8ysWAmtCp6+eAnKHjAHLO8w6Mk2gAFsS4sqrOKvnjgyP+YnOy!f2FqcgRBqScSLmaMASCRnx4Ciq483YgbN8rHc+kE5zACBDTQdileiLHuy0W5NoHN4pTvGfLK8C2j
X-Complaints-To: abuse@giganews.com
X-DMCA-Notifications: http://www.giganews.com/info/dmca.html
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
Bytes: 6098
X-Original-Lines: 177

Bonjour,
je suis débutant en python, je dois réaliser un programme me permettant a terme
de trouver l' enveloppe convexe d'une liste de points. 
j'ai essayé de coder l'algorithme de la marche de Jarvis mais celui-ci, ne
fonctionne pas.
Je ne vois pas comment faire pour avancer.
je ne dois pas utiliser de variable globale( à terme le programme aura une  IHM
affin de choisir un fichier csv).
Je n'ai pas non plus vu la notion de récursivité.
Auriez vous des pistes d'améliorations ?
merci d'avance.


La fonction envellopeconvexe3 est la plus aboutie les versions précédentes 
ayant encore plus de soucis. 
##Imports:
from math import cos,acos,sqrt
import matplotlib.pyplot as plt

##liste test
liste1= [[150, 200], [122, -232], [-200, 80], [138, 157], [-148, 75], [82,
-178], [129, 126], [-112, 73], [57, -142], [121, 100], [-84, 70], [40, -114],
[112, 80], [-61, 68], [28, -91], [104, 63], [-43, 65], [20, -72], [96, 49],
[-28, 61], [14, -56], [87, 38], [-16, 58], [11, -43], [80, 29], [-5, 54], [9,
-32], [72, 23], [3, 50], [9, -22], [65, 18], [9, 46], [9, -14], [59, 14], [15,
42], [10, -8], [54, 12], [19, 39], [11, -3], [49, 10], [22, 35], [12, 2], [45,
9], [24, 32], [14, 5], [42, 9], [26, 30], [15, 8], [39, 9], [28, 27], [17, 10]]

##fonctions intermédiaires
def coords(A, B):                     #on calculs les coordonnées d'un vecteur
avec les deux points
    vab=[B[0]-A[0],B[1]-A[1]]
    return vab


def Normevecteur(a,b):                               #on calculs la norme d'un
vecteur/la distance entre les deux points.
    Nab=sqrt((b[0]-a[0])**2+(b[1]-a[1])**2)
    return Nab
def pscalairecoords(A,B):                            #on calculs le produit
scalaire entre deux vecteurs par
    P=A[0]*B[0]+A[1]*B[1]
    return P

def angleentretroispoints(A,B,C):
    # Vab=[]
    # Vac=[]
    # Nab=0
    # Nac=0
    Vab=coords(A,B)
    Vac=coords(A,C)
    Nab=Normevecteur(A,B)
    Nac=Normevecteur(A,C)
    PS=pscalairecoords(Vab,Vac)
    CosX=PS/(Nab*Nac)
    X = acos(CosX)
    # print(Vab,Vac,Nab,Nac,PS,CosX,X)
    return     [A,B,X]


def pointleplusagauche1(liste):
    k = [0,0]
    indice = 0
    for i in range (len(liste)):
        if liste[i][0]< k[0]:
            k[0]=liste[i][0]
            indice = i
        A=liste[indice]
    return A

def envellopeconvexe(liste):
    pointàrelier=[]
    A=pointleplusagauche1(liste)
    B=[A[0],A[1]-1]
    pointàrelier.append(A)
    j=0
    while j!= pointleplusagauche1(liste):
        H=[]
        for i in range (len(liste)):
            z=angleentretroispoints(A,B,liste[i])
            H.append([z[0],z[1],[liste[i][0],liste[i][1]],z[2]])
        for i in range (len(H)):
            max=H[0]
            p=[0]
            if H[i][3]>max:
                max=H[i][3]
                p=H[i]
        A=p[2]
        B=p[0]
        pointàrelier.append(A)
        j=p[2]
    return pointàrelier




##test



def angleentretroispoints1(A,B,C):#bonne version de verif d'angle
    # Vab=[]
    # Vac=[]
    # Nab=0
    # Nac=0
    Vab=coords(A,B)
    Vac=coords(A,C)
    Nab=Normevecteur(A,B)
    Nac=Normevecteur(A,C)
    if Nab==0 or Nac==0 or Nac==Nab:
        return
    PS=pscalairecoords(Vab,Vac)
    CosX=PS/(Nab*Nac)
    X = acos(CosX)
    # print(Vab,Vac,Nab,Nac,PS,CosX,X)
    return     [A,B,X]



def envellopeconvexe3(liste):
    pointàrelier=[]
    A=pointleplusagauche1(liste)
    B=[A[0],A[1]-1]
    pointàrelier.append(A)
    j=0
    while j!= pointleplusagauche1(liste):
        H=[]
        m=liste.index(A)
        k=liste
        del k[m]
        print (k)
        for i in range(len(k)):
            z=angleentretroispoints1(A,B,liste[i])
            H.append([z[0],z[1],[liste[i][0],liste[i][1]],z[2]])
            # print(H)
        for i in range (len(H)):
            max=H[0][3]
            p=H[0]
            if H[i][3]>max:
                max=H[i][3]
                p=H[i]
                print(p)
            print(p)
        A=p[2]
        B=p[0]
        pointàrelier.append(A)
        j=p[2]
    print(pointàrelier)
    return pointàrelier

def affichage(liste):
    envellopeconvexe3(liste)
    

plt.plot([-200, 150, 122, 17,28,138,-148],[80 ,200,-232,10,27,157,75],'-gs')#
green carré
# plt.plot([-7,3,2.5,-7],[3.5,1,3.5,1.5],'-gs')# green carré
plt.show()



# def testx():
#     liste=[1,2,3,4,5,6,7]
#     point=5
#     compteur = 0
#     for i in range (len(liste)):
#         if point==liste[i]:
#             compteur = i
#     for i in range(0,compteur):
#         print(liste[i])
#     for i in range(compteur+1,len(liste)):
#         print(liste[i])
#     #print(compteur)
#
# def testxy():
#     listeo=[1,2,3,4,5,6,7,8,9]
#     P=5
#     i=listeo.index(P)
========== REMAINDER OF ARTICLE TRUNCATED ==========