Last active
June 6, 2018 11:48
-
-
Save PiotrWegrzyn/37e7e980091a81c8b8c31809f52a0d35 to your computer and use it in GitHub Desktop.
Computational geometry - Point inside a polygon problem and finding the Convex Hull with Graham, Jarvis and Naive methods (c#)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| using System; | |
| using System.Collections.Generic; | |
| using System.ComponentModel; | |
| using System.Data; | |
| using System.Drawing; | |
| using System.Linq; | |
| using System.Text; | |
| using System.Threading.Tasks; | |
| using System.Windows.Forms; | |
| //all fucntions work show nice results for sample data: P1(20,50) P2(100,90) | |
| //you need to create 10 buttons 1 picture box and 5 textboxes | |
| namespace GK_06_Linie | |
| { | |
| public partial class Form1 : Form | |
| { | |
| private System.Drawing.Graphics g; | |
| private System.Drawing.Pen penBlue = new System.Drawing.Pen(Color.Blue, 1); | |
| private System.Drawing.Pen penRed = new System.Drawing.Pen(Color.Red, 1); | |
| private System.Drawing.Pen penGreen = new System.Drawing.Pen(Color.Green, 1); | |
| private System.Drawing.Pen penBlack = new System.Drawing.Pen(Color.Black, 1); | |
| private System.Drawing.Pen penYellow = new System.Drawing.Pen(Color.Yellow, 1); | |
| private System.Drawing.Pen penOrange = new System.Drawing.Pen(Color.Orange, 1); | |
| private System.Drawing.Pen penLightSlateGray = new System.Drawing.Pen(Color.LightSlateGray, 1); | |
| //0 1 2 | |
| //3 4 5 | |
| //6 7 8 | |
| public double det(double[] tab) { | |
| return (tab[0] * tab[4] * tab[8]) + (tab[1] * tab[5] * tab[6]) + (tab[2] * tab[3] * tab[7]) - (tab[2] * tab[4] * tab[6]) - (tab[5] * tab[7] * tab[0]) - (tab[1] * tab[3] * tab[8]); | |
| } | |
| public double[] pointsToDet(PointF P1, PointF P2, PointF P0) { | |
| double[] table = { P1.X, P1.Y, 1, P2.X, P2.Y, 1, P0.X, P0.Y, 1 }; | |
| return table; | |
| } | |
| public double[] pointsToDet2(Point P1, Point P2, Point P0) | |
| { | |
| double[] table = { P1.X, P1.Y, 1, P2.X, P2.Y, 1, P0.X, P0.Y, 1 }; | |
| return table; | |
| } | |
| public int sideOfLine(PointF lineA, PointF lineB, PointF point) { | |
| double v = det(pointsToDet(lineA, lineB, point)); | |
| //if you want to display results in a visually but not mathemacitly correct way. | |
| /* if (lineA.X < lineB.X) | |
| { | |
| v = det(pointsToDet(lineA, lineB, point)); | |
| if (lineA.Y > lineB.Y) v = -v; | |
| } | |
| else { | |
| v = det(pointsToDet(lineB, lineA, point)); | |
| if (lineA.Y > lineB.Y) v = -v; | |
| } | |
| */ | |
| if (v == 0) return 0; | |
| if (v > 0) return 1; | |
| return -1; | |
| } | |
| int determinanat(Point P1, Point P2, Point P3) | |
| { | |
| int[,] Tmatrix = { { P1.X, P1.Y, 1 }, { P2.X, P2.Y, 1 }, { P3.X, P3.Y, 1 } }; | |
| int wynik = Tmatrix[0, 0] * Tmatrix[1, 1] * Tmatrix[2, 2] - Tmatrix[0, 0] * Tmatrix[2, 1] * Tmatrix[1, 2] + Tmatrix[1, 0] * Tmatrix[2, 1] * Tmatrix[0, 2] - Tmatrix[1, 0] * Tmatrix[0, 1] * Tmatrix[2, 2] + Tmatrix[2, 0] * Tmatrix[0, 1] * Tmatrix[1, 2] - Tmatrix[2, 0] * Tmatrix[1, 1] * Tmatrix[0, 2]; | |
| return wynik; | |
| } | |
| ///// | |
| int orientation(Point p, Point q, Point r) | |
| { | |
| int val = (q.Y - p.Y) * (r.X - q.X) - (q.X - p.X) * (r.Y - q.Y); | |
| if (val == 0) | |
| return 0; | |
| return (val > 0) ? 1 : -1; | |
| } | |
| bool doesContain(PointF lineStart,PointF lineEnd,PointF testingPoint){ | |
| int result = sideOfLine(lineStart, lineEnd, testingPoint); | |
| float tmp; | |
| if (lineStart.X > lineEnd.X){ | |
| tmp = lineEnd.X; | |
| lineEnd.X = lineStart.X; | |
| lineStart.X = tmp; | |
| } | |
| if (lineStart.Y > lineEnd.Y){ | |
| tmp = lineEnd.Y; | |
| lineEnd.Y = lineStart.Y; | |
| lineStart.Y = tmp; | |
| } | |
| if (result == 0){ | |
| if ((lineStart.X <= testingPoint.X) && (testingPoint.X<=lineEnd.X) && (lineStart.Y <= testingPoint.Y) && (testingPoint.Y<=lineEnd.Y)) return true; | |
| else return false; | |
| } | |
| return false; | |
| } | |
| bool doCross(PointF line1Start, PointF line1End, PointF line2Start, PointF line2End) | |
| { | |
| if (doesContain(line1Start, line1End, line2Start) && doesContain(line1Start, line1End, line2End)) return true; | |
| if ((sideOfLine(line1Start, line1End, line2Start) != sideOfLine(line1Start, line1End, line2End)) && (sideOfLine(line2Start, line2End, line1Start) != sideOfLine(line2Start, line2End, line1End))) return true; | |
| return false; | |
| } | |
| PointF setPointL(PointF[] points,int n, PointF givenPoint) { | |
| float maxX=0; | |
| for (int i = 0; i < n; i++) { | |
| if (points[i].X > maxX) maxX = points[i].X; | |
| } | |
| return new PointF(maxX+10,givenPoint.Y); | |
| } | |
| bool isInside(PointF[] points,int n, PointF givenPoint) { | |
| int interesections =0; | |
| PointF pointL = setPointL(points, n, givenPoint); | |
| //drawing lines just for testing | |
| //g.DrawLines(penBlue, points); | |
| /* g.DrawLine(penRed, givenPoint, pointL); | |
| g.DrawEllipse(penGreen, givenPoint.X - 2, givenPoint.Y - 2, 4, 4); | |
| g.DrawEllipse(penGreen, pointL.X - 2, pointL.Y - 2, 4, 4); | |
| */ | |
| for (int i = 0; i < n; i++){ | |
| if (doesContain(points[i % n], points[(i + 1) % n], givenPoint)){ //when point is contained by the circumference | |
| //g.DrawLine(penGreen, points[i % n], points[(i + 1) % n]); | |
| return true; | |
| } | |
| } | |
| for (int i = 0; i < n; i++) { | |
| if (doCross(givenPoint, pointL, points[i%n], points[(i + 1)%n])) { | |
| interesections++; | |
| //g.DrawLine(penRed, points[i % n], points[(i + 1) % n]); | |
| if (doesContain(givenPoint, pointL, points[i% n])) { //if it's a vertex | |
| if (doesContain(givenPoint, pointL, points[(i+1) % n])) //when the next point is contained by line: PL (line is collinear with PL) | |
| { | |
| if (sideOfLine(givenPoint, pointL, points[(n + i - 1) % n]) == sideOfLine(givenPoint, pointL, points[(n + i + 2) % n])) | |
| { | |
| interesections--; | |
| //g.DrawLine(penYellow, points[i % n], points[(i + 1) % n]); | |
| } | |
| } | |
| //when it's a vertex but not in a collintear line with PL and the i-1 and i+1 points are on different sides we need to get an even number of intersections | |
| else if ((sideOfLine(givenPoint, pointL, points[(n + i - 1) % n]) != sideOfLine(givenPoint, pointL, points[(n + i + 1) % n]) && (doesContain(givenPoint, pointL, points[(n+i-1) % n])==false))) | |
| { | |
| interesections--; | |
| //g.DrawLine(penBlack, points[i % n], points[(i + 1) % n]); | |
| } | |
| } | |
| } | |
| } | |
| if ((interesections % 2) == 1) return true; | |
| return false; | |
| } | |
| PointF[] findBorderNaive(PointF[] points, int n) { | |
| PointF[] border = new PointF[n]; | |
| bool isBorder = true; | |
| int numberOfPointsInBorder=0; | |
| for (int i = 0; i < n; i++) | |
| { | |
| isBorder = true; | |
| for (int j = 0; j < n; j++) | |
| { | |
| if (j != i) { | |
| for (int k = 0; k < n; k++) | |
| { | |
| if(k != i && k!=j){ | |
| for (int l = 0; l < n; l++) | |
| { | |
| PointF[] tmp = { points[l], points[k], points[j], points[l] }; | |
| if (l != i && l!=k && l!=j && isInside(tmp, 3, points[i])) | |
| { | |
| //g.DrawEllipse(penLightSlateGray, points[i].X - 1, points[i].Y - 1, 2, 2); | |
| l = n; | |
| k = n; | |
| j = n; | |
| isBorder = false; | |
| }; | |
| } | |
| } | |
| } | |
| } | |
| } | |
| if (isBorder) | |
| { | |
| numberOfPointsInBorder++; | |
| border[numberOfPointsInBorder] = points[i]; | |
| } | |
| } | |
| return border; | |
| } | |
| float alpha(PointF p) { | |
| float alpha = p.Y/(Math.Abs(p.X)+Math.Abs(p.Y)); | |
| if (p.X >= 0 && p.Y >= 0) return alpha; | |
| if (p.X < 0 && p.Y >= 0) return 2-alpha; | |
| if (p.X < 0 && p.Y < 0) return 2+Math.Abs(alpha); | |
| if (p.X >= 0 && p.Y < 0) return 4 - Math.Abs(alpha); | |
| return alpha; | |
| } | |
| PointF[] sortByAngle(PointF[] points,int n){ | |
| PointF[] sortedPoints = points; | |
| //Bubble Sort xD | |
| for(int i = 0 ; i < n-1 ; i++){ | |
| for (int j = 0; j < n-1; j++) { | |
| if (alpha(sortedPoints[j]) > alpha(sortedPoints[j + 1])) | |
| { | |
| PointF tmp = sortedPoints[j]; | |
| sortedPoints[j] = sortedPoints[j + 1]; | |
| sortedPoints[j+1] = tmp; | |
| } | |
| if (alpha(sortedPoints[j]) == alpha(sortedPoints[j + 1])) | |
| { | |
| if (sortedPoints[j].X > sortedPoints[j+1].X) | |
| { | |
| PointF tmp = sortedPoints[j]; | |
| sortedPoints[j] = sortedPoints[j + 1]; | |
| sortedPoints[j + 1] = tmp; | |
| } | |
| } | |
| } | |
| } | |
| return sortedPoints; | |
| } | |
| bool isRightTurn(Stack<PointF> stack ,Stack<PointF>backwards, PointF p) { | |
| PointF firstOnstack = stack.Pop(); | |
| if (stack.Any() == false) stack.Push(backwards.Pop()); | |
| PointF secondOnstack = stack.Pop(); | |
| stack.Push(secondOnstack); | |
| stack.Push(firstOnstack); | |
| if (sideOfLine(secondOnstack, firstOnstack, p) == -1 ) return true; | |
| else return false; | |
| } | |
| int findMostLeft(PointF[] points, int n) { | |
| float midX = pictureBox1.Width / 2, midY = pictureBox1.Height / 2, maxX = pictureBox1.Width, maxY = pictureBox1.Height; | |
| int smallest = 0; | |
| for (int i = 0; i < n; i++) { | |
| if (points[i].X < points[smallest].X) { | |
| smallest = i; | |
| } | |
| if (points[i].X == points[smallest].X) { | |
| if (points[i].Y < points[smallest].Y) | |
| { | |
| smallest = i; | |
| } | |
| } | |
| } | |
| return smallest; | |
| } | |
| int findMostRight(PointF[] points, int n) | |
| { | |
| int biggest = 0; | |
| for (int i = 0; i < n; i++) | |
| { | |
| if (points[i].X > points[biggest].X) | |
| { | |
| biggest = i; | |
| } | |
| if (points[i].X == points[biggest].X) | |
| { | |
| if (points[i].Y > points[biggest].Y) | |
| { | |
| biggest = i; | |
| } | |
| } | |
| } | |
| return biggest; | |
| } | |
| bool allPointsOnOneSide(int lineStart, int lineEnd, PointF[] points, int n) | |
| { | |
| int side = 0; | |
| float midX = pictureBox1.Width / 2, midY = pictureBox1.Height / 2, maxX = pictureBox1.Width, maxY = pictureBox1.Height; | |
| int tmp = 1; | |
| while (side == 0) | |
| { | |
| side = sideOfLine(points[lineStart], points[lineEnd], points[(lineStart + tmp) % n]); | |
| tmp++; | |
| } | |
| for (int i = 0; i < n; i++) | |
| { | |
| if (i != lineStart && i != lineEnd) | |
| { | |
| if (side != sideOfLine(points[lineStart], points[lineEnd], points[(i) % n]) && 0 != sideOfLine(points[lineStart], points[lineEnd], points[(i) % n])) | |
| { | |
| g.DrawEllipse(penGreen, midX + points[i].X - 1, midY - points[i].Y - 1, 2, 2); | |
| return false; | |
| } | |
| } | |
| } | |
| return true; | |
| } | |
| void convexHull(Point[] points, int n) | |
| { | |
| if (n < 3) return; | |
| List<Point> hull = new List<Point>(); | |
| int l = 0; | |
| for (int i = 1; i < n; i++) | |
| { | |
| if (points[i].X < points[l].X) | |
| { | |
| l = i; | |
| } | |
| } | |
| int p = l, q; | |
| do | |
| { | |
| hull.Add(points[p]); | |
| q = (p + 1) % n; | |
| for (int i = 0; i < n; i++) | |
| { | |
| if (orientation(points[p], points[i], points[q]) == -1) | |
| { | |
| q = i; | |
| } | |
| } | |
| p = q; | |
| } while (p != l); | |
| for (int i = 0; i < hull.Count - 1; i++) | |
| { | |
| g.DrawLine(penBlack, hull.ElementAt(i), hull.ElementAt(i + 1)); | |
| } | |
| g.DrawLine(penBlack, hull.ElementAt(0), hull.ElementAt(hull.Count - 1)); | |
| } | |
| public Form1() | |
| { | |
| InitializeComponent(); | |
| g = pictureBox1.CreateGraphics(); | |
| } | |
| private void button1_Click(object sender, EventArgs e) | |
| { | |
| pictureBox1.Refresh(); | |
| float midX = pictureBox1.Width / 2, midY = pictureBox1.Height / 2, maxX = pictureBox1.Width, maxY = pictureBox1.Height; | |
| PointF lineStart = new PointF(0, 0); | |
| PointF lineEnd = new PointF(100, 100); | |
| PointF testingPoint = new PointF((float)Double.Parse(textBox2.Text), (float)Double.Parse(textBox3.Text)); | |
| // PointF testingPoint = new PointF(50, 80); | |
| g.DrawLine(penBlue, lineStart.X + midX, midY-lineStart.Y, lineEnd.X+midX, midY-lineEnd.Y); | |
| g.DrawEllipse(penRed, midX+testingPoint.X-2, midY-testingPoint.Y-2, 4, 4); | |
| int result = sideOfLine(lineStart,lineEnd,testingPoint); | |
| if (result == 1) textBox1.Text = "Left"; | |
| if (result == -1) textBox1.Text = "Right"; | |
| if(result ==0)textBox1.Text = "Collinear"; | |
| } | |
| private void button2_Click(object sender, EventArgs e) | |
| { | |
| pictureBox1.Refresh(); | |
| float midX = pictureBox1.Width / 2, midY = pictureBox1.Height / 2, maxX = pictureBox1.Width, maxY = pictureBox1.Height; | |
| PointF lineStart = new PointF(0, 0); | |
| PointF lineEnd = new PointF(100, 100); | |
| PointF testingPoint1 = new PointF((float)Double.Parse(textBox2.Text), (float)Double.Parse(textBox3.Text)); | |
| PointF testingPoint2 = new PointF((float)Double.Parse(textBox4.Text), (float)Double.Parse(textBox5.Text)); | |
| g.DrawLine(penBlue, lineStart.X + midX, midY - lineStart.Y, lineEnd.X + midX, midY - lineEnd.Y); | |
| g.DrawEllipse(penRed, midX + testingPoint1.X - 2, midY - testingPoint1.Y - 2, 4, 4); | |
| g.DrawEllipse(penGreen, midX + testingPoint2.X - 2, midY - testingPoint2.Y - 2, 4, 4); | |
| int result1 = sideOfLine(lineStart, lineEnd, testingPoint1); | |
| int result2 = sideOfLine(lineStart, lineEnd, testingPoint2); | |
| if (result1 == result2) textBox1.Text = "Same Side"; | |
| else textBox1.Text = "Different Sides"; | |
| } | |
| private void button3_Click(object sender, EventArgs e) | |
| { | |
| pictureBox1.Refresh(); | |
| float midX = pictureBox1.Width / 2, midY = pictureBox1.Height / 2, maxX = pictureBox1.Width, maxY = pictureBox1.Height; | |
| PointF lineStart = new PointF(50, 100); | |
| PointF lineEnd = new PointF(100, 50); | |
| PointF testingPoint = new PointF((float)Double.Parse(textBox2.Text), (float)Double.Parse(textBox3.Text)); | |
| g.DrawLine(penBlue, lineStart.X + midX, midY - lineStart.Y, lineEnd.X + midX, midY - lineEnd.Y); | |
| g.DrawEllipse(penRed, midX + testingPoint.X - 2, midY - testingPoint.Y - 2, 4, 4); | |
| if(doesContain(lineStart,lineEnd,testingPoint))textBox1.Text = "Contains R."; | |
| else textBox1.Text = "Does not contain R."; | |
| } | |
| private void button4_Click(object sender, EventArgs e) | |
| { | |
| pictureBox1.Refresh(); | |
| float midX = pictureBox1.Width / 2, midY = pictureBox1.Height / 2, maxX = pictureBox1.Width, maxY = pictureBox1.Height; | |
| //PointF lineStart = new PointF((float)Double.Parse(textBox1.Text), (float)Double.Parse(textBox2.Text)); | |
| PointF line1Start = new PointF(80, 0); | |
| PointF line1End = new PointF(10, 80); | |
| PointF line2Start = new PointF((float)Double.Parse(textBox2.Text), (float)Double.Parse(textBox3.Text)); | |
| PointF line2End = new PointF((float)Double.Parse(textBox4.Text), (float)Double.Parse(textBox5.Text)); | |
| //PointF line2Start = new PointF(-20, 70); | |
| //PointF line2End = new PointF(60, 20); | |
| g.DrawLine(penRed, line1Start.X + midX, midY - line1Start.Y, line1End.X + midX, midY - line1End.Y); | |
| g.DrawLine(penGreen, line2Start.X + midX, midY - line2Start.Y, line2End.X + midX, midY - line2End.Y); | |
| if (doCross(line1Start,line1End,line2Start,line2End))textBox1.Text = "Lines Cross"; | |
| else textBox1.Text = "Lines DO NOT cross"; | |
| } | |
| private void button5_Click(object sender, EventArgs e) | |
| { | |
| pictureBox1.Refresh(); | |
| float midX = pictureBox1.Width / 2, midY = pictureBox1.Height / 2, maxX = pictureBox1.Width, maxY = pictureBox1.Height; | |
| int n = 8; //number of vertexes | |
| //PointF givenPoint = new PointF(20, 70); | |
| PointF givenPoint = new PointF((float)Double.Parse(textBox2.Text), (float)Double.Parse(textBox3.Text)); | |
| PointF[] points = new PointF[n+1]; | |
| points[0] = new PointF(0, 0); | |
| points[1] = new PointF(20, 20); | |
| points[2] = new PointF(30, 50); | |
| points[3] = new PointF(80, 50); | |
| points[4] = new PointF(80, 0); | |
| points[5] = new PointF(100, 50); | |
| points[6] = new PointF(50, 100); | |
| points[7] = new PointF(10, 80); | |
| points[8] = new PointF(0, 0); | |
| PointF pointL = setPointL(points, n, givenPoint); | |
| g.DrawLines(penBlue, points); | |
| g.DrawLine(penRed, givenPoint, pointL); | |
| g.DrawEllipse(penGreen, givenPoint.X - 2, givenPoint.Y - 2, 4, 4); | |
| g.DrawEllipse(penGreen, pointL.X - 2, pointL.Y - 2, 4, 4); | |
| if (isInside(points,n, givenPoint))textBox1.Text = "Inside." ; | |
| else textBox1.Text = "Not inside."; | |
| } | |
| private void button6_Click(object sender, EventArgs e) | |
| { | |
| float midX = pictureBox1.Width / 2, midY = pictureBox1.Height / 2, maxX = pictureBox1.Width, maxY = pictureBox1.Height; | |
| pictureBox1.Refresh(); | |
| g.DrawLine(penBlack, 0, midY, pictureBox1.Width, midY); | |
| g.DrawLine(penBlack, midX, pictureBox1.Height, midX, 0); | |
| int n = 30; //number of vertexes | |
| PointF[] points = new PointF[n]; | |
| Random rnd = new Random(); | |
| for (int i = 0; i < n; i++) { | |
| points[i] = new PointF(midX+rnd.Next(-150, 150), midY+rnd.Next(-100, 100)); | |
| } | |
| for (int i = 0; i < n; i++) | |
| { | |
| g.DrawEllipse(penBlack, points[i].X - 1, points[i].Y - 1, 2, 2); | |
| } | |
| PointF[] border = findBorderNaive(points, n); | |
| for (int i = 0; i < n; i++) | |
| { | |
| if(border[i].Equals(new PointF())==false) g.DrawEllipse(penRed, border[i].X - 1, border[i].Y - 1, 2, 2); | |
| } | |
| } | |
| private void button7_Click(object sender, EventArgs e){ | |
| float midX = pictureBox1.Width / 2, midY = pictureBox1.Height / 2, maxX = pictureBox1.Width, maxY = pictureBox1.Height; | |
| pictureBox1.Refresh(); | |
| g.DrawLine(penBlack, 0, midY, pictureBox1.Width, midY); | |
| g.DrawLine(penBlack, midX, pictureBox1.Height, midX, 0); | |
| int n = 10; | |
| PointF[] points = new PointF[n]; | |
| PointF[] border = new PointF[n]; | |
| int pointsInBorder = 1; | |
| Random rnd = new Random(); | |
| for (int i = 0; i < n; i++) | |
| { | |
| points[i] = new PointF(rnd.Next(-150, 150), rnd.Next(-100, 100)); | |
| } | |
| for (int i = 0; i < n; i++) | |
| { | |
| g.DrawEllipse(penBlue, midX + points[i].X - 1, midY - points[i].Y - 1, 2, 2); | |
| } | |
| int start = findMostLeft(points, n); | |
| bool notSame = true; | |
| int lastBorderPoint = start; | |
| border[0]= points[start]; | |
| while(notSame) { | |
| for (int j = 0; j < n; j++) { | |
| if (lastBorderPoint == j) continue; | |
| if(allPointsOnOneSide(lastBorderPoint,j,points,n)){ | |
| g.DrawEllipse(penOrange, midX + points[j%n].X - 1, midY - points[j%n].Y - 1, 2, 2); | |
| border[pointsInBorder%n]=points[j%n]; | |
| pointsInBorder++; | |
| lastBorderPoint = j; | |
| j = n; | |
| } | |
| } | |
| if (lastBorderPoint == start) notSame = false; | |
| } | |
| for (int i = 0; i < pointsInBorder; i++) | |
| { | |
| g.DrawEllipse(penRed, midX + border[i].X - 1, midY - border[i].Y - 1, 2, 2); | |
| } | |
| } | |
| //sorts N points by their angle via (0,0) and shows them in order in a sequence of colors: Red Green Blue Black for i, i+1, i+2,i+3 and so on | |
| private void button9_Click(object sender, EventArgs e) | |
| { | |
| float midX = pictureBox1.Width / 2, midY = pictureBox1.Height / 2, maxX = pictureBox1.Width, maxY = pictureBox1.Height; | |
| pictureBox1.Refresh(); | |
| g.DrawLine(penBlack, 0, midY, pictureBox1.Width, midY); | |
| g.DrawLine(penBlack, midX, pictureBox1.Height, midX, 0); | |
| int n = 30; | |
| PointF[] points = new PointF[n]; | |
| Random rnd = new Random(); | |
| for (int i = 0; i < n; i++) | |
| { | |
| points[i] = new PointF(rnd.Next(-150, 150), rnd.Next(-100, 100)); | |
| } | |
| /* | |
| points[0] = new PointF(10, 5); | |
| points[1] = new PointF(20, 20); | |
| points[2] = new PointF(30, 50); | |
| points[3] = new PointF(80, 50); | |
| points[4] = new PointF(80, 15); | |
| points[5] = new PointF(100, 50); | |
| points[6] = new PointF(50, 100); | |
| points[7] = new PointF(10, 80); | |
| points[8] = new PointF(20, 50); | |
| points[9] = new PointF(25, 55); | |
| points[10] = new PointF(20, 60); | |
| points[11] = new PointF(30, 40); | |
| points[12] = new PointF(45, 5); | |
| points[13] = new PointF(90, 40); | |
| points[14] = new PointF(55, 60); | |
| points[15] = new PointF(15, 50); | |
| */ | |
| points = sortByAngle(points, n); | |
| for (int i = 0; i < n; i++) | |
| { | |
| if (i % 4 == 0) g.DrawEllipse(penRed, midX + points[i].X - 1, midY - points[i].Y - 1, 2, 2); | |
| if (i % 4 == 1) g.DrawEllipse(penGreen, midX + points[i].X - 1, midY - points[i].Y - 1, 2, 2); | |
| if (i % 4 == 2) g.DrawEllipse(penBlue, midX + points[i].X - 1, midY - points[i].Y - 1, 2, 2); | |
| if (i % 4 == 3) g.DrawEllipse(penBlack, midX + points[i].X - 1, midY - points[i].Y - 1, 2, 2); | |
| } | |
| } | |
| private void button8_Click(object sender, EventArgs e) | |
| { //Graham | |
| float midX = pictureBox1.Width / 2, midY = pictureBox1.Height / 2, maxX = pictureBox1.Width, maxY = pictureBox1.Height; | |
| pictureBox1.Refresh(); | |
| g.DrawLine(penBlack, 0, midY, pictureBox1.Width, midY); | |
| g.DrawLine(penBlack, midX, pictureBox1.Height, midX, 0); | |
| int n = 17; | |
| PointF[] points = new PointF[n]; | |
| Random rnd = new Random(); | |
| points[0] = new PointF(0, 0); //The algorythm has some flaws. The 1st points always stays in the border even when it shouldn't. You can prevent that by assuring the point will be in the border. | |
| for (int i = 1 ; i < n; i++) | |
| { | |
| points[i] = new PointF(rnd.Next(0,150), rnd.Next(0, 100)); | |
| } | |
| /* points[0] = new PointF(0, 0); | |
| points[1] = new PointF(20, 20); | |
| points[2] = new PointF(30, 50); | |
| points[3] = new PointF(80, 50); | |
| points[4] = new PointF(80, 15); | |
| points[5] = new PointF(100, 50); | |
| points[6] = new PointF(50, 100); | |
| points[7] = new PointF(10, 80); | |
| points[8] = new PointF(20, 50); | |
| points[9] = new PointF(25, 55); | |
| points[10] = new PointF(20, 60); | |
| points[11] = new PointF(30, 40); | |
| points[12] = new PointF(45, 5); | |
| points[13] = new PointF(90, 40); | |
| points[14] = new PointF(55, 60); | |
| points[15] = new PointF(15, 50); | |
| points[16] = new PointF(rnd.Next(0, 150), rnd.Next(0, 100)); | |
| */ | |
| points = sortByAngle(points, n); | |
| Stack<PointF> border = new Stack<PointF>(); | |
| Stack<PointF> pointsBackwards = new Stack<PointF>(); | |
| for(int i =n-1 ; i >=0;i--){ | |
| pointsBackwards.Push(points[i]); | |
| } | |
| border.Push(points[0]); | |
| border.Push(points[1]); | |
| border.Push(points[2]); | |
| for (int i = 0; i < n; i++) | |
| { | |
| g.DrawEllipse(penBlue, midX + points[i].X - 1, midY - points[i].Y - 1, 2, 2); | |
| } | |
| for (int i = 3; i < n; i++) | |
| { | |
| while (isRightTurn(border, pointsBackwards, points[i])) border.Pop(); | |
| border.Push(points[i]); | |
| } | |
| while (isRightTurn(border,pointsBackwards, points[0]))border.Pop(); | |
| PointF first; | |
| PointF next = border.Pop(); | |
| PointF tmpf = next; | |
| while (border.Any()) | |
| { | |
| first = next; | |
| next = border.Pop(); | |
| g.DrawLine(penRed, first.X + midX, midY - first.Y, next.X + midX, midY - next.Y); | |
| } | |
| g.DrawLine(penRed, tmpf.X + midX, midY - tmpf.Y, next.X + midX, midY - next.Y); | |
| } | |
| private void button10_Click(object sender, EventArgs e) | |
| { | |
| float midX = pictureBox1.Width / 2, midY = pictureBox1.Height / 2, maxX = pictureBox1.Width, maxY = pictureBox1.Height; | |
| pictureBox1.Refresh(); | |
| g.DrawLine(penBlack, 0, midY, pictureBox1.Width, midY); | |
| g.DrawLine(penBlack, midX, pictureBox1.Height, midX, 0); | |
| int n = 10; | |
| PointF[] points = new PointF[n]; | |
| Random rnd = new Random(); | |
| points[0] = new PointF(rnd.Next(-100, 80), rnd.Next(-100, 80)); | |
| points[1] = new PointF(20, 20); | |
| points[2] = new PointF(30, 50); | |
| points[3] = new PointF(80, 50); | |
| points[4] = new PointF(80, 15); | |
| points[5] = new PointF(100, 50); | |
| points[6] = new PointF(50, 100); | |
| points[7] = new PointF(10, 80); | |
| points[8] = new PointF(20, 50); | |
| points[9] = new PointF(25, 55); | |
| /* for (int i = 1; i < n; i++) | |
| { | |
| points[i] = new PointF(rnd.Next(0, 150), rnd.Next(0, 100)); | |
| } | |
| */ | |
| if (allPointsOnOneSide(0, 1, points, 5)) textBox1.Text = "all on one side"; | |
| else textBox1.Text = "different sides"; | |
| for (int i = 0; i < n; i++) | |
| { | |
| g.DrawEllipse(penBlue, midX + points[i].X - 1, midY - points[i].Y - 1, 2, 2); | |
| } | |
| g.DrawLine(penRed, midX + points[0].X, midY - points[0].Y, midX + points[1].X, midY - points[1].Y); | |
| } | |
| private void button11_Click(object sender, EventArgs e) | |
| { | |
| Random rnd = new Random(); | |
| pictureBox1.Refresh(); | |
| Stack<Point> otoczka = new Stack<Point>(); | |
| int n = 10; | |
| Point[] arrP = new Point[n]; | |
| for (int i = 1; i < n; i++) | |
| { | |
| arrP[i] = new Point(rnd.Next(0, 150), rnd.Next(0, 100)); | |
| } | |
| // = { new Point(rnd.Next(90, 110), rnd.Next(90, 150)), new Point(rnd.Next(90, 110), rnd.Next(90, 110)), new Point(rnd.Next(130, 150), rnd.Next(170, 180)), new Point(rnd.Next(230, 400), rnd.Next(140, 180)), new Point(rnd.Next(280, 320), rnd.Next(150, 200)), new Point(rnd.Next(190, 210), rnd.Next(90, 110)), new Point(rnd.Next(150, 170), rnd.Next(160, 180)), new Point(rnd.Next(110, 140), rnd.Next(100, 150)) }; | |
| List<Point> punkty = new List<Point>(); | |
| punkty.AddRange(arrP); | |
| for (int i = 0; i < n; i++)g.DrawEllipse(penBlue, arrP[i].X - 1, arrP[i].Y - 1, 2, 2); | |
| convexHull(arrP, n); | |
| } | |
| private void button12_Click(object sender, EventArgs e) | |
| { int n = 1000000; | |
| Random rnd = new Random(); | |
| Point[] arrP = new Point[n]; | |
| textBox1.Text = "Same"; | |
| for (int i = 1; i < n; i++) | |
| { | |
| arrP[i] = new Point(rnd.Next(-150, 150), rnd.Next(-100, 100)); | |
| } | |
| for (int i = 0; i < n-2; i++) { | |
| if (orientation(arrP[i], arrP[i + 1], arrP[i + 2])!= sideOfLine(arrP[i+1], arrP[i ], arrP[i + 2])) textBox1.Text = "different"; | |
| } | |
| } | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment