GrahamScan Algorithm

Convex Hull문제를 해결하는 방법 중에 GrahamScan이 있다.

참고 : https://en.wikipedia.org/wiki/Graham_scan

예전에 문제에서 알게되고 관심있게 보았던 알고리즘.

간단히하면 주어진 Point에서 외각의 점들을 선택하는 알고리즘이다.

이것으로 최외각 다각형을 구할 수 있으며, 응용할 여지가 많다.

Wiki의 코드를 사용해 구현했다.

환경은 c#에 Graphics를 사용했다.

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

namespace GrahamScanTest
{
    public partial class Form1 : Form
    {
        private List al = new List();
        public Form1()
        {
            InitializeComponent();
        }
        void Form1_Load(object sender, EventArgs e)
        {

        }
        void Form1_Paint(object sender, PaintEventArgs e)
        {
            Graphics gr = e.Graphics;
            Pen myPen = new Pen(Color.Black);
            foreach (Point p in al)
                gr.DrawRectangle(myPen, p.X, 262 - p.Y, 1, 1);

            if (al.Count > 2){
                int i = 0, length = GrahamScanTest();
                for (; i < length; i++)
                    gr.DrawLine(myPen, cp(al[i]), cp(al[i+1]));
                gr.DrawLine(myPen, cp(al[i]), cp(al[0]));
            }
        }
        void Form1_MouseDown(object sender, MouseEventArgs e)
        {
            al.Add(new Point(e.X, 262 - e.Y));
            Invalidate();
        }
        private Point cp(Point p)
        {
            return new Point(p.X, 262 - p.Y);
        }
        private float Angle(Point m){
            return Math.Abs((float)(Math.Atan2(m.Y - al[0].Y, m.X - al[0].X)*180d/Math.PI));
        }
        private int ccw(Point p1, Point p2, Point p3){
            return (p2.X - p1.X) * (p3.Y - p1.Y) - (p2.Y - p1.Y) * (p3.X - p1.X);
        }
        private int GrahamScanTest()
        {
            int N = al.Count;
            for (int i = 1, lowestY = 0; i < N; i++)
                if (al[i].Y < al[lowestY].Y)
                    swap(i, lowestY);

            al.Sort((a, b) =>
            {
                return Angle(a).CompareTo(Angle(b));
            });

            int M = 1;
            for (int i = 2; i < N; i++){
                while (ccw(al[M - 1], al[M], al[i]) <= 0)
                {
                    if (M > 1)
                        --M;
                    else if (i == N)
                        break;
                    else
                        ++i;
                }
                ++M;
                swap(M, i);
            }

            return M;
        }
        private void swap(int src, int des) {
            Point temp = al[src];
            al[src] = al[des];
            al[des] = temp;
        }
    }
}