Code : Tout sélectionner
size(0,5cm);
real a=6, b=4;
path polygon(pair[] c)
{
guide g;
for (int k=0; k < c.length; ++k)
g=g--c[k];
return g--cycle;
}
pair pivot(pair[] c)
{
real[][] coords;
for (int i=0; i < c.length; ++i) coords.push(new real[] {c[i].y,c[i].x,i});
return c[round(sort(coords)[0][2])];
}
pair[] polarSort(pair[] c, int pivot=-1)
{
int n=c.length;
if(pivot >= n) abort("polarSort: pivot to large.");
pair O;
real[][] polar;
if(pivot < 0) {
O=pivot(c);
for (int i=0; i < n; ++i)
polar.push(new real[] {degrees(c[i]-O,false),abs(c[i]-O),i});
polar=sort(polar);
} else {
O=c[pivot]; // Origine of the polar coordinates system
real[][] polp, polm;
for (int i=0; i < n; ++i) {
real d;
if(i != pivot) {
d=degrees(c[i]-O,false);
if(d > 180) d=d-360;
if(d > 0) // 0 <= angle <= 180
polp.push(new real[] {d,abs(c[i]-O),i});
else // 180 < angle < 0
polm.push(new real[] {d,abs(c[i]-O),i});
}
}
// Sort the angles in ascending order;
polp=sort(polp);
polm=sort(polm);
void append(real[][] a, real[][] b, real[][] c)
{
polar=copy(a);
polar.append(b);
polar.append(c);
}
if(polp.length > 0 && polm.length > 0) {
pair p1=c[round(polp[0][2])],
p2=c[round(polm[polm.length-1][2])],
p3=1/3*(O+p1+p2);
// We must be careful in rotation to join the paths
if((p2.x-p1.x)*(p3.y-p1.y)-(p2.y-p1.y)*(p3.x-p1.x) > 0)
append(new real[][]{{0,0,pivot}}, polp, polm);
else
append(new real[][]{{0,0,pivot}}, polm, polp);
} else
append(new real[][]{{0,0,pivot}}, polp, polm);
}
return sequence(new pair(int i){return c[round(polar[i][2])];}, n);
}
pair[] hull(pair[] c, real depthMin=infinity, real depthMax=0, real angleMin=360, real angleMax=0, int pivot=-1)
{
pair minb, maxb, center;
if(depthMax > 0) {
minb=minbound(c);
maxb=maxbound(c);
center=(minb+maxb)/2;
}
real dbound(pair M, pair dir)
{
return abs(M-minb-realmult(rectify(dir-center),maxb-minb));
}
pair[] nodes;
int n=c.length;
nodes=polarSort(c,pivot);
nodes.cyclic=true;
bool modified;
do {
modified=false;
for (int i=0; i < n; ++i) {
pair p1=nodes[i], p2=nodes[i+1], p3=nodes[i+2];
if((p2.x-p1.x)*(p3.y-p1.y)-(p2.y-p1.y)*(p3.x-p1.x) < 0)
if((depthMax <= 0 || dbound(p2,0.5*(p1+p3)) > depthMax) ||
(depthMin == infinity || dbound(p2,0.5*(p1+p3)) < depthMin) ||
(angleMin >=360 || (degrees(p3-p2)-degrees(p1-p2) < angleMin)) ||
(angleMax <=0 || (degrees(p3-p2)-degrees(p1-p2) > angleMax))) {
nodes.delete(i+1);
modified=true;
break;
}
}
} while(modified);
return nodes;
}
pair[] randompairs(int n=25)
{
pair[] c = {};
srand(seconds());
for (int k=0; k<n+1; ++k)
{
c.push((unitrand()*a,unitrand()*b));
}
return c;
}
pair[] points = randompairs();
for (pair p:points) { dot(p); };
draw(polygon(hull(points)),red);