任意多边形的最小外接圆(注意最小两字)通常的外接圆是讲得是所-查字典问答网
分类选择

来自何勋桂的问题

  任意多边形的最小外接圆(注意最小两字)通常的外接圆是讲得是所有顶点在圆上,不存在最小两字,地图上存在N个点,我想用一个最小的圆将其全部圈起来,怎么求,给数学算法就行.

  任意多边形的最小外接圆(注意最小两字)

  通常的外接圆是讲得是所有顶点在圆上,不存在最小两字,地图上存在N个点,我想用一个最小的圆将其全部圈起来,怎么求,给数学算法就行.

3回答
2020-05-22 15:08
我要回答
请先登录
汪慧英

  这是离散几何问题.具体是这样做的:

  多边形可不妨设为凸的,因为显然有凹多边形跟其凸包多边形的最小外接圆相同.算法上可以先求出给定多边形的凸包.

  设P是一个给定的凸n边形.考察其任意三个顶点决定的圆,至多有{nchoose3}个不同的圆.

  设这些圆中能盖住P的为圆C_1,圆C_2,...,圆C_m.

  找出那个最小的圆C_i即可,这里谁大谁小看直径,最小的C_i可能不唯一.

2020-05-22 15:10:54
何勋桂

  你没有详细思考这个问题。我的开始想法是,能包含这些些点的最小外凸多边形,这个能解决。你所说的解决方案明显不对,简单的例子,一个正6多边形,将其中的一对对边拉长,你的解决方案错了。。我想了很久。没想到好的方法。用数学应该能解决,给点点集{pn(xn,yn)}有(xn-x)^2+(yn-y)^2

2020-05-22 15:12:32
汪慧英

  你说的对我答错了。任给一个钝角三角形,欲求的圆都不外接。而我的记号里面Ci的集合也可能是空集。通过收缩外面大圆的思想,显见所求的圆至少经过凸包的两个顶点。另一方面,其直径长度至少跟凸包直径一样长。你给的例子暗含着:如果给定的凸多边形有一个直径,使得以它为直径的圆盖住P,那么这个圆是所求的最小圆中的一个。这个矫正包含了凸包是钝角三角形的情况。其它的情况存在。

2020-05-22 15:13:16

最新问答

推荐文章

猜你喜欢

附近的人在看

推荐阅读

拓展阅读

  • 大家都在看
  • 小编推荐
  • 猜你喜欢
  •