■ 포인트 리스트를 둘러싸는 외곽선(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

    }

}

 

 

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

    }

}

 

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

Posted by 사용자 icodebroker
TAG