已知n个点坐标，求覆盖所有点的最小面积圆的算法代码

Question

這個算法如何?時間關系沒細細考慮.
遍歷所有的點,找到距離最遠的兩個點.  Math.Sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2))然后,用這兩個點的中點做圓心,距離的一般做半徑畫圓.....

Answer 1

http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/CG-Applets/Center/centercli.htm

Answer 2

唉，这个不是一个很简单的graph theory的题吗？最简单的方法是取4个方向的极点，东南西北，从南极点，为A开始，往东扫，看是否每一点都在东极点称B的左边（用vector的左手定律还是右手定律算），如果有点一点是在右边，那么这一点就是边距的下一点。如果找到这点（叫C），就停止，就把C加到结果list里面，那么现在结果里面是 A->C->B，然后就看 CB，再扫，如果没有点在 CB line 右边，那么就把北极点 D 加入，从 BD 开始扫，没有点在 BD 右边，就把西极点 E 加入，从 DE 开始扫。最后假设你的list里面有 ACBDE，这个就是能够包含所有的点的一个多边形。取多边形的中点，然后取一个最长的为半径，就可以得到一个圆形了。有更好的算法，现在不记得了。但是这个算法是最容易实现和最简单的

Answer 3

因为理论与计算的误差，在绘图的时候将点的半径设置为大约0.00294L    （L是N点之间的最大距离）
  

Answer 4

namespace 覆盖n点坐标的最小的圆算法
{
//中间是包含的类}

Answer 5

class SimpleDemon
    {
        static void Main(string[] args)
        {
            //输入点
            GetData theGD = new GetData();
            //加坐标
            //theGD.AddData();
            CycPint theCP = new CycPint(theGD .TheAL );
            System.Console .WriteLine ("圆心的横坐标:{0}",theCP.CycP.WData);
            System.Console.WriteLine("圆心的纵坐标:{0}", theCP.CycP.LenghtData);
            System.Console .WriteLine ("圆的半径:{0}",theCP.TheR);        }
    }

Answer 6

 #region 记录坐标
    /// <summary>
    /// 记录输入点坐标
    /// </summary>
    class GetData
    {
        private ArrayList _TheAL = new ArrayList();//记录各点
        //输入坐标
        public void AddData(double wdata, double lenghdata)
        {
            ModelForData theM = new ModelForData();
            theM.WData = wdata;
            theM.LenghtData = lenghdata;
            theAL.Add(theM);        }
        public ArrayList TheAL
        {
            get { return this._TheAL; }
            set { this._TheAL = value; }
        }
    }
    #endregion

Answer 7

 #region 单点坐标模型
    /// <summary>
    /// 单点坐标模型
    /// </summary>
    class ModelForData
    {
        private double mHeightData;
        private double mWData;
        public double LenghtData
        {
            get { return mLenghtData; }
            set { mLenghtData = value; }
        }
        public double WData
        {
            get { return mWData; }
            set { mWData = value; }
        }
    }
    #endregion    #region 距离，与对应的两点模型
    /// <summary>
    /// 距离，与对应的两点模型
    /// </summary>
    class ModelFroDataRecord
    {
        private ModelForData mOneModelForData=new ModelForData ();
        private ModelForData mTwoModelForData=new ModelForData ();
        private double mOneTwoLong;
        public ModelForData OneModelForData
        {
            get { return mOneModelForData; }
            set { this.mTwoModelForData = value; }
        }
        public ModelForData TwoModelForData
        {
            get { return mTwoModelForData; }
            set { this.mTwoModelForData = value; }
        }
        public double OneTwoLong
        {
            get { return mOneTwoLong; }
            set { this.mOneTwoLong = value; }
        }
    }
    #endregion    #region 余弦值与第三点坐标的模型
    class ModelForCosValueRecord
    {
        private double _CosValue;
        private ModelForData _thePostData=new ModelForData ();
        public double CosValue
        {
            get { return _CosValue; }
            set { _CosValue = value; }
        }
        public ModelForData thePostData
        {
            get { return _thePostData; }
            set { _thePostData = value; }
        }
    }    #endregion

Answer 8

