Voronoi-Diagramm

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

// Diese Klasse implementiert eine Vergleichsmethode für das Sortieren der Punkte
class PointComparer : Comparer<PointF>
{
	// Vergleichsmethode, die die Punkte von links nach rechts und bei Gleichheit von oben nach unten sortiert
	public override int Compare(PointF point1, PointF point2)
	{
		int result = point1.X.CompareTo(point2.X);
		if (result == 0)
		{
			return point1.Y.CompareTo(point2.Y);
		}
		return result;
	}
}

// Diese Klasse implementiert eine Vergleichsmethode für das Sortieren der CircleEvents
class EventComparer : Comparer<CircleEvent>
{
	// Vergleichsmethode, die die CircleEvents
	public override int Compare(CircleEvent event1, CircleEvent event2)
	{
		return event1.x.CompareTo(event2.x);
	}
}

// Klasse für die CircleEvents
class CircleEvent
{
	public double x; // x-Koordinate der Sweep Line
	public PointF point; // Das Zentrum, das der Brennpunkt der Parabel ist
	public ParabolaArc arc; // Parabelbogen
	public bool isValid; // Gibt an, ob das CircleEvent aktuell ist

	// Konstruktor für die Initialisierung der Attribute
	public CircleEvent(double _x, PointF _point, ParabolaArc _arc)
	{
		x = _x;
		point = _point;
		arc = _arc;
		isValid = true;
	}
};

// Klasse für die Parabelbögen
class ParabolaArc
{
	public PointF point; // Das Zentrum, das der Brennpunkt der Parabel ist
	public ParabolaArc previousArc, nextArc; // Benachbarte Parabelbögen
	public CircleEvent circleEvent; // Zugeordnetes CircleEvent
	public VoronoiEdge edge1, edge2; // Benachbarte Voronoi-Kanten

	// Konstruktor für die Initialisierung der Attribute
	public ParabolaArc(PointF _point, ParabolaArc arc1, ParabolaArc arc2)
	{
		{
			point = _point;
			previousArc = arc1;
			nextArc = arc2;
			circleEvent = null;
			edge1 = null;
			edge2 = null;
		}
	}
}

// Klasse für die Voronoi-Kanten
class VoronoiEdge
{
	public PointF point1, point2; // Endpunkte der Kante
	public bool isFinished; // Gibt an, ob die Kante fertiggestellt wurde
	public static List<VoronoiEdge> edges = new List<VoronoiEdge>(); // Liste der Kanten

	// Konstruktor für die Initialisierung der Attribute
	public VoronoiEdge(PointF point)
	{
		point1 = point; // Setzt den ersten Endpunkt
		point2.X = 0;
		point2.Y = 0;
		isFinished = false;
		edges.Add(this); // Fügt die Kante der Liste hinzu
	}

	// Diese Methode stellt die Kante fertig
	public void Finish(PointF point)
	{
		if (!isFinished)
		{
			point2 = point; // Setzt den zweiten Endpunkt
			isFinished = true;
		}
	}
}

// Klasse, die die Methoden für den Algorithmus von Fortune deklariert
class Fortune
{
	public ParabolaArc root = null;
	public List<PointF> points = new List<PointF>(); // Liste der Punkte
	public List<CircleEvent> circleEvents = new List<CircleEvent>(); // Liste der CircleEvents

	// Verarbeitet den verbleibenden Punkt (rechts der Sweep Line), der ganz links liegt
	public void ProcessPoint(double x)
	{
		PointF point = points[0];
		points.RemoveAt(0); // Entfernt den ersten Punkt aus der Liste
		AddNewArc(point, x); // Fügt der Beach Line einen Parabelbogen hinzu
	}

