[C#/WINFORM] 포인트 리스트를 둘러싸는 외곽선(Convex Hull) 구하기

TestProject.zip

다운로드

▶ ConvexHullHepler.cs

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

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

        #region Field

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

        #endregion

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

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

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

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

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

        #endregion
        #region 컬렁 사각형 - CullingRectangle

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

        #endregion

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

        #region 생성자 - GeometryHepler()

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

        #endregion

        //////////////////////////////////////////////////////////////////////////////////////////////////// Method
        ////////////////////////////////////////////////////////////////////////////////////////// Public

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

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

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

            Point currentPoint = nolCulledPointList[0];

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

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

            convexHullPointList.Add(currentPoint);

            nolCulledPointList.Remove(currentPoint);

            float sweepAngle = 0;

            for(;;)
            {
                int x = convexHullPointList[convexHullPointList.Count - 1].X;
                int y = convexHullPointList[convexHullPointList.Count - 1].Y;

                currentPoint = nolCulledPointList[0];

                float currentAngle = 3600;

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

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

                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;

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

            return convexHullPointList;
        }

        #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<Point> sourcePointList, ref Point leftTop, ref Point rightTop, ref Point leftBottom, ref Point rightBottom)
        {
            leftTop     = sourcePointList[0];
            rightTop    = leftTop;
            leftBottom  = leftTop;
            rightBottom = leftTop;

            foreach(Point 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 Point[] { leftTop, rightTop, rightBottom, leftBottom };
        }

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

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

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

            int xMinimum;
            int xMaximum;
            int yMinimum;
            int 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;
            }

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

            CullingRectangle = rectangle;

            return rectangle;
        }

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

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

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

            foreach(Point 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 Point[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(int x1, int y1, int x2, int 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
    }
}

 

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 GeometryHepler helper = new GeometryHepler();

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

        #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

        #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));

            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;

            #region 마우스로 클릭한 포인트를 채워서 그린다.

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

            #endregion

            List<Point> convexHullPointList = null;

            if(this.pointList.Count >= 3)
            {
                convexHullPointList = this.helper.GetConvexHullPointList(this.pointList);

                #region 컬링 사각형에 포함되지 않는 포인트를 그린다.

                foreach(Point point in this.helper.NonCulledPointArray)
                {
                    e.Graphics.FillEllipse(Brushes.White, point.X - 3, point.Y - 3, 7, 7);
                }

                #endregion
            }

            #region 마우스로 클릭한 포인트 외곽선을 그린다.

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

            #endregion

            if(this.pointList.Count >= 3)
            {
                #region 최소/최대 포인트를 잇는 선을 그린다.

                e.Graphics.DrawPolygon(Pens.Red, this.helper.MinimumMaximumCornerPointArray);

                #endregion
                #region 컬링 사각형을 그린다.

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

                #endregion
                #region 외곽선을 그린다.

                Point[] convexHullPointArray = new Point[convexHullPointList.Count];

                convexHullPointList.CopyTo(convexHullPointArray);

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

                #endregion
            }
        }

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

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

            Invalidate();
        }

        #endregion
    }
}