Ich muss den kleinsten Kreis bestimmen, der eine Gruppe von 10 Punkten abdeckt (insbesondere den Durchmesser des Kreises). Hat jemand eine Idee, wie ich das in JSL berechnen kann?
Vielen Dank für den Einblick! Ich habe dies noch nicht vollständig implementiert, aber es scheint, als würde es für mich funktionieren.
Ich weiß nicht, wie ich eine genaue Antwort berechnen soll, aber dies scheint eine Annäherung zu sein.
Update, 15. Februar 2019 – das funktioniert nicht gut, wenn sich nur zwei Punkte auf dem Kreis befinden, siehe Bild am Ende.
<STRIKE>see slightly better JSL below</STRIKE>
Circle shrunk to fit the pointsCircle shrunk to fit the pointsDer Kreis wurde verkleinert, um ihn an die Punkte anzupassen
Hier ist der Zwei-Punkte-Fall, der nicht gut funktionieren wird:
can't find the center very well with only two pointscan't find the center very well with only two pointsIch kann mit nur zwei Punkten das Zentrum nicht so gut finden
Sie könnten dies testen und den Durchschnitt dieser beiden Punkte ermitteln, wenn der drittnächste Punkt nicht auf dem Radius liegt, aber das wird umständlich und könnte zu weiteren Problemen führen. Wenn Sie eine genaue Antwort benötigen, sollten Sie sich die Wikipedia-Antwort ansehen. https://en.wikipedia.org/wiki/Smallest-circle_problem
könnte schwer sein... https://stackoverflow.com/questions/33443006/understanding-algorithm-for-finding-the-smallest-circle-enclosing-points
Das ist etwas besser, aber das Der Welzl-Algorithmus sollte in kürzerer Zeit genaue Antworten liefern :
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 closerZentrum ist näher
@kvnsngr ,
Nun, ich möchte Ihnen wirklich helfen, würde Ihnen jedoch empfehlen und darum bitten, dass Sie versuchen, zumindest einen guten Pseudocode zu entwickeln, bei dem Sie sich die Hilfe der Community wünschen. Wenn Sie einen Pseudocode entwickeln könnten, können ich oder andere Community-Mitglieder Ihnen zeigen, wie Sie den Pseudocode in JMP erreichen.
Verzeihen Sie mir, ich bin über das Thema nicht sehr informiert. Aber ich habe einen Artikel von gefunden Sven Skyum schien einen effizienten Algorithmus zu haben.
@kvnsngr ,
Beziehen Sie sich auf das Problem des kleinsten umschließenden Kreises? Wenn ja, haben Sie einen Algorithmus im Sinn, den Sie in JMP implementieren möchten?
