Für diese Lösung habe ich den sogenannten "Gift-wrapping-algorithm" benutzt. Dieser ist sicherlich nicht der schnellste aber meiner Meinung nach der einfachste zum Verstehen. Für den Algorithmus habe ich mich an dem Pseudocode aus diesem Wikipedia-Artikel orientiert
Link .
C#-Code
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Drawing.Drawing2D;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;
namespace WindowsFormsApplication1
{
public partial class Form1 : Form
{
public List<PointF> pointList = new List<PointF>();
public Form1()
{
InitializeComponent();
}
private void Form1_Load(object sender, EventArgs e)
{
}
private void button1_Click(object sender, EventArgs e)
{
Random r = new Random();
zeichnenZufälligePunkte(panel1, r.Next(10, 20));
}
public void zeichnenZufälligePunkte(Panel p,int anzahlPunkte)
{
Graphics g = p.CreateGraphics();
Pen pen = new Pen(Color.Black);
SolidBrush sb = new SolidBrush(Color.Blue);
for(int i = 0; i < anzahlPunkte; i++)
{
Random r = new Random();
int x = r.Next(0, p.Width);
int y = r.Next(0, p.Height);
g.FillEllipse(sb, x, y, 5, 5);
PointF tempP = new PointF(Convert.ToSingle(x), Convert.ToSingle(y));
pointList.Add(tempP);
System.Threading.Thread.Sleep(10);
}
foreach(PointF tp in pointList)
{
listBox1.Items.Add("[" + tp.X + ";" + tp.Y + "]");
}
}
private void button2_Click(object sender, EventArgs e)
{
zeichneHülle(panel1);
}
public void zeichneHülle(Panel p)
{
Graphics g = p.CreateGraphics();
Pen pen = new Pen(Color.Black);
if (pointList.Count >= 3)
{
List<PointF> hülle = GetPunkteFürKonvexeHülle(pointList);
PointF[] pArr = hülle.ToArray();
for (int i = 0; i < pArr.Length; i++)
{
if (i == pArr.Length - 1)
{
g.DrawLine(pen, pArr[i], pArr[0]);
}
else
{
g.DrawLine(pen, pArr[i], pArr[i + 1]);
}
}
}
}
//Diese Funktion ermittelt alle Punkte für die Kurve mit Hilfe dem "Gift-wrapping-algorithm"
public static List<PointF> GetPunkteFürKonvexeHülle(List<PointF> punkte)
{
List<PointF> hülle = new List<PointF>();
PointF Startpunkt = punkte.SelectMin(p => p.X);
PointF Endpunkt;
do
{
hülle.Add(Startpunkt);
Endpunkt = punkte[0];
for (int i = 1; i < punkte.Count; i++)
{
if ((Startpunkt == Endpunkt)
|| (Orientation(Startpunkt, Endpunkt, punkte[i]) == -1))
{
Endpunkt = punkte[i];
}
}
Startpunkt = Endpunkt;
}
while (Endpunkt != hülle[0]);
return hülle;
}
private static int Orientation(PointF p1, PointF p2, PointF p)
{
float Orin = (p2.X - p1.X) * (p.Y - p1.Y) - (p.X - p1.X) * (p2.Y - p1.Y);
if (Orin > 0)
return -1; //Der Punkt liegt auf der linken Seite der Gerade
if (Orin < 0)
return 1; //Der Punkt liegt auf der rechten Seite der Gerade
return 0; // Der Punkt liegt auf der Gerade
}
}
}
//Extension um den Punkt mit der geringsten Ordinate(x-Wert) festzustellen
static class IEnumerableExtensions
{
public static T SelectMin<T>(this IEnumerable<T> source, Func<T, float> selector)
{
if (source == null)
{
throw new ArgumentNullException("source");
}
float min = 0;
T returnValue = default(T);
bool flag = false;
foreach (T t in source)
{
float value = selector(t);
if (flag)
{
if (value < min)
{
returnValue = t;
min = value;
}
}
else
{
min = value;
returnValue = t;
flag = true;
}
}
if (!flag)
{
throw new InvalidOperationException("source is empty");
}
return returnValue;
}
}