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

任意多边形的最小外接圆(注意最小两字）
通常的外接圆是讲得是所有顶点在圆上,不存在最小两字,地图上存在N个点,我想用一个最小的圆将其全部圈起来,怎么求,给数学算法就行.
billpun 1年前 已收到2个回答 举报
赞

suguolin1 幼苗

共回答了12个问题采纳率：83.3% 举报

这是离散几何问题.具体是这样做的:
多边形可不妨设为凸的,因为显然有凹多边形跟其凸包多边形的最小外接圆相同.算法上可以先求出给定多边形的凸包.
设P是一个给定的凸n边形.考察其任意三个顶点决定的圆,至多有{n choose 3}个不同的圆.
设这些圆中能盖住P的为圆C_1,圆C_2,...,圆C_m.
找出那个最小的圆C_i即可,这里谁大谁小看直径,最小的C_i可能不唯一.

1年前 追问

3

billpun 举报

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

举报 suguolin1

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

等待我们的爱 幼苗

共回答了2个问题 举报

最小圆覆盖
1.在点集中任取3点A,B,C
2.作一个包含A,B,C三点的最小圆,圆周可能通过这3点，也可能只通过其中两点,但包含第3点.后一种情况圆周上的两点一定是位于圆的一条直径的两端。
3. 在点集中找出距离第2步所建圆圆心最远的D点，若D点已在圆内或圆周上，则该圆即为所求的圆，算法结束.否则，执行第4步。
4. 在A,B,C,D中选3个点,使由它们生成的一...

1年前

0
可能相似的问题

你能帮帮他们吗

精彩回答

Copyright © 2024 YULUCN.COM - 雨露学习互助 - 18 q. 2.648 s. - webmaster@yulucn.com