113680_zh-CN

liliconcom

最小覆盖圈

我需要确定覆盖一组 10 个点的最小圆（特别是所述圆的直径）。 有谁知道我如何在 JSL 中计算这个？

回复：最小覆盖圈

非常感谢您的洞察力！ 我还没有完全实现这一点，但似乎这可能对我有用。

回复：最小覆盖圈

我找到的最佳描述： https://www.nayuki.io/page/smallest-enclosure-circle具有多种语言的实现和页面上的实时演示。

回复：最小覆盖圈

不知道如何计算一个确切的答案，但这似乎迭代到一个近似值。

更新，2019 年 2 月 15 日 - 如果圆上只有两个点，这将无法正常工作，请参见最后的图片。

 

<STRIKE>see slightly&nbsp;better&nbsp;JSL&nbsp;below</STRIKE>

Circle shrunk to fit the points圆圈缩小以适合点

这是两个不能正常工作的案例：

can'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-enclosure-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 closer中心更近

回复：最小覆盖圈

@kvnsngr ,
好吧，我真的很想帮助你，但是我建议并要求你尝试并至少想出你希望社区帮助的好的伪代码。 如果你能想出一个伪代码，我或其他社区成员可以带路如何在 JMP 中实现伪代码。

 

回复：最小覆盖圈

原谅我，我对这个话题不是很了解。 但我找到了一篇论文Sven Skyum 似乎有一个高效的算法。

回复：最小覆盖圈

@kvnsngr ,
你指的是最小的封闭圆问题。 如果是，您是否有想在 JMP 中实现的算法？