Discussion:Marche de Jarvis
Dernier commentaire : il y a 7 ans par Cdang dans le sujet Programme Scilab
Autres discussions [liste]
- Admissibilité
- Neutralité
- Droit d'auteur
- Article de qualité
- Bon article
- Lumière sur
- À faire
- Archives
- Commons
Animation
modifierJ'ai remplacé l'animation pour que tout tourne dans le même sens.--Fschwarzentruber (discuter) 24 mars 2016 à 23:29 (CET)
Référence
modifierL'é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)
ː(
Programme Scilab
modifierBonjour,
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)
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");