10개 점 그룹을 포함하는 가장 작은 원(구체적으로 해당 원의 직경)을 결정해야 합니다. JSL에서 이것을 어떻게 계산할 수 있는지 아는 사람이 있나요?
통찰력을 주셔서 감사합니다! 나는 이것을 아직 완전히 구현하지는 않았지만 이것이 나에게 효과가 있을 것 같습니다.
정확한 답을 계산하는 방법을 모르지만 이는 근사치를 반복하는 것 같습니다.
2019년 2월 15일 업데이트 - 원에 점이 두 개만 있으면 제대로 작동하지 않습니다. 끝 그림을 참조하세요.
<STRIKE>see slightly better JSL below</STRIKE>
Circle shrunk to fit the pointsCircle shrunk to fit the points원이 점에 맞게 축소되었습니다.
잘 작동하지 않는 두 가지 사례는 다음과 같습니다.
can't find the center very well with only two pointscan't find the center very well with only two points두 점만으로는 중심을 잘 찾을 수 없습니다
세 번째로 가까운 지점이 반경에 없을 때 이를 테스트하고 두 지점의 평균을 구할 수 있지만 이는 점점 더 어려워지고 더 많은 문제가 발생할 수 있습니다. 정확한 답변이 필요하면 위키피디아 답변을 살펴봐야 합니다. https://en.wikipedia.org/wiki/Smallest-circle_problem
힘들지도.. https://stackoverflow.com/questions/33443006/understanding-algorithm-for-finding-the-smallest-circle-enclosing-points
이게 좀 나아졌지만, Welzl 알고리즘은 더 짧은 시간에 정확한 답변을 제공해야 합니다. :
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 closer센터가 더 가까워요
@kvnsngr ,
글쎄요, 저는 정말로 당신을 돕고 싶습니다. 그러나 저는 당신이 커뮤니티에서 도움을 받기를 원하는 것에 대해 최소한 좋은 의사 코드를 생각해 보도록 권장하고 요청하고 싶습니다. 의사 코드를 생각해 낼 수 있다면 저나 다른 커뮤니티 구성원이 JMP에서 의사 코드를 얻는 방법을 주도할 수 있습니다.
죄송합니다. 저는 그 주제에 대해 잘 알지 못합니다. 그런데 내가 한 논문을 찾았어. 효율적인 알고리즘을 가지고 있는 것 같은 Sven Skyum.
@kvnsngr ,
가장 작은 둘러싸는 원 문제를 언급하고 있습니까? 그렇다면 JMP에서 구현하려는 알고리즘을 염두에 두고 있습니까?
