Nadesłany przez Andrzej Borucki, 31 stycznia 2012 12:44
Kod przedstawiony poniżej przedstawia główną część rozwiązania problemu.Pobierz pełne rozwiązanie.
Jeżeli nie odpowiada Ci sposób formatowania kodu przez autora skorzystaj z pretty printer'a i dostosuj go automatycznie do siebie.
ClipLineWF/Form1.cs:
//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(); } } }