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

public class GiftWrapping
{
	// Diese Methode bestimmt die Orientierung des drei Punkte. Wenn die Punkte im Uhrzeigersinn sind, wird ein Wert größer als 0 zurückgegeben. Wenn die Punkte im Gegenuhrzeigersinn sind, wird ein Wert kleiner als 0 zurückgegeben. Wenn die Punkte kollinear sind, wird der Wert 0 zurückgegeben.
	public int GetOrientation(Point point1, Point point2, Point point3)
	{
		return (point2.Y - point1.Y) * (point3.X - point2.X) - (point2.X - point1.X) * (point3.Y - point2.Y);
	}
	
	// Diese Methode gibt eine Liste der Punkte der konvexen Hülle zurück
	public List<Point> GetConvexHull(List<Point> points)
	{
		List<Point> convexHull = new List<Point>();
		int numberOfpoints = points.Count;
		if (numberOfpoints < 3) // Wenn weniger als 3 Punkte vorhanden sind, wird eine leere Liste zurückgegeben
		{
			return convexHull;
		}
		float minimumX = points[0].X;
		int indexOfMinimum = 0;
		// Diese for-Schleife durchläuft die verbleibenden Punkte und ermittelt den Punkt ganz links und bei Gleichheit den untersten Punkt
		for (int i = 1; i < numberOfpoints; i++)
		{
			float x = points[i].X;
			if (x < minimumX || minimumX == x && points[i].Y < points[indexOfMinimum].Y)
			{
				minimumX = points[i].X;
				indexOfMinimum = i;
			}
		}
		int currentIndex = indexOfMinimum;
		int nextIndex;
		// Diese do-while-Schleife beginnt beim Punkt ganz links und läuft im Gegenuhrzeigersinn, bis sie wieder den Anfangspunkt erreicht. Die Anzahl der Durchläufe der Schleife ist die Anzahl der Punkte der konvexen Hülle.
		do
		{
			convexHull.Add(points[currentIndex]); // Fügt den aktuellen Punkt der Liste der Punkte der konvexen Hülle hinzu
			nextIndex = (currentIndex + 1) % numberOfpoints; // Erhöht den Index nextIndex um 1 und setzt ihn zurück auf 0, wenn der maximale Wert überschritten ist
			// Diese for-Schleife durchläuft alle Punkte und sucht einen Punkt mit Index nextIndex, sodass die Punkte mit den Indexen currentIndex, nextIndex, x für alle Indexe x im Gegenuhrzeigersinn sind
			for (int i = 0; i < numberOfpoints; i++)
			{
				if (GetOrientation(points[currentIndex], points[nextIndex], points[i]) < 0) // Wenn der Punkt mit Index i weiter im Gegenuhrzeigersinn liegt als der Punkt mit Index nextIndex, wird nextIndex aktualisiert
				{
					nextIndex = i;
				}
			}
			// Der Punkt mit Index nextIndex ist der Punkt, der in Bezug auf den Punkt mit Index currentIndex am weitesten im Gegenuhrzeigersinn liegt. Nach der folgenden Zuweisung wird dieser Punkt der konvexen Hülle hinzugefügt.
			currentIndex = nextIndex;
		}
		while (currentIndex != indexOfMinimum); // While we don't come to first
		return convexHull;
	}
}

// Klasse für das Hauptfenster
public partial class MainForm : Form
{
	private Graphics graphics;
	
	private List<Point> points = new List<Point>(); // Liste der Punkte
	private List<Point> convexHull = new List<Point>(); // Liste der Punkte der konvexen Hülle
	private double x1, y1, x2, y2;
	
	public MainForm()
	{
		x1 = 100; y1 = 100; x2 = 700; y2 = 700; // Setzt die Koordinaten der Eckpunkte der quadratischen Zeichenfläche
		Random random = new Random(); // Initialisiert den Zufallsgenerator
		int numberOfPoints = 100;
		for (int i = 0; i < numberOfPoints; i++) // Diese for-Schleife erzeugt 100 zufällige Punkte innerhalb der quadratischen Zeichenfläche
		{
			Point point = new Point();
			point.X = (int)(random.NextDouble() * (x2 - x1) + x1);
			point.Y = (int)(random.NextDouble() * (y2 - y1) + y1);
			points.Add(point); // Fügt den Punkt der Liste hinzu
		}
		
		GiftWrapping giftWrapping = new GiftWrapping(); // Erzeugt ein Objekt der Klasse GiftWrapping
		convexHull = giftWrapping.GetConvexHull(points); // Aufruf der Methode, die die konvexe Hülle zurückgibt
		
		InitializeComponent();
		Text = "Konvexe Hülle";
		Width = 800;
		Height = 800;
		graphics = CreateGraphics(); // Erzeugt ein Grafikobjekt für das Zeichnen auf dem Hauptfenster.
		Paint += OnPaint; // Verknüpft die Ereignisbehandlungsmethode mit dem Paint Ereignis des Hauptfensters.
	}
	
	// Diese Methode wird aufgerufen, wenn das Hauptfenster gezeichnet wird.
	private void OnPaint(object sender, PaintEventArgs e)
	{
		for (int i = 0; i < points.Count; i++)
		{
			graphics.FillRectangle(new SolidBrush(Color.FromArgb(0, 0, 0)), points[i].X - 1, points[i].Y - 1, 2, 2); // Zeichnet die Punkte
		}
		int numberOfPoints = convexHull.Count;
		for (int i = 0; i < numberOfPoints; i++)
		{
			graphics.DrawLine(new Pen(Color.FromArgb(0, 0, 255)), convexHull[i], convexHull[(i + 1) % numberOfPoints]); // Zeichnet die Kanten der konvexen Hülle
		}
	}
}