■ 포인트 리스트를 둘러싸는 외곽선(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 } }
|
------------------------------------------------------------------------------------------------------------------------
'C# > Common' 카테고리의 다른 글
| [C#/COMMON] 경로 결합하기 (0) | 2018.12.05 |
|---|---|
| [C#/COMMON] 최대공약수(GCD)/최소공배수(LCM) 구하기 (0) | 2018.12.05 |
| [C#/COMMON] 조합(Combination) 구하기 (0) | 2018.12.05 |
| [C#/COMMON] 순열(Permutation) 구하기 (0) | 2018.12.04 |
| [C#/COMMON] WMI를 사용해 운영 체제 정보 구하기 (0) | 2018.12.03 |
| [C#/COMMON] 포인트 리스트를 둘러싸는 외곽선(Convex Hull) 구하기 (0) | 2018.12.02 |
| [C#/COMMON] WMI를 이용해 프린터 정보 구하기 (0) | 2018.12.02 |
| [C#/COMMON] 수식 평가하기 (0) | 2018.12.02 |
| [C#/COMMON] DriveInfo 클래스 : GetDrives 정적 메소드를 사용해 논리적 드라이브 정보 구하기 (0) | 2018.12.01 |
| [C#/COMMON] FileSystemWatcher 클래스 : 이벤트 중복 방지하기 (0) | 2018.11.23 |
| [C#/COMMON] FileSystemWatcher 클래스 사용하기 (0) | 2018.11.23 |
