Discussion:Marche de Jarvis

Autres discussions [liste]

Admissibilité
Neutralité
Droit d'auteur
Article de qualité
Bon article
Lumière sur
À faire
Archives
Commons

Cet article est indexé par le projet Mathématiques.

Les projets ont pour but d’enrichir le contenu de Wikipédia en aidant à la coordination du travail des contributeurs. Vous pouvez modifier directement cet article ou visiter les pages de projets pour prendre conseil ou consulter la liste des tâches et des objectifs.

**Évaluation** de l’article « **Marche de Jarvis** »
Avancement	Importance	pour le projet
Ébauche	À évaluer		Mathématiques (discussion • critères • liste • stats • hist. • comité • stats vues)

Cet article ne comporte pas de liste de tâches suggérées. Vous pouvez saisir une liste de tâches à accomplir (par exemple sous forme d'une liste à puces), puis sauvegarder. Vous pouvez aussi consulter la page d'aide.

Animation[modifier le code]

J'ai remplacé l'animation pour que tout tourne dans le même sens.--Fschwarzentruber (discuter) 24 mars 2016 à 23:29 (CET)[répondre]

Référence[modifier le code]

L'éditeur visuel ne veut pas insérer

R. A. Jarvis, « On the identification of the convex hull of a finite set of points in the plane », Information Processing Letters, vol. 2,‎ 1er mars 1973, p. 18–21 (DOI 10.1016/0020-0190(73)90020-3, lire en ligne)

ː(

--Fschwarzentruber (discuter) 24 mars 2016 à 23:32 (CET)[répondre]

Programme Scilab[modifier le code]

Bonjour,

voici un programme Scilab qui trouve l'enveloppe convexe se faisant avec la marche de Jarvis.

cdang | m'écrire 30 janvier 2017 à 16:45 (CET)[répondre]

Programme Scilab marche_jarvis.sce

//============================================================================
// nom : marche_jarvis.sce
// auteur : Christophe Dang Ngoc Chan
// date de création : 2017-01-23
// dates de modification : 
//
//----------------------------------------------------------------------------
// version de Scilab : 6.0.0
// module Atoms requis : aucun
//----------------------------------------------------------------------------
// Objectif : Déterminer l'enveloppe convexe d'un ensemble de points par la
//    méthode de la marche de Jarvis.
// Entrées : aucune (points générés aléatoirement)
// Sorties : fenêtre graphique avec le résultat et affichage de la durée de
//    traitement
//============================================================================


// ******************
// * Initialisation *
// ******************


// **************
// * Constantes *
// **************

// ********** Génération aléatoire de points **********

n = 10; // nombre de points

// Pour une surface carrée
xmin = 0; xmax = 10; // bornes
ymin = 0; ymax = 10;
largeurx = xmax - xmin;
largeury = ymax - ymin;
// Commenter les deux lignes suivantes pour avoir un disque
points = rand(n, 2, "uniform").*[ones(n, 1)*largeurx, ones(n, 1)*largeury]...
   + [ones(n, 1)*xmin, ones(n, 1)*ymin];

// Pour un disque
r = 10; // rayon
x0 = 5; y0 = 5; // centre du cercle
rayons = r*rand(n, 1, "uniform");
angles = 2*%pi*rand(n, 1, "uniform");
// points = [rayons, rayons].*[cos(angles), sin(angles)]; // décommenter
// cette ligne pour avoir un disque


// *************
// * Fonctions *
// *************

// ********** marche_jarvis **********

function [ind_env_sens] = marche_jarvis_sens_unique(pts, sens)
    // détermine la moitié de l'enveloppe convexe
    //     par l'algorithme de la marche de Jarvis
    // entrées : pts : matrice n × 2 de réels, ensemble de points [X, Y]
    // sens : entier, +1 ou -1 selon le sens de parcours
    // sorties : ind_env_sens : vecteur d'entiers,
    //    indices des points de l'enveloppe convexe
    n = size(pts, "r");  // nombre de points
    if (sens == 1)
        then indice_courant = 1;
            indice_stop = n;
            ind_env_sens = [1];
        else indice_courant = n;
            indice_stop = 1
            ind_env_sens = [n];
    end
    taille_env = 1; // nombre de points dans l'enveloppe
    condition = %t;
    while condition
        taille_env = taille_env + 1;
        pts_foo = pts - ones(n, 1)*pts(indice_courant, :);
        pts_foo(indice_courant, :) = [];
        angle_polaire = atan(-pts_foo(:, 1)*sens, pts_foo(:, 2)*sens);
        [angle_extr, indice_extr] = min(angle_polaire);
        if indice_extr >= indice_courant
            then indice_extr = indice_extr + 1;
        end
        condition = (indice_extr <> indice_stop);
        ind_env_sens(taille_env) = indice_extr;
        indice_courant = indice_extr;
    end
endfunction

function [env_cvx] = marche_jarvis(pts)
    // détermine l'enveloppe convexe
    //     par l'algorithme de la marche de Jarvis
    // entrées : pts : matrice n × 2 de réels, ensemble de points [X, Y]
    // sorties : env_cvx : matrice ? × 2 de réels, points de l'enveloppe convexe
    
    n = size(pts, "r");  // nombre de points
    pts = gsort(pts, "lr", "i"); // tri
    
    // progression de xmin vers xmax
    ind_env_positif = marche_jarvis_sens_unique(pts, +1)
    
    // progression de xmax vers xmin
    ind_env_negatif = marche_jarvis_sens_unique(pts, -1)
    
    // Bilan
    ind_env = [ind_env_positif', ind_env_negatif']
    env_cvx = pts(ind_env, :);
endfunction

// **********************
// * Programe principal *
// **********************

// ********** Détermination du cercle minimum **********

tic();
enveloppe = marche_jarvis(points); 
duree = toc();

// ********** Affichage du résultat **********

figure(0);
clf();
plot(points(:, 1), points(:, 2), "+"); // points des données

plot([enveloppe(:, 1) ; enveloppe(1, 1)], [enveloppe(:, 2) ; enveloppe(1, 2)]);

disp("Durée du calcul : "+string(duree)+" s. pour "+string(n)+" points");