첨부 실행 코드는 나눔고딕코딩 폰트를 사용합니다.
유용한 소스 코드가 있으면 icodebroker@naver.com으로 보내주시면 감사합니다.
블로그 자료는 자유롭게 사용하세요.

■ 포인트 리스트를 둘러싸는 원 구하기

------------------------------------------------------------------------------------------------------------------------


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

    }

}

 

 

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

    }

}

 

------------------------------------------------------------------------------------------------------------------------

Posted by 사용자 icodebroker

댓글을 달아 주세요