J'ai besoin de déterminer le plus petit cercle couvrant un groupe de 10 points (plus précisément le diamètre dudit cercle). Quelqu'un a-t-il une idée de la façon dont je peux calculer cela en JSL ?
Merci beaucoup pour la perspicacité! Je ne l'ai pas encore pleinement mis en œuvre, mais il semble que cela pourrait fonctionner pour moi.
Je ne sais pas comment calculer une réponse exacte, mais cela semble être une approximation.
Mise à jour du 15 février 2019 - cela ne fonctionne pas bien s'il n'y a que deux points sur le cercle, voir l'image à la fin.
<STRIKE>see slightly better JSL below</STRIKE>
Circle shrunk to fit the pointsCircle shrunk to fit the pointsCercle réduit pour s'adapter aux points
Voici le cas en deux points qui ne fonctionnera pas bien :
can't find the center very well with only two pointscan't find the center very well with only two pointsje ne trouve pas très bien le centre avec seulement deux points
Vous pouvez tester cela et prendre la moyenne de ces deux points lorsque le troisième point le plus proche n'est pas au rayon, mais cela devient maladroit et pourrait poser plus de problèmes. Si vous avez besoin d'une réponse exacte, vous devriez consulter la réponse Wikipédia. https://en.wikipedia.org/wiki/Smallest-circle_problem
ça risque d'être dur... https://stackoverflow.com/questions/33443006/understanding-algorithm-for-finding-the-smallest-circle-enclosing-points
C'est un peu mieux, mais le L'algorithme de Welzl devrait donner des réponses exactes en moins de temps :
points = J( 33, 2, Random normal( 50, 20 ) ); // make 33 random points
nrows = N Rows( points );
kdt = KDTable( points ); // make a nearest row look up table
center = Mean( points[0, 1] ) || Mean( points[0, 2] ); // pick a starting point
radius = 1e99; // make it big enough
fraction = .2; // fractional distance to move the center towards farthest point
For( i = 1, i < 1000, i++, // usually stops around 700
{indexes, distances} = kdt << knearestrows( nrows, center ); // just need farthest point, but get them all
farthest = indexes[nrows]; // last one is far away
howfar = distances[nrows];
If( howfar > radius, // if oscillating, make the fraction smaller
fraction = fraction * .9; // .5 stops the iterations too soon and gives really poor answers for 2-points on circle case
Show( i, fraction );
If( fraction < 1e-15, // good enough
Break()
);
);
radius = howfar;
// move slightly toward the farthest point
center = center + fraction * (points[farthest, 0] - center);
);
New Window( "Example",
Graph Box(
Frame Size( 500, 500 ),
X Scale( -30, 130 ),
Y Scale( -30, 130 ),
Marker( Marker State( 3 ), points[0, 2], points[0, 1] );
Pen Color( "Blue" );
Circle( {center[2], center[1]}, radius );
fill Color( "red" );
Pen Color( "red" );
Circle( {center[2], center[1]}, 2.0,"FILL" );
for(i=nrows,i>nrows-3,i--,
for(j=i,j>nrows-3,j--,
line({points[indexes[i],2],points[indexes[i],1]},{points[indexes[j],2],points[indexes[j],1]})
)
);
)
);
center is closercenter is closerle centre est plus proche
@kvnsngr ,
Eh bien, je veux vraiment vous aider, mais je vous recommanderais et vous demanderais d'essayer au moins de trouver un bon pseudo-code sur ce pour quoi vous aimeriez que la communauté vous aide. Si vous pouviez proposer un pseudo-code, moi-même ou d'autres membres de la communauté pouvons montrer la voie à suivre pour obtenir le pseudo-code dans JMP.
Pardonnez-moi, je ne suis pas très informé sur le sujet. Mais j'ai trouvé un article de Sven Skyum qui semblait avoir un algorithme efficace.
@kvnsngr ,
Faites-vous référence au plus petit problème de cercle englobant. Si oui, avez-vous en tête un algorithme que vous souhaitez implémenter dans JMP ?
