//Andrzej Borucki
//www.algorytm.org
//Algorytm obcinania odcinkow

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;

namespace ClipLineWF
{
    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();
        }

        const int MinX = 0;
        const int MinY = 0;
        const int MaxX = 100;
        const int MaxY = 100;

        private void SwapPoints(ref int x0, ref int y0, ref int x1, ref int y1)
        {
            int tmpX, tmpY;
            tmpX = x0;
            tmpY = y0;
            x0 = x1;
            y0 = y1;
            x1 = tmpX;
            y1 = tmpY;
        }

        private void SwapCodes(ref int c1, ref int c2)
        {
            int tmp = c1;
            c1 = c2;
            c2 = tmp;
        }

        const int LEFT_EDGE = 1;
        const int RIGHT_EDGE = 2;
        const int BOTTOM_EDGE = 4;
        const int TOP_EDGE = 8;

        /* Algorytm obcinania odcinkow
         * return: 
         * 0 - inside; 1 - clip; 2 - outside
         */
        private int ClipLine1(ref int x0, ref int y0, ref int x1, ref int y1)
        {
            int code1, code2;
            bool clipped = false;
            double m;
            while (true)
            {
                code1 = 0;
                code2 = 0;
                if (x0 < MinX) code1 |= 1;
                if (x0 > MaxX) code1 |= 2;
                if (y0 < MinY) code1 |= 4;
                if (y0 > MaxY) code1 |= 8;
                if (x1 < MinX) code2 |= 1;
                if (x1 > MaxX) code2 |= 2;
                if (y1 < MinY) code2 |= 4;
                if (y1 > MaxY) code2 |= 8;

                if ((code1 | code2) == 0)
                {
                    if (clipped) return 1;
                    else return 0;
                }
                else if ((code1 & code2) != 0)
                {
                    return 2;
                }
                else
                {
                    clipped = true;
                    /*ensure that p1 is outside window*/
                    if (code1 == 0)
                    {
                        SwapPoints(ref x0, ref y0, ref x1, ref y1);
                        SwapCodes(ref code1, ref code2);
                    }
                    /* use slope (m) to find line_clip edge Intersection */
                    if (x1 != x0)
                        m = (double)(y1 - y0) / (x1 - x0);
                    else
                        m = Double.PositiveInfinity;

                    if ((code1 & TOP_EDGE) != 0)
                    {
                        if (x1 != x0)
                            x0 += (int)((MaxY - y0) / m);
                        y0 = MaxY;
                    }
                    else
                    if ((code1 & BOTTOM_EDGE) != 0)
                    {
                        if (x1 != x0)
                            x0 += (int)((MinY - y0) / m);
                        y0 = MinY;
                    }
                    else
                    if ((code1 & RIGHT_EDGE) != 0)
                    {
                        if (x1 != x0)
                        {
                            y0 += (int)((MaxX - x0) * m);
                            x0 = MaxX;
                        }
                    }
                    else
                    if ((code1 & LEFT_EDGE) != 0)
                    {
                        if (x1 != x0)
                        {
                            y0 += (int)((MinX - x0) * m);
                            x0 = MinX;
                        }
                    }                                                                             
                }
            }
        }

        /* Algorytm obcinania odcinkow
         * bardziej zwarta i szybsza implementacja algorytmu
         * return: 
         * 0 - inside; 1 - clip; 2 - outside
         */
        private int ClipLine2(ref int x0, ref int y0, ref int x1, ref int y1)
        {
            int V, C1, C2;
            C1 = 0;
            C2 = 0;

            if (x0 < MinX) C1 |= 1;
            if (x0 > MaxX) C1 |= 2;
            if (y0 < MinY) C1 |= 4;
            if (y0 > MaxY) C1 |= 8;
            if (x1 < MinX) C2 |= 1;
            if (x1 > MaxX) C2 |= 2;
            if (y1 < MinY) C2 |= 4;
            if (y1 > MaxY) C2 |= 8;

            if (((C1 & C2) == 0) && ((C1 | C2) != 0))
            {
                if ((C1 & 12) != 0)
                {
                    if (C1 < 8) V = MinY; else V = MaxY;
                    x0 += (int)((double)(V - y0) * (x1 - x0) / (y1 - y0));
                    y0 = V;
                    C1 = (x0 < MinX ? 1 : 0) + (x0 > MaxX ? 2 : 0);
                }

                if ((C2 & 12) != 0)
                {
                    if (C2 < 8) V = MinY; else V = MaxY;
                    x1 += (int)((double)(V - y1) * (x1 - x0) / (y1 - y0));
                    y1 = V;
                    C2 = (x1 < MinX ? 1 : 0) + (x1 > MaxX ? 2 : 0);
                }

                if (((C1 & C2) == 0) && ((C1 | C2) != 0))
                {
                    if (C1 != 0)
                    {
                        if (C1 == 1) V = MinX; else V = MaxX;
                        y0 += (int)((double)(V - x0) * (y1 - y0) / (x1 - x0));
                        x0 = V;
                        C1 = 0;
                    }

                    if (C2 != 0)
                    {
                        if (C2 == 1) V = MinX; else V = MaxX;
                        y1 += (int)((double)(V - x1) * (y1 - y0) / (x1 - x0));
                        x1 = V;
                        C2 = 0;
                    }
                }
                if ((C1 == 0) || (C2 == 0)) return 1; else return 2;
            }
            else
                if ((C1 | C2) == 0) return 0; else return 2;
        }

        private void Form1_Load(object sender, EventArgs e)
        {
            Bitmap bmp = new Bitmap(pictureBox1.Width, pictureBox1.Height);
            pictureBox1.Image = bmp;
            Graphics g = Graphics.FromImage(bmp);
            g.Clear(Color.White);
            Pen pen = new Pen(Brushes.Black);
            using(pen)
            {
                g.DrawRectangle(pen, new Rectangle(100, 100, 100, 100));
            }
            g.Dispose();
            pictureBox1.Invalidate();
        }

        private void button1_Click(object sender, EventArgs e)
        {
            Bitmap bmp = (Bitmap)pictureBox1.Image;
            Random rand = new Random();

            int x0 = rand.Next(200) - 100;
            int y0 = rand.Next(200) - 100;
            int x1 = rand.Next(200);
            int y1 = rand.Next(200);
            Graphics g = Graphics.FromImage(bmp);
            g.Clear(Color.White);
            Pen pen = new Pen(Brushes.Black);
            using (pen)
            {
                g.DrawRectangle(pen, new Rectangle(100, 100, 100, 100));
                g.DrawLine(pen, x0+100, y0+100, x1+100, y1+100);
            }            
            int res = ClipLine2(ref x0, ref y0, ref x1, ref y1);
            switch (res)
            {
                case 0: pen = new Pen(Brushes.Red, 2); break;
                case 1: pen = new Pen(Brushes.Lime, 2); break;
                default: pen = new Pen(Brushes.Magenta, 2); break;
            }            
            using (pen)
            {                
                g.DrawLine(pen, x0 + 100, y0 + 100, x1 + 100, y1 + 100);
            }
            g.Dispose();
            pictureBox1.Invalidate();
        }
    }
}