	// Diese Methode verarbeitet das CircleEvent mit der kleinsten x-Koordinate
	public void ProcessCircleEvent()
	{
		CircleEvent circleEvent = circleEvents[0];
		circleEvents.RemoveAt(0); // Entfernt das erste CircleEvent aus der Liste
		if (circleEvent.isValid) // Wenn das CircleEvent aktuell ist
		{
			VoronoiEdge edge = new VoronoiEdge(circleEvent.point); // Erzeugt eine neue Kante
			// Entfernt den zugehörigen Parabelbogen
			ParabolaArc arc = circleEvent.arc;
			if (arc.previousArc != null)
			{
				arc.previousArc.nextArc = arc.nextArc;
				arc.previousArc.edge2 = edge;
			}
			if (arc.nextArc != null)
			{
				arc.nextArc.previousArc = arc.previousArc;
				arc.nextArc.edge1 = edge;
			}
			// Stellt die benachbarten Kanten des Parabelbogens fertig
			if (arc.edge1 != null)
			{
				arc.edge1.Finish(circleEvent.point);
			}
			if (arc.edge2 != null)
			{
				arc.edge2.Finish(circleEvent.point);
			}
			// Prüft die CircleEvents auf beiden Seiten des Parabelbogens
			if (arc.previousArc != null)
			{
				CheckCircleEvent(arc.previousArc, circleEvent.x);
			}
			if (arc.nextArc != null)
			{
				CheckCircleEvent(arc.nextArc, circleEvent.x);
			}
		}
	}

	// Diese Methode fügt einen neuen Parabelbogen mit dem gegebenen Brennpunkt hinzu
	public void AddNewArc(PointF point, double x)
	{
		if (root == null)
		{
			root = new ParabolaArc(point, null, null);
			return;
		}
		// Bestimmt den aktuellen Parabelbogen mit der y-Koordinate des Punkts point
		ParabolaArc arc;
		for (arc = root; arc != null; arc = arc.nextArc) // Diese for-Schleife durchläuft die Parabelbögen
		{
			PointF intersection1 = new PointF(0, 0), intersection2 = new PointF(0, 0);
			if (GetIntersection(point, arc, ref intersection1)) // Wenn die neue Parabel den Parabelbogen schneidet
			{
				// Dupliziert gegebenenfalls den Parabelbogen
				if (arc.nextArc != null && !GetIntersection(point, arc.nextArc, ref intersection2))
				{
					arc.nextArc.previousArc = new ParabolaArc(arc.point, arc, arc.nextArc);
					arc.nextArc = arc.nextArc.previousArc;
				}
				else
				{
					arc.nextArc = new ParabolaArc(arc.point, arc, null);
				}
				arc.nextArc.edge2 = arc.edge2;
				// Fügt einen neuen Parabelbogen zwischen den Parabelbögen arc und arc.nextArc ein.
				arc.nextArc.previousArc = new ParabolaArc(point, arc, arc.nextArc);
				arc.nextArc = arc.nextArc.previousArc;
				arc = arc.nextArc;
				// Verbindet 2 neue Kanten mit den Endpunkten des Parabelbogens
				arc.previousArc.edge2 = arc.edge1 = new VoronoiEdge(intersection1);
				arc.nextArc.edge1 = arc.edge2 = new VoronoiEdge(intersection1);
				// Prüft die benachbarten CircleEvents des Parabelbogens
				CheckCircleEvent(arc, point.X);
				CheckCircleEvent(arc.previousArc, point.X);
				CheckCircleEvent(arc.nextArc, point.X);
				return;
			}
		}
		// Spezialfall: Wenn der Parabelbogen keinen anderen schneidet, wird er der doppelt verketteten Liste hinzugefügt
		for (arc = root; arc.nextArc != null; arc = arc.nextArc); // Bestimmt den letzten Parabelbogen
		arc.nextArc = new ParabolaArc(point, arc, null);
		// Fügt eine Kante zwischen den Parabelbögen ein
		PointF start = new PointF(0, 0);
		start.X = (float)x;
		start.Y = (arc.nextArc.point.Y + arc.point.Y) / 2;
		arc.edge2 = arc.nextArc.edge1 = new VoronoiEdge(start);
	}

	// Diese Methode erzeugt wenn nötig ein neues CircleEvent für den gegebenen Parabelbogen
	public void CheckCircleEvent(ParabolaArc arc, double _x)
	{
		// Setzt das bisherige CircleEvent auf nicht aktuell
		if (arc.circleEvent != null && arc.circleEvent.x != _x)
		{
			arc.circleEvent.isValid = false;
		}
		arc.circleEvent = null;
		if (arc.previousArc == null || arc.nextArc == null)
		{
			return;
		}
		double x = 0;
		PointF point = new PointF(0, 0);
		if (GetRightmostCirclePoint(arc.previousArc.point, arc.point, arc.nextArc.point, ref x, ref point) && x > _x)
		{
			arc.circleEvent = new CircleEvent(x, point, arc); // Erzeugt ein neues CircleEvent
			circleEvents.Add(arc.circleEvent);
			circleEvents.Sort(new EventComparer()); // Sortiert die Liste
		}
	}

