Bonsoir,

Le 28 avril 2008, Bertrand Lenoir-Welter écrivit :

Ça peut être plus facile à faire en coordonnées polaires, centrée sur
le barycentre des points.

Oui, j'ai envisagé cette solution, mais il est évident que le problème
revient à décider si un point à l'intérieur de l'enveloppe doit
déterminer une concavité ou non.
[...]
Y'a plus qu'à coder et essayer.

Je ne me suis pas (encore) penché sur la question de la profondeur de la
concavité mais cela ne devrait plus poser de gros problèmes.
100 enveloppes pour un même nuage de points:
ftp://download.tuxfamily.org/piprim/temp/enveloppe.pdf

Le code (en Asymptote: http://asymptote.sourceforge.net/ )
8<------8<------8<------8<------8<------8<------8<------8<------8<------
size(10cm,0);
import stats;
import animation;
animation A;
// A.global=false;
settings.outformat="pdf";

pair[] cloud;
int nbpt=100;

// Generate random points.
for (int i=0; i < nbpt; ++i)
  cloud.push((10*unitrand(),10*unitrand()));

// Start animation
for (int i=0; i < nbpt; ++i) {
  pair O=cloud[i]; // Origine of the polar coordinates system
  real[][] polp, polm;

  // Convert cartesian to polar
  for (int j=0; j < nbpt; ++j) {
    real d;
    if(j != i) {
      d=degrees(cloud[j]-O,false);
      d=d > 180 ? d-360 : d;
      if(d > 0) // 0 <= angle <= 180
        polp.push(new real[] {d,abs(cloud[j]-O)});
      else // 180 < angle < 0
        polm.push(new real[] {d,abs(cloud[j]-O)});
    }
  }

  // Sort the angles in ascending order;
  polp=sort(polp);
  polm=sort(polm);
  guide[] g={nullpath,nullpath};

  save(); // Start a blank picture

  // Generate the top path (0 <= angle <= 180);
  for (int j=0; j < polp.length; ++j) {
    pair p=polp[j][1]*dir(polp[j][0]);
    if(j==0) dot(O+polp[j][1]*dir(polp[j][0]),3mm+yellow);
    g[0]=g[0]--p;
  }
  // Generate the bottom path (180 < angle < 0);
  for (int j=0; j < polm.length; ++j) {
    pair p=polm[j][1]*dir(polm[j][0]);
    if(j==0) dot(O+polm[j][1]*dir(polm[j][0]),3mm+yellow);
    g[1]=g[1]--p;
  }

  guide env; // Final envelop

  if(length(g[0]) > 0 && length(g[1]) > 0) {
    // No empty path
    // We must be careful in rotation to join the paths
    pair p1=point(g[0],0), p2=relpoint(g[1],1);
    pair p=1/3*(p1+p2);
    if(windingnumber((0,0)--p1--p2--cycle,p) > 0) env=g[0]--g[1]--(0,0)--cycle;
    else env=g[1]--g[0]--(0,0)--cycle;
  } else env=g[1]--g[0]--(0,0)--cycle; // One empty path => no problem

  // Fill and draw the envelop
  filldraw(shift(O)*env,lightgrey);
  // Plot the cloud and the "point of view".
  dot(cloud,dotsize(black)/2+red);
  dot(O,green);

  // Add a the picture in the animation
  A.add();
  restore();
}

// Generate the animation
A.movie();
8<------8<------8<------8<------8<------8<------8<------8<------8<------
--
   Philippe Ivaldi.
http://piprim.tuxfamily.org/