 #region 得到距离最大的两点的坐标
    class GetMaxP1P2
    {
        #region 属性
        private ModelForData _ThePost1;
        private ModelForData _ThePost2;
        private ArrayList _InputPList;
        private ArrayList _P1P2Lenth;        private ModelFroDataRecord _MaxLongRecord;
        #endregion
        #region 构造方法
        public GetMaxP1P2(ArrayList inputPList)
        {
            _InputPList = inputPList;
            //将所有的　两点的距离　放入集合_P1P2Lenth中
            this.OutAL();
            //获得最大记录　赋给属性
            _MaxLongRecord = this.MaxRecord();
        }
        #endregion
        #region 获得最大记录
        /// <summary>
        /// 获得最大记录
        /// </summary>
        /// <returns></returns>
        private  ModelFroDataRecord MaxRecord()
        {
            ModelFroDataRecord returnMFDR=new ModelFroDataRecord ();
            foreach (ModelFroDataRecord theR in _P1P2Lenth)
            {
                double MaxLong=this.AllThePost ();
                if (theR.OneTwoLong== MaxLong)
                {
                    returnMFDR = theR;
                }
            }
            return returnMFDR;
        }
        #endregion
        #region 任意一点到其他点的距离----只针对该算法
        /// <summary>
        /// 任意一点到其他点的距离----只针对该算法
        /// </summary>
        /// <param name="i"></param>
        /// <returns></returns>
        private void Lenth(int i)
        {
            for (int j = i; j < _InputPList.Count; j++)
            {
                try
                {
                    ModelForData theMI = new ModelForData();
                    theMI = (ModelForData)_InputPList[i];
                    ModelForData theMID = new ModelForData();
                    theMID = (ModelForData)_InputPList[j];                    ModelFroDataRecord theMFDR = new ModelFroDataRecord();
                    double jl1 = System.Math.Sqrt(System.Math.Pow(theMI.WData - theMID.WData, 2) + System.Math.Pow(theMI.mHeightData - theMID.mHeightData, 2));
                    theMFDR.OneModelForData = theMI;
                    theMFDR.TwoModelForData = theMID;
                    theMFDR.OneTwoLong = jl1;
                    _P1P2Lenth.Add(theMFDR);
                }
                catch { }
            }
        }
        #endregion
        #region 记录各点的距离
        /// <summary>
        /// 记录各点的距离
        /// </summary>
        private void OutAL()
        {
            int i=0;
            foreach (ModelForData tempM in theAL)
            {
                this.Lenth(i);  
                i++;
            }
        }
        #endregion
        #region 取得两点距离最大的记录
        /// <summary>
        /// 遍历输入点，得到所有距离列表和对应的点的距离。
        /// </summary>
        private double AllThePost()
        {
            double MaxLeng = 0;
            foreach (ModelFroDataRecord maxM in _P1P2Lenth)
            {
                if (MaxLeng < maxM.OneTwoLong)
                {
                    MaxLeng = maxM.OneTwoLong;
                }
            }            return MaxLeng;
        }
        #endregion
        #region 对外报露最大长度记录
        /// <summary>
        /// 对外报露最大长度记录
        /// </summary>
        public ModelFroDataRecord MaxLongRecord
        {
            get { return _MaxLongRecord; }
        }
        #endregion    }
    #endregion

Answer 9

  #region 已知两点，以第三点为顶点的 的余弦值和其对应的坐标　列表
    class CosValueList
    {
        double _x1;
        double _y1;
        double _x2;
        double _y2;
        double _x3;
        double _y3;
        ArrayList _PostList = new ArrayList();
        ArrayList _CosList = new ArrayList();
        public CosValueList(ArrayList PostList)
        {
            GetMaxP1P2 getMaxP1P2 = new GetMaxP1P2(PostList);
            ModelFroDataRecord theMFDR=getMaxP1P2.MaxLongRecord ;
            _x1 = theMFDR.OneModelForData.WData;
            _y1 = theMFDR.OneModelForData.LenghtData;
            _x2 = theMFDR.TwoModelForData.WData;
            _y2 = theMFDR.TwoModelForData.LenghtData;
            _PostList = PostList;
        }
        private void GetTheList()
        {
            foreach (ModelForData theMFD in _PostList)
            {
                _x3 = theMFD.WData;
                _y3 = theMFD.LenghtData;
                double a = System.Math.Sqrt(System.Math.Pow(_x1-_x3, 2) + System.Math.Pow(_y1 -_y3, 2));
                double b = System.Math.Sqrt(System.Math.Pow(_x2 - _x3, 2) + System.Math.Pow(_y2 - _y3, 2));
                double c = System.Math.Sqrt(System.Math.Pow(_x2 - _x1, 2) + System.Math.Pow(_y2 - _y1, 2));
                double theCosValue = (System.Math.Pow(_x1 - _x3, 2) + System.Math.Pow(_y1 - _y3, 2) + System.Math.Pow(_x2 - _x3, 2) + System.Math.Pow(_y2 - _y3, 2) - System.Math.Pow(_x2 - _x1, 2) + System.Math.Pow(_y2 - _y1, 2)) /( a * b * 2);
                ModelForCosValueRecord theModel = new ModelForCosValueRecord();
                theModel.CosValue = theCosValue;
                theModel.thePostData.WData = _x3;
                theModel.thePostData.LenghtData = _y3;
                _CosList.Add(theModel);
            }
        }
        public ArrayList CosList
        {
            get { return _CosList; }
        }    }
    #endregion

Answer 10

