[C#/WINFORM] 포인트 리스트를 둘러싸는 원 구하기

TestProject.zip

다운로드

▶ GeometryHelper.cs

using System;
using System.Collections.Generic;
using System.Drawing;

namespace TestProject
{
    /// <summary>
    /// 기하학 헬퍼
    /// </summary>
    public class GeometryHelper
    {
        //////////////////////////////////////////////////////////////////////////////////////////////////// Field
        ////////////////////////////////////////////////////////////////////////////////////////// Private

        #region Field

        /// <summary>
        /// 소스 포인트 리스트
        /// </summary>
        private List<PointF> sourcePointList = null;

        #endregion

        //////////////////////////////////////////////////////////////////////////////////////////////////// Property
        ////////////////////////////////////////////////////////////////////////////////////////// Public

        #region 컬링 사각형에 포함되지 않는 포인트 배열 - NonCulledPointArray

        /// <summary>
        /// 컬링 사각형에 포함되지 않는 포인트 배열
        /// </summary>
        public PointF[] NonCulledPointArray { get; set; }

        #endregion
        #region 최소/최대 코너 포인트 배열 - MinimumMaximumCornerPointArray

        /// <summary>
        /// 최소/최대 코너 포인트 배열
        /// </summary>
        public PointF[] MinimumMaximumCornerPointArray { get; set; }

        #endregion
        #region 컬렁 사각형 - CullingRectangle

        /// <summary>
        /// 컬렁 사각형
        /// </summary>
        public RectangleF CullingRectangle { get; set; }

        #endregion

        //////////////////////////////////////////////////////////////////////////////////////////////////// Constructor
        ////////////////////////////////////////////////////////////////////////////////////////// Public

        #region 생성자 - GeometryHelper()

        /// <summary>
        /// 생성자
        /// </summary>
        public GeometryHelper()
        {
        }

        #endregion

        //////////////////////////////////////////////////////////////////////////////////////////////////// Method
        ////////////////////////////////////////////////////////////////////////////////////////// Static
        //////////////////////////////////////////////////////////////////////////////// Public

        #region 외곽선(Convex Hull) 포인트 리스트 구하기 - GetConvexHullPointList(sourcePointList)

        /// <summary>
        /// 외곽선(Convex Hull) 포인트 리스트 구하기
        /// </summary>
        /// <param name="sourcePointList">소스 포인트 리스트</param>
        /// <returns>외곽선 포인트 리스트</returns>
        public List<PointF> GetConvexHullPointList(List<PointF> sourcePointList)
        {
            this.sourcePointList = sourcePointList;

            List<PointF> nolCulledPointList = GetNonCulledPointList(this.sourcePointList);

            PointF currentPoint = nolCulledPointList[0];

            foreach(PointF nonCulledPoint in nolCulledPointList)
            {
                if((nonCulledPoint.Y < currentPoint.Y) || ((nonCulledPoint.Y == currentPoint.Y) && (nonCulledPoint.X < currentPoint.X)))
                {
                    currentPoint = nonCulledPoint;
                }
            }

            List<PointF> convexHullPointList = new List<PointF>();

            convexHullPointList.Add(currentPoint);

            nolCulledPointList.Remove(currentPoint);

            float sweepAngle = 0;

            for(;;)
            {
                if(nolCulledPointList.Count == 0)
                {
                    break;
                }

                float x = convexHullPointList[convexHullPointList.Count - 1].X;
                float y = convexHullPointList[convexHullPointList.Count - 1].Y;

                currentPoint = nolCulledPointList[0];

                float currentAngle = 3600;

                foreach(PointF nolCulledPoint in nolCulledPointList)
                {
                    float testAngle = GetAngleValue(x, y, nolCulledPoint.X, nolCulledPoint.Y);

                    if((testAngle >= sweepAngle) && (currentAngle > testAngle))
                    {
                        currentAngle = testAngle;
                        currentPoint = nolCulledPoint;
                    }
                }

                float firstAngle = GetAngleValue(x, y, convexHullPointList[0].X, convexHullPointList[0].Y);

                if((firstAngle >= sweepAngle) && (currentAngle >= firstAngle))
                {
                    break;
                }

                convexHullPointList.Add(currentPoint);

                nolCulledPointList.Remove(currentPoint);

                sweepAngle = currentAngle;
            }

            return convexHullPointList;
        }

        #endregion
        #region 최소 테두리 원 찾기 - FindMinimalBoundingCircle(sourcePointList, centerPoint, radius)

        /// <summary>
        /// 최소 테두리 원 찾기
        /// </summary>
        /// <param name="sourcePointList">소스 포인트 리스트</param>
        /// <param name="centerPoint">중심점</param>
        /// <param name="radius">반경</param>
        public void FindMinimalBoundingCircle(List<PointF> sourcePointList, out PointF centerPoint, out float radius)
        {
            List<PointF> convexHullPointList = GetConvexHullPointList(sourcePointList);

            PointF currentCenterPoint   = sourcePointList[0];
            float  currentRadiusSquared = float.MaxValue;

            for(int i = 0; i < convexHullPointList.Count - 1; i++)
            {
                for(int j = i + 1; j < convexHullPointList.Count; j++)
                {
                    PointF testCenterPoint = new PointF
                    (
                        (convexHullPointList[i].X + convexHullPointList[j].X) / 2f,
                        (convexHullPointList[i].Y + convexHullPointList[j].Y) / 2f
                    );

                    float deltaX            = testCenterPoint.X - convexHullPointList[i].X;
                    float deltaY            = testCenterPoint.Y - convexHullPointList[i].Y;
                    float testRadiusSquared = deltaX * deltaX + deltaY * deltaY;

                    if(testRadiusSquared < currentRadiusSquared)
                    {
                        if(IsCircleEnclosePointList(testCenterPoint, testRadiusSquared, convexHullPointList, i, j, -1))
                        {
                            currentCenterPoint   = testCenterPoint;
                            currentRadiusSquared = testRadiusSquared;
                        }
                    }
                }
            }

            for(int i = 0; i < convexHullPointList.Count - 2; i++)
            {
                for(int j = i + 1; j < convexHullPointList.Count - 1; j++)
                {
                    for(int k = j + 1; k < convexHullPointList.Count; k++)
                    {
                        PointF testCenterPoint;
                        float  testRadiusSquared;

                        FindCircle
                        (
                            convexHullPointList[i],
                            convexHullPointList[j],
                            convexHullPointList[k],
                            out testCenterPoint,
                            out testRadiusSquared
                        );

                        if(testRadiusSquared < currentRadiusSquared)
                        {
                            if(IsCircleEnclosePointList(testCenterPoint, testRadiusSquared, convexHullPointList, i, j, k))
                            {
                                currentCenterPoint   = testCenterPoint;
                                currentRadiusSquared = testRadiusSquared;
                            }
                        }
                    }
                }
            }

            centerPoint = currentCenterPoint;

            if(currentRadiusSquared == float.MaxValue)
            {
                radius = 0;
            }
            else
            {
                radius = (float)Math.Sqrt(currentRadiusSquared);
            }
        }

        #endregion

        #region 사각형 그리기 - DrawRectangle(graphics, pen, rectangle)

        /// <summary>
        /// 사각형 그리기
        /// </summary>
        /// <param name="graphics">그래픽스</param>
        /// <param name="pen">펜</param>
        /// <param name="rectangle">사각형</param>
        public void DrawRectangle(Graphics graphics, Pen pen, RectangleF rectangle)
        {
            graphics.DrawRectangle(pen, Rectangle.Round(rectangle));
        }

        #endregion

        //////////////////////////////////////////////////////////////////////////////// Private

        #region 최소/최대 코너 포인트 설정하기 - SetMinimumMaximumCornerPoint(sourcePointList, leftTop, rightTop, leftBottom, rightBottom)

        /// <summary>
        /// 최소/최대 코너 포인트 설정하기
        /// </summary>
        /// <param name="sourcePointList">소스 포인트 리스트</param>
        /// <param name="leftTop">좌상단 포인트</param>
        /// <param name="rightTop">우상단 포인트</param>
        /// <param name="leftBottom">좌하단 포인트</param>
        /// <param name="rightBottom">우하단 포인트</param>
        private void SetMinimumMaximumCornerPoint(List<PointF> sourcePointList, ref PointF leftTop, ref PointF rightTop, ref PointF leftBottom, ref PointF rightBottom)
        {
            leftTop     = sourcePointList[0];
            rightTop    = leftTop;
            leftBottom  = leftTop;
            rightBottom = leftTop;

            foreach(PointF sourcePoint in sourcePointList)
            {
                if(-sourcePoint.X - sourcePoint.Y > -leftTop.X - leftTop.Y)
                {
                    leftTop = sourcePoint;
                }

                if(sourcePoint.X - sourcePoint.Y > rightTop.X - rightTop.Y)
                {
                    rightTop = sourcePoint;
                }

                if(-sourcePoint.X + sourcePoint.Y > -leftBottom.X + leftBottom.Y)
                {
                    leftBottom = sourcePoint;
                }

                if(sourcePoint.X + sourcePoint.Y > rightBottom.X + rightBottom.Y)
                {
                    rightBottom = sourcePoint;
                }
            }

            MinimumMaximumCornerPointArray = new PointF[] { leftTop, rightTop, rightBottom, leftBottom };
        }

        #endregion
        #region 컬링 사각형 구하기 - GetCullingRectangle(sourcePointList)

        /// <summary>
        /// 컬링 사각형 구하기
        /// </summary>
        /// <param name="sourcePointList">소스 포인트 리스트</param>
        /// <returns>컬링 사각형</returns>
        private RectangleF GetCullingRectangle(List<PointF> sourcePointList)
        {
            PointF leftTop     = new Point(0, 0);
            PointF rightTop    = leftTop;
            PointF leftBottom  = leftTop;
            PointF rightBottom = leftTop;

            SetMinimumMaximumCornerPoint(sourcePointList, ref leftTop, ref rightTop, ref leftBottom, ref rightBottom);

            float xMinimum;
            float xMaximum;
            float yMinimum;
            float yMaximum;

            xMinimum = leftTop.X;
            yMinimum = leftTop.Y;

            xMaximum = rightTop.X;

            if(yMinimum < rightTop.Y)
            {
                yMinimum = rightTop.Y;
            }

            if(xMaximum > rightBottom.X)
            {
                xMaximum = rightBottom.X;
            }

            yMaximum = rightBottom.Y;

            if(xMinimum < leftBottom.X)
            {
                xMinimum = leftBottom.X;
            }

            if(yMaximum > leftBottom.Y)
            {
                yMaximum = leftBottom.Y;
            }

            RectangleF rectangle = new RectangleF(xMinimum, yMinimum, xMaximum - xMinimum, yMaximum - yMinimum);

            CullingRectangle = rectangle;

            return rectangle;
        }

        #endregion
        #region 컬링 사각형에 포함되지 않는 포인트 리스트 구하기 - GetNonCulledPointList(sourcePointList)

        /// <summary>
        /// 컬링 사각형에 포함되지 않는 포인트 리스트 구하기
        /// </summary>
        /// <param name="sourcePointList">소스 포인트 리스트</param>
        /// <returns>컬링 사각형에 포함되지 않는 포인트 리스트</returns>
        private List<PointF> GetNonCulledPointList(List<PointF> sourcePointList)
        {
            RectangleF cullingRectangle = GetCullingRectangle(sourcePointList);

            List<PointF> nonCulledPointList = new List<PointF>();

            foreach(PointF sourcePoint in sourcePointList)
            {
                if
                (
                    sourcePoint.X <= cullingRectangle.Left  ||
                    sourcePoint.X >= cullingRectangle.Right ||
                    sourcePoint.Y <= cullingRectangle.Top   ||
                    sourcePoint.Y >= cullingRectangle.Bottom
                )
                {
                    nonCulledPointList.Add(sourcePoint);
                }
            }
            
            NonCulledPointArray = new PointF[nonCulledPointList.Count];

            nonCulledPointList.CopyTo(NonCulledPointArray);

            return nonCulledPointList;
        }

        #endregion
        #region 각도 값 구하기 - GetAngleValue(x1, y1, x2, y2)

        /// <summary>
        /// 각도 값 구하기
        /// </summary>
        /// <param name="x1">X1</param>
        /// <param name="y1">Y1</param>
        /// <param name="x2">X2</param>
        /// <param name="y2">Y2</param>
        /// <returns>각도 값</returns>
        private float GetAngleValue(float x1, float y1, float x2, float y2)
        {
            float deltaX;
            float deltaY;
            float absoluteX;
            float absoluteY;
            float temporaryValue;

            deltaX    = x2 - x1;
            absoluteX = Math.Abs(deltaX);
            deltaY    = y2 - y1;
            absoluteY = Math.Abs(deltaY);

            if(absoluteX + absoluteY == 0)
            {
                temporaryValue = 360f / 9f;
            }
            else
            {
                temporaryValue = deltaY / (absoluteX + absoluteY);
            }

            if(deltaX < 0)
            {
                temporaryValue = 2 - temporaryValue;
            }
            else if(deltaY < 0)
            {
                temporaryValue = 4 + temporaryValue;
            }

            return temporaryValue * 90;
        }

        #endregion

        #region 원의 포인트 리스트 포함 여부 구하기 - IsCircleEnclosePointList(centerPoint, radiusSquared, sourcePointList, skip1, skip2, skip3)

        /// <summary>
        /// 원의 포인트 리스트 포함 여부 구하기
        /// </summary>
        /// <param name="centerPoint">중심점</param>
        /// <param name="radiusSquared">반경 제곱</param>
        /// <param name="sourcePointList">소스 포인트 리스트</param>
        /// <param name="skip1">건너뛰기 1</param>
        /// <param name="skip2">건너뛰기 2</param>
        /// <param name="skip3">건너뛰기 3</param>
        /// <returns>원의 포인트 리스트 포함 여부</returns>
        private bool IsCircleEnclosePointList(PointF centerPoint, float radiusSquared, List<PointF> sourcePointList, int skip1, int skip2, int skip3)
        {
            for(int i = 0; i < sourcePointList.Count; i++)
            {
                if((i != skip1) && (i != skip2) && (i != skip3))
                {
                    PointF point = sourcePointList[i];

                    float deltaX            = centerPoint.X - point.X;
                    float deltaY            = centerPoint.Y - point.Y;
                    float testRadiusSquared = deltaX * deltaX + deltaY * deltaY;

                    if(testRadiusSquared > radiusSquared)
                    {
                        return false;
                    }
                }
            }

            return true;
        }

        #endregion
        #region 교차점 찾기 - FindIntersection(p1, p2, p3, p4, lineIntersect, segmentIntersect, intersectPoint, closePoint1, closePoint2)

        /// <summary>
        /// 교차점 찾기
        /// </summary>
        /// <param name="p1">직선 1 포인트 1</param>
        /// <param name="p2">직선 1 포인트 2</param>
        /// <param name="p3">직선 2 포인트 1</param>
        /// <param name="p4">직선 2 포인트 2</param>
        /// <param name="lineIntersect">직선 교차 여부</param>
        /// <param name="segmentIntersect">세그먼트 교차 여부</param>
        /// <param name="intersectPoint">교차점</param>
        /// <param name="closePoint1">근접점 1</param>
        /// <param name="closePoint2">근접점 2</param>
        private void FindIntersection(PointF p1, PointF p2, PointF p3, PointF p4, out bool lineIntersect, out bool segmentIntersect,
            out PointF intersectPoint, out PointF closePoint1, out PointF closePoint2)
        {
            float deltaX21 = p2.X - p1.X;
            float deltaY21 = p2.Y - p1.Y;
            float deltaX43 = p4.X - p3.X;
            float deltaY43 = p4.Y - p3.Y;

            float denominator = (deltaY21 * deltaX43 - deltaX21 * deltaY43);

            float t1;

            try
            {
                t1 = ((p1.X - p3.X) * deltaY43 + (p3.Y - p1.Y) * deltaX43) / denominator;
            }
            catch
            {
                lineIntersect    = false;
                segmentIntersect = false;

                intersectPoint = new PointF(float.NaN, float.NaN);
                closePoint1    = new PointF(float.NaN, float.NaN);
                closePoint2    = new PointF(float.NaN, float.NaN);

                return;
            }

            lineIntersect = true;

            float t2 = ((p3.X - p1.X) * deltaY21 + (p1.Y - p3.Y) * deltaX21) / -denominator;

            intersectPoint = new PointF(p1.X + deltaX21 * t1, p1.Y + deltaY21 * t1);

            segmentIntersect = ((t1 >= 0) && (t1 <= 1) && (t2 >= 0) && (t2 <= 1));

            if(t1 < 0)
            {
                t1 = 0;
            }
            else if(t1 > 1)
            {
                t1 = 1;
            }

            if(t2 < 0)
            {
                t2 = 0;
            }
            else if(t2 > 1)
            {
                t2 = 1;
            }

            closePoint1 = new PointF(p1.X + deltaX21 * t1, p1.Y + deltaY21 * t1);
            closePoint2 = new PointF(p3.X + deltaX43 * t2, p3.Y + deltaY43 * t2);
        }

        #endregion
        #region 원 찾기 - FindCircle(a, b, c, centerPoint, radiusSquared)

        /// <summary>
        /// 원 찾기
        /// </summary>
        /// <param name="a">A 포인트</param>
        /// <param name="b">B 포인트</param>
        /// <param name="c">C 포인트</param>
        /// <param name="centerPoint">중심점</param>
        /// <param name="radiusSquared">반경 제곱</param>
        private void FindCircle(PointF a, PointF b, PointF c, out PointF centerPoint, out float radiusSquared)
        {
            float centerXba = (b.X + a.X) / 2;
            float centerYba = (b.Y + a.Y) / 2;
            float deltaYba  = b.X - a.X;
            float deltaXba  = -(b.Y - a.Y);

            float centerXcb = (c.X + b.X) / 2;
            float centerYcb = (c.Y + b.Y) / 2;
            float deltaYcb  = c.X - b.X;
            float deltaXcb  = -(c.Y - b.Y);

            bool   lineIntersect;
            bool   segmentIntersect;
            PointF intersectPoint;
            PointF closePoint1;
            PointF closePoint2;

            FindIntersection
            (
                new PointF(centerXba, centerYba),
                new PointF(centerXba + deltaXba, centerYba + deltaYba),
                new PointF(centerXcb, centerYcb),
                new PointF(centerXcb + deltaXcb, centerYcb + deltaYcb),
                out lineIntersect,
                out segmentIntersect,
                out intersectPoint,
                out closePoint1,
                out closePoint2
            );

            centerPoint = intersectPoint;

            float deltaX = centerPoint.X - a.X;
            float deltaY = centerPoint.Y - a.Y;

            radiusSquared = deltaX * deltaX + deltaY * deltaY;
        }

        #endregion
    }
}

 

728x90

 

▶ MainForm.cs

using System;
using System.Collections.Generic;
using System.Drawing;
using System.Drawing.Drawing2D;
using System.Windows.Forms;

namespace TestProject
{
    /// <summary>
    /// 메인 폼
    /// </summary>
    public partial class MainForm : Form
    {
        //////////////////////////////////////////////////////////////////////////////////////////////////// Field
        ////////////////////////////////////////////////////////////////////////////////////////// Private

        #region Field

        /// <summary>
        /// 헬퍼
        /// </summary>
        private GeometryHelper helper = new GeometryHelper();

        /// <summary>
        /// 포인트 리스트
        /// </summary>
        private List<PointF> pointList = new List<PointF>();

        /// <summary>
        /// 포인트 외곽선 포인트 리스트
        /// </summary>
        private List<PointF> convexHullPointList = null;

        /// <summary>
        /// 원 중심점
        /// </summary>
        private PointF circleCenterPoint;

        /// <summary>
        /// 원 반지름
        /// </summary>
        private float circleRadius = -1;

        #endregion

        //////////////////////////////////////////////////////////////////////////////////////////////////// Constructor
        ////////////////////////////////////////////////////////////////////////////////////////// Public

        #region 생성자 - MainForm()

        /// <summary>
        /// 생성자
        /// </summary>
        public MainForm()
        {
            InitializeComponent();

            #region 이벤트를 설정한다.

            MouseDown              += Form_MouseDown;
            Paint                  += Form_Paint;
            this.clearButton.Click += clearButton_Click;

            #endregion
        }

        #endregion

        //////////////////////////////////////////////////////////////////////////////////////////////////// Method
        ////////////////////////////////////////////////////////////////////////////////////////// Private
        //////////////////////////////////////////////////////////////////////////////// Event

        #region 폼 마우스 DOWN 처리하기 - Form_MouseDown(sender, e)

        /// <summary>
        /// 폼 마우스 DOWN 처리하기
        /// </summary>
        /// <param name="sender">이벤트 발생자</param>
        /// <param name="e">이벤트 인자</param>
        private void Form_MouseDown(object sender, MouseEventArgs e)
        {
            this.pointList.Add(new Point(e.X, e.Y));

            this.convexHullPointList = this.helper.GetConvexHullPointList(this.pointList);

            this.helper.FindMinimalBoundingCircle(this.convexHullPointList, out this.circleCenterPoint, out this.circleRadius);

            Invalidate();
        }

        #endregion
        #region 폼 페인트시 처리하기 - Form_Paint(sender, e)

        /// <summary>
        /// 폼 페인트시 처리하기
        /// </summary>
        /// <param name="sender">이벤트 발생자</param>
        /// <param name="e">이벤트 인자</param>
        private void Form_Paint(object sender, PaintEventArgs e)
        {
            e.Graphics.Clear(BackColor);

            e.Graphics.SmoothingMode = SmoothingMode.AntiAlias;

            foreach(PointF point in this.pointList)
            {
                e.Graphics.FillEllipse(Brushes.Cyan, point.X - 3, point.Y - 3, 7, 7);
            }

            if(this.helper.NonCulledPointArray != null)
            {
                foreach(PointF point in this.helper.NonCulledPointArray)
                {
                    e.Graphics.FillEllipse(Brushes.White, point.X - 3, point.Y - 3, 7, 7);
                }
            }

            foreach(PointF point in this.pointList)
            {
                e.Graphics.DrawEllipse(Pens.Black, point.X - 3, point.Y - 3, 7, 7);
            }

            if(this.pointList.Count >= 3)
            {
                e.Graphics.DrawPolygon(Pens.Red, this.helper.MinimumMaximumCornerPointArray);

                this.helper.DrawRectangle(e.Graphics, Pens.Orange, this.helper.CullingRectangle);

                PointF[] convexHullPointArray = new PointF[this.convexHullPointList.Count];

                this.convexHullPointList.CopyTo(convexHullPointArray);

                e.Graphics.DrawPolygon(Pens.Blue, convexHullPointArray);
            }

            if(this.circleRadius > 0)
            {
                RectangleF rectangle = new RectangleF
                (
                    this.circleCenterPoint.X - this.circleRadius,
                    this.circleCenterPoint.Y - this.circleRadius,
                    2 * this.circleRadius,
                    2 * this.circleRadius
                );

                e.Graphics.DrawEllipse(Pens.Green, rectangle);

                e.Graphics.FillEllipse
                (
                    Brushes.Green,
                    this.circleCenterPoint.X - 2,
                    this.circleCenterPoint.Y - 2,
                    5,
                    5
                );
            }
        }

        #endregion
        #region 지우기 버튼 클릭시 처리하기 - clearButton_Click(sender, e)

        /// <summary>
        /// 지우기 버튼 클릭시 처리하기
        /// </summary>
        /// <param name="sender">이벤트 발생자</param>
        /// <param name="e">이벤트 인자</param>
        private void clearButton_Click(object sender, EventArgs e)
        {
            this.pointList = new List<PointF>();

            this.circleRadius = -1;

            Invalidate();
        }

        #endregion
    }
}