	// Diese Methode bestimmt die x-Koordinate des Kreises durch die 3 Punkte, der ganz rechts liegt und prüft, ob die 3 Punkte auf einer Geraden liegen
	public bool GetRightmostCirclePoint(PointF point1, PointF point2, PointF point3, ref double x, ref PointF point)
	{
		// Prüft, dass die 3 Punkt im Uhrzeigersinn orientiert sind
		if ((point2.X - point1.X) * (point3.Y - point1.Y) > (point3.X - point1.X) * (point2.Y - point1.Y))
		{
			return false;
		}
		double x1 = point2.X - point1.X;
		double y1 = point2.Y - point1.Y;
		double a = 2 * (x1 * (point3.Y - point2.Y) - y1 * (point3.X - point2.X));
		if (a == 0)
		{
			return false;  // Wenn die 3 Punkte auf einer Geraden liegen, wird false zurückgegeben
		}
		double x2 = point3.X - point1.X;
		double y2 = point3.Y - point1.Y;
		double a1 = x1 * (point1.X + point2.X) + y1 * (point1.Y + point2.Y);
		double a2 = x2 * (point1.X + point3.X) + y2 * (point1.Y + point3.Y);
		// Berechnet den Mittelpunkt des Kreises durch die 3 Punkte
		point.X = (float)((y2 * a1 - y1 * a2) / a);
		point.Y = (float)((x1 * a2 - x2 * a1) / a);
		x = point.X + Math.Sqrt(Math.Pow(point1.X - point.X, 2) + Math.Pow(point1.Y - point.Y, 2)); // x-Koordinate des Mittelpunkts plus Radius
		return true;
	}

	// Diese Methode bestimmt gegebenenfalls den Schnittpunkt zwischen der Parabel mit dem gegebenen Brennpunkt und dem Parabelbogen und prüft, ob er existiert
	public bool GetIntersection(PointF point, ParabolaArc arc, ref PointF intersection)
	{
		if (arc.point.X == point.X)
		{
			return false; // Wenn die Brennpunkte übereinstimmen, wird false zurückgegeben
		}
		double y1 = 0, y2 = 0;
		if (arc.previousArc != null)
		{
			y1 = GetParabolasIntersection(arc.previousArc.point, arc.point, point.X).Y; // Berechnet die y-Koordinate des Schnittpunkts zwischen dem aktuellen und dem vorherigen Parabelbogen
		}
		if (arc.nextArc != null)
		{
			y2 = GetParabolasIntersection(arc.point, arc.nextArc.point, point.X).Y; // Berechnet die y-Koordinate des Schnittpunkts zwischen dem aktuellen und dem nächsten Parabelbogen
		}
		// Berechnet die Koordinaten des Schnittpunkts, falls vorhanden
		if ((arc.previousArc == null || y1 <= point.Y) && (arc.nextArc == null || point.Y <= y2))
		{
			intersection.Y = point.Y;
			intersection.X = (arc.point.X * arc.point.X + (arc.point.Y - intersection.Y) * (arc.point.Y - intersection.Y) - point.X * point.X) / (2 * arc.point.X - 2 * point.X);
			return true;
		}
		return false;
	}

