Ho bisogno di determinare il cerchio più piccolo che copre un gruppo di 10 punti (in particolare il diametro di detto cerchio). Qualcuno ha un'idea di come posso calcolare questo in JSL?
Non so come calcolare una risposta esatta, ma questo sembra ripetere un'approssimazione.
Update, 15feb2019 - questo non funziona bene se ci sono solo due punti sul cerchio, vedi l'immagine alla fine.
<STRIKE>see slightly better JSL below</STRIKE>
Circle shrunk to fit the pointsIl cerchio si restringe per adattarsi ai punti
Ecco il caso in due punti che non funzionerà bene:
can't find the center very well with only two pointsnon riesco a trovare il centro molto bene con solo due punti
Potresti provare per quello e prendere la media di quei due punti quando il terzo punto più vicino non è al raggio, ma questo diventa sempre più goffo e potrebbe avere più problemi. Se hai bisogno di una risposta esatta, dovresti esaminare la risposta di wikipedia. https://en.wikipedia.org/wiki/Smallest-circle_problem
potrebbe essere difficile ... https://stackoverflow.com/questions/33443006/understanding-algorithm-for-finding-the-smallest-circle-enclosing-points
Questo è un po 'meglio, ma il L'algoritmo di Welzl dovrebbe dare risposte esatte in meno tempo :
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 closeril centro è più vicino
@kvnsngr ,
Beh, voglio davvero aiutarti, tuttavia ti raccomando e ti chiedo di provare e almeno di trovare un buon pseudo-codice su cosa vorresti che la comunità ti aiutasse. Se si riuscisse a creare uno pseudo-codice, io o altri membri della comunità possiamo aprire la strada a come ottenere lo pseudocodice in JMP.
Perdonami, non sono molto informato sull'argomento. Ma ho trovato un documento di Sven Skyum sembrava avere un algoritmo efficace.
@kvnsngr ,
Ti riferisci al più piccolo problema del cerchio di chiusura. Se sì, hai in mente un algoritmo che vuoi implementare in JMP?
Thanks a lot for the insight! I haven't fully implimented this yet but it seems like this might work for me.
