【一道数学题】已知一个不规则图形的所有顶点坐标

---

锐角三角形和直角三角形就是外接圆，钝角三角形就是以最长边为半径的圆。

但是任意多边形呢……
比如，把多边形的所有顶点放入一个列表，然后任取三个点，把这三个点根据上一个帖子的原则找到圆，然后检测列表中所有的点，如果这个点在这个圆之内，就把这个点从列表中排除掉。然后，更换一个点，再组成一个三角形。直到列表中只剩下三个点为止。

前面的三角形没有什么问题,但是对于多边形这样未必可以获取你所需的最小圆,你算的圆一定不包含所有点.

我可以补充一下:
无论其中三个点构成直角,锐角,钝角三角形我们都采取过三个点做圆的办法,这样得到的圆未必是最小的,但是一定可以包住所有的点.而且当点很多且大致均匀分布时,这样做的圆很接近最小的圆.
具体方法是:
如果是计算机程序完成的话,不妨简单的做:
假定总共有n个点,n选3,总共有c[n,3]=n!/((n-3)!*3!)中不同的选法.可以得到对应数量的圆,判断哪些圆包含了所有的点(不失一般性,可能不止一个圆满足包含了所有的点,但是至少存在一个圆包含了所有的点),然后在这些圆中找半径最小的圆,就是我们需要的结果了.再重申一遍,这样的圆不一定是最小的,如果不是,就一定是很接近最小的圆).
答案很劲爆，重心就可以了！这里重心的求法是，多边形的所有点，包括顶点和非顶点（因为是位图，就像用Windows画笔画出的多边形，很容易就得到所有的点），坐标相加求平均数，就是重心。重心为圆心，最远点为半径，就是所求的结果了。除了一些极端分布不均的图形，比如圆形上边伸出一根长棍，否则结果总是符合唯一和半径尽量小。
先将其分为多个三角形，求出其中的外心，在将中心，将其连接，在分成三角形就中心，直到剩1个中心及为所求。锐角三角形和直角三角形就是外接圆，钝角三角形就是以最长边为半径的圆。

但是任意多边形呢……
比如，把多边形的所有顶点放入一个列表，然后任取三个点，把这三个点根据上一个帖子的原则找到圆，然后检测列表中所有的点，如果这个点在这个圆之内，就把这个点从列表中排除掉。然后，更换一个点，再组成一个三角形。直到列表中只剩下三个点为止。

前面的三角形没有什么问题,但是对于多边形这样未必可以获取你所需的最小圆,你算的圆一定不包含所有点.

我可以补充一下:
无论其中三个点构成直角,锐角,钝角三角形我们都采取过三个点做圆的办法,这样得到的圆未必是最小的,但是一定可以包住所有的点.而且当点很多且大致均匀分布时,这样做的圆很接近最小的圆.
具体方法是:
如果是计算机程序完成的话,不妨简单的做:
假定总共有n个点,n选3,总共有c[n,3]=n!/((n-3)!*3!)中不同的选法.可以得到对应数量的圆,判断哪些圆包含了所有的点(不失一般性,可能不止一个圆满足包含了所有的点,但是至少存在一个圆包含了所有的点),然后在这些圆中找半径最小的圆,就是我们需要的结果了.再重申一遍,这样的圆不一定是最小的,如果不是,就一定是很接近最小的圆).
先将其分为多个三角形，求出其中的外心，在将中心，将其连接，在分成三角形就中心，直到剩1个中心及为所求。
锐角三角形和直角三角形就是外接圆，钝角三角形就是以最长边为半径的圆。

但是任意多边形呢……
比如，把多边形的所有顶点放入一个列表，然后任取三个点，把这三个点根据上一个帖子的原则找到圆，然后检测列表中所有的点，如果这个点在这个圆之内，就把这个点从列表中排除掉。然后，更换一个点，再组成一个三角形。直到列表中只剩下三个点为止。

前面的三角形没有什么问题,但是对于多边形这样未必可以获取你所需的最小圆,你算的圆一定不包含所有点.

我可以补充一下:
无论其中三个点构成直角,锐角,钝角三角形我们都采取过三个点做圆的办法,这样得到的圆未必是最小的,但是一定可以包住所有的点.而且当点很多且大致均匀分布时,这样做的圆很接近最小的圆.
具体方法是:
如果是计算机程序完成的话,不妨简单的做:
假定总共有n个点,n选3,总共有c[n,3]=n!/((n-3)!*3!)中不同的选法.可以得到对应数量的圆,判断哪些圆包含了所有的点(不失一般性,可能不止一个圆满足包含了所有的点,但是至少存在一个圆包含了所有的点),然后在这些圆中找半径最小的圆,就是我们需要的结果了.再重申一遍,这样的圆不一定是最小的,如果不是,就一定是很接近最小的圆).
花了1小时研究出的给分吧！！