	// Diese Methode bestimmt den Schnittpunkt zwischen den Parabeln mit den gegebenen Brennpunkten für die Sweep Line mit der gegebenen x-Koordinate
	public PointF GetParabolasIntersection(PointF point1, PointF point2, double x)
	{
		PointF intersection = new PointF(0, 0), point = point1;
		// Spezialfälle
		if (point1.X == point2.X)
		{
			intersection.Y = (point1.Y + point2.Y) / 2;
		}
		else if (point2.X == x)
		{
			intersection.Y = point2.Y;
		}
		else if (point1.X == x)
		{
			intersection.Y = point1.Y;
			point = point2;
		}
		else // Standardfall
		{
			// Verwendet die Lösungsformel für quadratische Gleichungen, um die y-Koordinate des Schnittpunkts zu berechnen
			double x1 = 2 * (point1.X - x);
			double x2 = 2 * (point2.X - x);
			double a = 1 / x1 - 1 / x2;
			double b = -2 * (point1.Y / x1 - point2.Y / x2);
			double c = (point1.Y * point1.Y + point1.X * point1.X - x * x) / x1 - (point2.Y * point2.Y + point2.X * point2.X - x * x) / x2;
			intersection.Y = (float)((-b - Math.Sqrt(b * b - 4 * a * c)) / (2 * a));
		}
		// Setzt die y-Koordinate in die Parabelgleichung ein, um die x-Koordinate zu berechnen
		intersection.X = (float)((point.X * point.X + (point.Y - intersection.Y) * (point.Y - intersection.Y) - x * x) / (2 * point.X - 2 * x));
		return intersection;
	}

	// Diese Methode stellt die benachbarten Kanten der Parabelbögen fertig
	public void FinishEdges(double x1, double y1, double x2, double y2)
	{
		// Verschiebt die Sweep Line, sodass keine Parabel die Zeichenfläche schneiden kann
		double x = x2 + (x2 - x1) + (y2 - y1);
		// Verlängert jede benachbarte Kante bis zum Schnittpunkt der neuen Parabeln
		for (ParabolaArc arc = root; arc.nextArc != null; arc = arc.nextArc)
		{
			if (arc.edge2 != null)
			{
				arc.edge2.Finish(GetParabolasIntersection(arc.point, arc.nextArc.point, 2 * x));
			}
		}
	}
}

// Klasse für das Hauptfenster
public partial class MainForm : Form
{
	private Graphics graphics;
	
	private List<PointF> points = new List<PointF>(); // Liste der Punkte
	private double x1, y1, x2, y2;

	public MainForm()
	{
		x1 = 0; y1 = 0; x2 = 800; y2 = 800; // Setzt die Koordinaten der Eckpunkte der quadratischen Zeichenfläche
		Random random = new Random(); // Initialisiert den Zufallsgenerator
		int numberOfPoints = 10;
		for (int i = 0; i < numberOfPoints; i++) // Diese for-Schleife erzeugt 10 zufällige Punkte innerhalb der quadratischen Zeichenfläche
		{
			PointF point = new PointF();
			point.X = (float)(random.NextDouble() * (x2 - x1) + x1);
			point.Y = (float)(random.NextDouble() * (y2 - y1) + y1);
			points.Add(point); // Fügt den Punkt der Liste hinzu
		}
		points.Sort(new PointComparer()); // Sortiert die Punkte
		Fortune fortune = new Fortune(); // Erzeugt ein Objekt der Klasse Fortune
		fortune.points.AddRange(points); // Fügt die Punkte der Liste hinzu

		// Diese for-Schleife verarbeitet bei jedem Durchlauf das Element mit der kleinsten x-Koordinate
		while (fortune.points.Count != 0) // Solange die Liste der Punkte nicht leer ist
		{
			if (fortune.circleEvents.Count != 0 && fortune.circleEvents[0].x <= fortune.points[0].X)
			{
				fortune.ProcessCircleEvent(); // Aufruf der Methode, verarbeitet das CircleEvent
			}
			else
			{
				fortune.ProcessPoint(x1); // Aufruf der Methode, verarbeitet den Punkt
			}
		}
		// Nachdem alle Punkte verarbeitet wurden, werden die verbleibenden circleEvents verarbeitet.
		while (fortune.circleEvents.Count != 0) // Solange die Liste der CircleEvents nicht leer ist
		{
			fortune.ProcessCircleEvent();
		}
		fortune.FinishEdges(x1, y1, x2, y2); // Aufruf der Methode, stellt die benachbarten Kanten der Parabelbögen fertig

		InitializeComponent();
		Text = "Voronoi-Diagramm";
		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 Voronoi-Zentrums
		}
		for (int i = 0; i < VoronoiEdge.edges.Count; i++)
		{
			graphics.DrawLine(new Pen(Color.FromArgb(0, 0, 255)), VoronoiEdge.edges[i].point1, VoronoiEdge.edges[i].point2); // Zeichnet die Voronoi-Kanten
		}
	}
}