Tengo la necesidad de determinar el círculo más pequeño que cubre un grupo de 10 puntos (específicamente el diámetro de dicho círculo). ¿Alguien tiene una idea de cómo puedo calcular esto en JSL?
No sé cómo calcular una respuesta exacta, pero esto parece repetirse en una aproximación.
Actualización, 15feb2019: esto no funciona bien si solo hay dos puntos en el círculo, vea la imagen al final.
<STRIKE>see slightly better JSL below</STRIKE>
Circle shrunk to fit the pointsCírculo encogido para encajar los puntos.
Aquí está el caso de dos puntos que no va a funcionar bien:
can't find the center very well with only two pointsNo puedo encontrar el centro muy bien con solo dos puntos.
Podría hacer una prueba para eso y tomar el promedio de esos dos puntos cuando el tercer punto más cercano no esté en el radio, pero eso se está volviendo torpe y podría tener más problemas. Si necesita una respuesta exacta, debe buscar en la respuesta de wikipedia. https://en.wikipedia.org/wiki/Smallest-circle_problem
podría ser difícil ... https://stackoverflow.com/questions/33443006/understanding-algorithm-for-finding-the-smallest-circle-enclosing-points
Esto es un poco mejor, pero el El algoritmo Welzl debería dar respuestas exactas en menos tiempo. :
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 closerel centro esta mas cerca
@kvnsngr ,
Bueno, realmente quiero ayudarte, sin embargo, te recomendaría y te pediría que lo intentes y al menos creas un buen pseudo código sobre en qué te gustaría que ayudara la comunidad. Si pudiera crear un pseudocódigo, yo u otros miembros de la comunidad pueden liderar el camino para lograr el pseudocódigo en JMP.
Perdóname, no estoy muy informado sobre el tema. Pero encontré un papel por Sven Skyum que parecía tener un algoritmo eficiente.
@kvnsngr ,
¿Te refieres al problema del círculo cerrado más pequeño? En caso afirmativo, ¿tiene un algoritmo en mente que desea implementar en JMP?
Thanks a lot for the insight! I haven't fully implimented this yet but it seems like this might work for me.