 #region 取得最小的余弦值的坐标记录
    class MinCosValue
    {
        private double _MinCosValue = 0;
        private ArrayList _CosValueList;
        private ModelForData _P3;
        public MinCosValue(ArrayList theCosValueList)
        {
            _CosValueList = theCosValueList;
            this.MinValue();
            this.MinValueRecord();
        }
        private void MinValue()
        {
            foreach (ModelForCosValueRecord theMFCVR in _CosValueList)
            {
                if (_MinCosValue - theMFCVR.CosValue > 0.001)
                {
                    _MinCosValue = theMFCVR.CosValue;
                }
            }
        }
        private void MinValueRecord()
        {
            ModelForData _theP;
            foreach (ModelForCosValueRecord theMFCVR in _CosValueList)
            {
                if (_MinCosValue - theMFCVR.CosValue > 0.001)
                {
                    _theP = theMFCVR.thePostData;
                }
            }
        }
        public ModelForData P3
        {
            get { return _P3; }
        }
    }
    #endregion

Answer 11

#region 取得　圆心和半径
    /// <summary>
    /// 取得　圆心和半径
    /// </summary>
    class CycPint
    {
        double _x1;
        double _x2;
        double _x3;
        double _y1;
        double _y2;
        double _y3;
        ModelForData _MidPointForP1=new ModelForData ();
        ModelForData _MidPointForP2 = new ModelForData();
        double _K1;
        double _K2;
        ModelForData _CycP=new ModelForData ();
        double _LongP1P2P3;
        public CycPint(ArrayList InputPointList)
        {
            GetMaxP1P2 theP1P2 = new GetMaxP1P2(InputPointList);
            ModelFroDataRecord theRecord = theP1P2.MaxLongRecord;
            _x1 = theRecord.OneModelForData.WData;
            _y1 = theRecord.OneModelForData.LenghtData;
            _x2 = theRecord.TwoModelForData.WData;
            _y2 = theRecord.TwoModelForData.LenghtData;
            CosValueList theCVL = new CosValueList(InputPointList);
            MinCosValue theMin = new MinCosValue(theCVL.CosList);
            _x3 = theMin.P3.WData;
            _y3 = theMin.P3.LenghtData;
            _K1 = (_y1 - _y3) / (_x1 - _x3);
            _K2 = (_y1 - _y2) / (_x1 - _x2);
            _MidPointForP1.WData = _x1 - _x3;
            _MidPointForP1.LenghtData = _y1 - _y3;
            _MidPointForP2.WData = _x1 - _x2;
            _MidPointForP2.LenghtData = _y1 - _y3;
            _CycP.WData = (_MidPointForP2.LenghtData - _MidPointForP1.LenghtData) / ((_MidPointForP1.WData - _MidPointForP1.WData) * (_K1 - _K2));
            _CycP.LenghtData = (_K2 * _MidPointForP1.LenghtData - _K1 * _MidPointForP2.LenghtData) / (_K2 - _K1);
            _LongP1P2P3 = System.Math.Sqrt(System.Math.Pow((_CycP.WData - _x1), 2) + System.Math.Pow((_CycP.LenghtData - _y1), 2));
 
        }
        public ModelForData CycP
        {
            get{return _MidPoint;}
        }
        public double TheR
        {
            get { return _LongP1P2P3; }
        }
    }
    #endregion

Answer 12

上面已经完整。
当需要用GUI绘图的时候 注意我上面说的 那个点的大小就好了  嘿嘿