C# :: Aufgabe #176

3 Lösungen Lösungen öffentlich

Konvexe Hüllkurve um Punktwolke

Fortgeschrittener - C# von hollst - 04.05.2017 um 10:36 Uhr
In der X-Y-Ebene seinen N Punkte zufällig verteilt (Bild 1). Man schreibe ein Programm, das die konvexe Hüllkurve um diese Punktwolke zeichnet (Bild 2).

Zum Verständnid, was die konvexe Hüllkurve um eine Punktwolke ist, stelle man sich die Punkte als fixierte Push-Pins oder Nägel auf einem Pinbord (möglichst nicht aus Kork) oder Holzbrett vor. Jetzt nehme man einen Gummiring (z. B. vom Einweckglas) und spanne diesen so um die Pins, dass sich alle im „Inneren“ des Gummiringes befinden (eine „360-Grad-Umwicklung“ eines Pins ist nicht erlaibt). Der so verformte Gummiring ergibt aus physikalischen Gründen einen geschlossenen Linienzug. Dieser Linienzug wird konvexe Hüllkurve um die Punktwolke genannt.

Lösungen:

vote_ok
von daniel59 (2700 Punkte) - 05.05.2017 um 15:47 Uhr
MainWindow.xaml.cs
Quellcode ausblenden C#-Code
using System;
using System.Collections.Generic;
using System.Linq;
using System.Windows;
using System.Windows.Controls;
using System.Windows.Media;
using System.Windows.Shapes;

namespace WpfKonvexeHuellkurve
{
    /// <summary>
    /// Interaktionslogik für MainWindow.xaml
    /// </summary>
    public partial class MainWindow : Window
    {
        private static readonly Random rnd = new Random();
        private List<Point> points;

        const int size = 6;
        const int padding = 20;
        private readonly Brush brush = Brushes.Blue;
        public MainWindow()
        {
            InitializeComponent();
        }

        private void DrawRandomPoints(int n)
        {
            points = new List<Point>();

            listBoxPoints.Items.Clear();
            canvasDraw.Children.Clear();
            canvasDraw.UpdateLayout();
            int width = (int)canvasDraw.ActualWidth;
            int height = (int)canvasDraw.ActualHeight;

            for (int i = 0; i < n; i++)
            {
                int x = rnd.Next(padding, width - padding);
                int y = rnd.Next(padding, height - padding);
                points.Add(new Point(x, y));

                Ellipse ell = new Ellipse() { Width = size, Height = size, Stroke = brush, StrokeThickness = double.Epsilon, Fill = brush };
                Canvas.SetLeft(ell, x - size / 2);
                Canvas.SetTop(ell, y - size / 2);

                canvasDraw.Children.Add(ell);

                listBoxPoints.Items.Add($"X: {x} | Y: {y}");
            }
        }

        private void buttonDrawRandom_Click(object sender, RoutedEventArgs e)
        {
            int n;
            if (int.TryParse(textBoxNumber.Text, out n))
            {
                if (n >= 3)
                {
                    DrawRandomPoints(n);
                }
            }
        }

        private void DrawConvexLine()
        {
            PointCollection points = new PointCollection(GetPoints().Distinct());
            Polygon convex = new Polygon() { Points = points, Stroke = Brushes.Red, StrokeThickness = 2 };
            canvasDraw.Children.Add(convex);
        }

        private IEnumerable<Point> GetPoints()
        {
            var westernmost = points.Where(b => b.X == points.Min(a => a.X)).OrderByDescending(a => a.Y);
            var northernmost = points.Where(b => b.Y == points.Min(a => a.Y)).OrderBy(a => a.X);
            var easternmost = points.Where(b => b.X == points.Max(a => a.X)).OrderBy(a => a.Y);
            var southernmost = points.Where(b => b.Y == points.Max(a => a.Y)).OrderByDescending(a => a.X);

            Point west = westernmost.First();
            Point north = northernmost.First();
            Point east = easternmost.First();
            Point south = southernmost.First();
            Point start = new Point(west.X, west.Y);

            foreach (var point in westernmost)
            {
                west = point;
                yield return west;
            }

            while (west != north)
            {
                west = GetNextPointWest(west);
                yield return west;
            }

            foreach (var point in northernmost)
            {
                north = point;
                yield return north;
            }

            while (north != east)
            {
                north = GetNextPointNorth(north);
                yield return north;
            }

            foreach (var point in easternmost)
            {
                east = point;
                yield return east;
            }
            
            while (east != south)
            {
                east = GetNextPointEast(east);
                yield return east;
            }

            foreach (var point in southernmost)
            {
                south = point;
                yield return south;
            }
            
            while (south != start)
            {
                south = GetNextPointSouth(south);
                yield return south;
            }
        }

        private Point GetNextPointWest(Point west)
        {
            var northern = points.Where(p => p.X > west.X && p.Y < west.Y);

            foreach (Point p in northern)
            {
                Vector r = p - west;
                Vector s = new Vector(west.X, west.Y);

                double m = r.Y / r.X;
                double c = west.Y - (m * west.X);

                if (!northern.Any(a => Math.Round((a.X * m + c)) > a.Y))
                {
                    return p;
                }
            }

            return default(Point);
        }

        private Point GetNextPointNorth(Point north)
        {
            var eastern = points.Where(p => p.Y > north.Y && p.X > north.X);

            foreach (Point p in eastern)
            {
                Vector r = p - north;
                Vector s = new Vector(north.X, north.Y);

                double m = r.Y / r.X;
                double c = north.Y - (m * north.X);

                if (!eastern.Any(a => Math.Round((a.X * m + c)) > a.Y))
                {
                    return p;
                }
            }

            return default(Point);
        }

        private Point GetNextPointEast(Point east)
        {
            var southern = points.Where(p => p.X < east.X && p.Y > east.Y);

            foreach (Point p in southern)
            {
                Vector r = p - east;
                Vector s = new Vector(east.X, east.Y);

                double m = r.Y / r.X;
                double c = east.Y - (m * east.X);

                if (!southern.Any(a => Math.Round((a.X * m + c)) < a.Y))
                {
                    return p;
                }
            }

            return default(Point);
        }

        private Point GetNextPointSouth(Point south)
        {
            var western = points.Where(p => p.Y < south.Y && p.X < south.X);

            foreach (Point p in western)
            {
                Vector r = p - south;
                Vector s = new Vector(south.X, south.Y);

                double m = r.Y / r.X;
                double c = south.Y - (m * south.X);

                if (!western.Any(a => Math.Round((a.X * m + c)) < a.Y))
                {
                    return p;
                }
            }

            return default(Point);
        }

        private void buttonDrawConvex_Click(object sender, RoutedEventArgs e)
        {
            DrawConvexLine();
        }
    }
}


MainWindow.xaml
Quellcode ausblenden XML-Code
<Window x:Class="WpfKonvexeHuellkurve.MainWindow"
        xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
        xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
        xmlns:d="http://schemas.microsoft.com/expression/blend/2008"
        xmlns:mc="http://schemas.openxmlformats.org/markup-compatibility/2006"
        xmlns:local="clr-namespace:WpfKonvexeHuellkurve"
        mc:Ignorable="d"
        Title="MainWindow" Height="610" Width="755" ResizeMode="CanMinimize">
    <Grid>
        <Border BorderBrush="Black" BorderThickness="2" Width="504" Height="504" Margin="10,10,0,0" HorizontalAlignment="Left" VerticalAlignment="Top">
            <Canvas x:Name="canvasDraw" Background="#FF08F48E" Width="500" Height="500" Margin="0"/>
        </Border>
        <ListBox x:Name="listBoxPoints" Width="218" Height="504" Margin="519,10,0,0" HorizontalAlignment="Left" VerticalAlignment="Top"/>
        <Button x:Name="buttonDrawRandom" Content="Zufällige Punkte zeichnen" HorizontalAlignment="Left" Margin="10,548,0,0" VerticalAlignment="Top" Width="161" Click="buttonDrawRandom_Click"/>
        <TextBlock x:Name="textBlock" HorizontalAlignment="Left" Margin="10,522,0,0" TextWrapping="Wrap" Text="Anzahl" VerticalAlignment="Top"/>
        <TextBox x:Name="textBoxNumber" HorizontalAlignment="Left" Height="24" Margin="51,519,0,0" TextWrapping="Wrap" Text="20" VerticalAlignment="Top" Width="120" TextAlignment="Center"/>
        <Button x:Name="buttonDrawConvex" Content="Konvexe Hüllkurve zeichnen" HorizontalAlignment="Left" Margin="176,548,0,0" VerticalAlignment="Top" Width="172" Click="buttonDrawConvex_Click"/>


    </Grid>
</Window>
vote_ok
von hollst (6440 Punkte) - 10.05.2017 um 10:06 Uhr
Quellcode ausblenden C#-Code
using System;
using System.Collections.Generic;
using System.Text;
using System.Windows;
using System.Windows.Controls;
using System.Windows.Media;
using System.Windows.Shapes;

using System.Text.RegularExpressions;

namespace convex_line_of_point_set  {

    public partial class MainWindow : Window    {

        public static string NL = Environment.NewLine;

        public MainWindow() {
            InitializeComponent();
            this.MyCanvas.ClipToBounds = true;
            this.tb_anzahl.Text = anzahl_default.ToString();

            this.tb_1.Text = MyTestTool.test_CalcPolygonArea();
        }

        private point_set ps;
        private point_set.xyr[] line_points;

        private double rw = 8.0;
        private bool bo_data_available = false;
        private bool bo_more_info = false;

        private void draw_pointes(int i, point_set.xyr[] set)        {

            Rectangle myRect = new Rectangle();
            myRect.Width = rw; myRect.Height = rw;
            myRect.Fill = new SolidColorBrush(Colors.Blue);
            Canvas.SetLeft(myRect, set[i].x);
            Canvas.SetTop(myRect,  set[i].y);
            MyCanvas.Children.Add(myRect);
        }

        private void draw_lines(int i)        {
            Line line = new Line();
            line.Stroke = Brushes.Red;
            line.StrokeThickness = rw / 4;
            line.X1 = line_points[i].x + rw / 2;
            line.X2 = line_points[i + 1].x + rw / 2;
            line.Y1 = line_points[i].y + rw / 2;
            line.Y2 = line_points[i + 1].y + rw / 2;

            MyCanvas.Children.Add(line);

            Rectangle myRect = new Rectangle();
            myRect.Width = rw; myRect.Height = rw;
            myRect.Fill = new SolidColorBrush(Colors.Yellow);
            Canvas.SetLeft(myRect, line_points[i].x);
            Canvas.SetTop(myRect, line_points[i].y);
            MyCanvas.Children.Add(myRect);
        }

        private static uint anzahl_default = 50, anzahl = anzahl_default;

        private void bt_punkte_Click(object sender, RoutedEventArgs e)
        //create and draw point set
        {
            uint anzahl_out;
            if (!uint.TryParse(this.tb_anzahl.Text, out anzahl_out))
            {
                MessageBox.Show("no number in textbox");
                this.tb_anzahl.Text = anzahl_default.ToString();
                return;
            }
            else
                if (anzahl_out <= 0)
                    return;
                else
                    anzahl_default = anzahl_out;

            anzahl = anzahl_default;

            MyCanvas.Children.Clear();

            int bo_xy = 1;
            if ((bool)this.rb_rphi_zyl.IsChecked) bo_xy = 2;
            if ((bool)this.rb_rphi_euc.IsChecked) bo_xy = 3;

            int laenge = (int)(Math.Min(size_values[2], size_values[3]) - 2 * rw);
            ps = new point_set(anzahl: (int)anzahl, laenge: laenge, bo_xy: bo_xy);
            this.tb_1.Text = ps.point_set_as_string_org;

            point_set.xyr[] set = ps.set;


            line_points = new point_set.xyr[ps.linepoints + 1];
            for (var i = 0; i < set.Length; i++)
                if (set[i].rank != -1)
                    line_points[set[i].rank] = set[i];
            line_points[line_points.Length - 1] = line_points[0];

            
            for (var i = 0; i < set.Length; i++)
                draw_pointes(i, set);

            this.bo_data_available = true;
        }

        private void bt_clear_Click(object sender, RoutedEventArgs e)
        {
            this.MyCanvas.Children.Clear();
            this.tb_1.Clear();
            this.bo_data_available = false;
        }

        private void bt_run_Click(object sender, RoutedEventArgs e)
        //draw convex line in one step
        {
            if (!this.bo_data_available)
                return;
                   
            for (var i = 0; i < line_points.Length - 1; i++)
                draw_lines(i);

            double verhaeltnis = 1.0 * (line_points.Length - 1) / ps.set.Length;
            double verhaeltnis_p = 1.0 * (line_points.Length - 1) / (int)(Math.Min(size_values[2], size_values[3]));

            this.tb_1.Text = 
                (line_points.Length - 1).ToString("n0") + 
                NL + ps.set.Length.ToString("n0") + 
                NL + verhaeltnis.ToString("p2") + 

                NL + ps.area.ToString("n2") +
                
                NL + ps.point_set_as_string ;
        }

        private int bt_by_step_counter = 0;
        private void bt_by_step_Click(object sender, RoutedEventArgs e)
        //draw convex line step by step
        {
            if (!this.bo_data_available)
                return;

            draw_lines(bt_by_step_counter);
            this.tb_1.Text = ps.strings_step_by_step[bt_by_step_counter];

            bt_by_step_counter++;
            bt_by_step_counter = bt_by_step_counter % (line_points.Length - 1);
        }

        private double[] size_values;

        private void tb_anzahl_TextChanged(object sender, TextChangedEventArgs e)
        {
            TextBox a_textBox = (TextBox)sender;
            string a_newText = string.Empty;

            for (int i = 0; i < a_textBox.Text.Length; i++)
            {
                if (Regex.IsMatch(a_textBox.Text[i].ToString(), "[0-9]"))//  "^[a-zA-Z0-9-]+$"))
                {
                    a_newText += a_textBox.Text[i];
                }
            }

            a_textBox.Text = a_newText;
            a_textBox.SelectionStart = a_textBox.Text.Length;
        }

        private void main_window_SizeChanged(object sender, SizeChangedEventArgs e)        {

            double set_w = 0, set_h = 0, minx = -1, miny = -1, maxx = -1, maxy = -1;

            if(bo_data_available)            {

                double x0 = double.MaxValue, y0 = double.MaxValue, x1 = double.MinValue, y1 = double.MinValue;

                for(var i = 0; i < ps.set.Length; i++)  {

                    if (ps.set[i].x < x0) x0 = ps.set[i].x;
                    if (ps.set[i].y < y0) y0 = ps.set[i].y;
                    if (ps.set[i].x > x1) x1 = ps.set[i].x;
                    if (ps.set[i].y > y1) y1 = ps.set[i].y;
                }

                minx = x0; miny = y0; maxx = x1; maxy = y1;
                set_w = x1 - x0;
                set_h = y1 - y0;
            }

            this.size_values = new double[]             {
                this.main_window.ActualWidth, this.main_window.ActualHeight,
                this.MyCanvas.ActualWidth, this.MyCanvas.ActualHeight,
                this.main_border.ActualWidth, this.main_border.ActualHeight,
                set_w, set_h, minx, miny, maxx, maxy
            };

            if(bo_more_info)
                this.tb_1.Text = this.size_values.ToMyString(false);     
        }
    }

    public class point_set    {

        public class xyr
        {
            public double x;
            public double y;
            public int rank;
        }

        public string   point_set_as_string = String.Empty,
                        point_set_copy_as_string = String.Empty,
                        point_set_as_string_org = String.Empty;

        public xyr[] set, set_copy, set_temp;

        public List<string> strings_step_by_step = new List<string>();

        public int linepoints = 0;
        public double area = 0;

        private int most_south = -1;

        public point_set(int anzahl = 50, int laenge = 10, int bo_xy = 1)
        {
            this.set = new xyr[anzahl]; this.set_copy = new xyr[anzahl]; this.set_temp = new xyr[anzahl];

            Random rand = new Random();
            double dmost_south = double.MaxValue;

            for(var i= 0; i < this.set.Length; i++)
            {
                set[i] = new xyr();

                double x = 0, y = 0;

                if (bo_xy == 1)
                {
                    x = laenge * rand.NextDouble();
                    y = laenge * rand.NextDouble();
                }

                if (bo_xy == 2)
                {
                    double r = laenge * rand.NextDouble() / 2; ; double ph = 2.0 * Math.PI * rand.NextDouble();
                    y = r * Math.Sin(ph) + laenge / 2;
                    x = r * Math.Cos(ph) + laenge / 2;
                }

                if (bo_xy == 3) { 
                    bool bo_okay = false;
                    while (!bo_okay)
                    {
                        x = laenge * rand.NextDouble();
                        y = laenge * rand.NextDouble();
                        double lh = laenge / 2;
                        bo_okay = Math.Sqrt((x - lh) * (x - lh) + (y - lh) * (y - lh)) <= lh;
                    }
                }

                set[i].x = x;
                set[i].y = y;

                set[i].rank = -1;
                if (set[i].y < dmost_south)
                {
                    dmost_south = set[i].y;
                    this.most_south = i;
                }
            }

            this.point_set_as_string_org = set_as_string(set);

            set[most_south].rank = 0;

            this.strings_step_by_step.Add(set_as_string(set));

            this.copy_and_adjust(this.set, out this.set_copy, this.set[this.most_south], 0.0);

            double phi = 0.0;
            int counter = 1;

            while (true)    {
                int merker_i = -1;
                double phi_temp = double.MaxValue;
                for (var i = 0; i < this.set_copy.Length; i++)  {

                    if ((this.set_copy[i].rank < 1) && !((this.set_copy[i].y == 0) && (this.set_copy[i].x == 0)))   {
                        double phi_i = Math.Atan2(this.set_copy[i].y, this.set_copy[i].x);
                        if (phi_i < 0.0)
                            phi_i = 2.0 * Math.PI - Math.Abs(phi_i);

                        if (phi_i < phi_temp)   {
                            phi_temp = phi_i;
                            merker_i = i;
                        }
                    }
                }
                phi += phi_temp;
                if (phi > 2 * Math.PI)
                    break;

                if (this.set_copy[merker_i].rank != 0)  {
                    this.set_copy[merker_i].rank = counter;
                    this.set[merker_i].rank = counter;
                    this.strings_step_by_step.Add(set_as_string(set));
                }
                else
                    break;

                counter++;
                copy_and_adjust(this.set_copy, out this.set_copy, this.set_copy[merker_i], phi_temp);
            }

            for (var i = 0; i < this.set_copy.Length; i++)
                if (this.set[i].rank != -1)
                    linepoints++;

            double[] xp = new double[linepoints], yp = new double[linepoints];
            for (var i = 0; i < this.set_copy.Length; i++)
                if (this.set[i].rank != -1) {
                    xp[this.set[i].rank] = this.set[i].x;
                    yp[this.set[i].rank] = this.set[i].y;
                }

            this.area = MyTestTool.CalcPolygonArea(xp, yp);
            this.point_set_as_string = set_as_string(set);
        }

        private void copy_and_adjust(xyr[] from, out xyr[] to, xyr adjust, double w )
        {
            to = new xyr[from.Length];
            for (var i = 0; i < from.Length; i++)
            {
                to[i] = new xyr();
                to[i].x = from[i].x - adjust.x;
                to[i].y = from[i].y - adjust.y;
                to[i].rank = from[i].rank;
                to[i] = drehe(to[i], w);
            }
            point_set_copy_as_string = set_as_string(to);
        }

        private string set_as_string(xyr[] set)
        {
            StringBuilder sb = new StringBuilder();
            sb.AppendLine();
            for (var i = 0; i < this.set.Length; i++)
            {
                sb.Append(" [" + set[i].x.ToString("0.00") + "; ");
                sb.Append(set[i].y.ToString("0.00") + "] ");
                sb.AppendLine(set[i].rank.ToString());
            }            
            return sb.ToString();
        }

        private xyr drehe(xyr p, double w)
        {
            xyr result = new xyr();
            result.rank = p.rank;
            double cos = Math.Cos(w), sin = Math.Sin(w);
            result.x = p.x * cos + p.y * sin;
            result.y = p.y * cos - p.x * sin;
            return result;
        }
    }

    public static class MyTestTool    {

        public static string test_atan2()
        {
            String LZ = " ";
            StringBuilder sb = new StringBuilder();
            double[] x = new double[] { 1, 1, 0, -1, -1, -1,  0,  1,  1        };
            double[] y = new double[] { 0, 1, 1,  1,  0, -1, -1, -1, -0.000001 };
            for(var i = 0; i < y.Length; i++)
            {
                double phi = Math.Atan2(y[i], x[i]);
                if (phi < 0.0)
                    phi = 2.0 * Math.PI - Math.Abs(phi);
                sb.AppendLine(i.ToString() + LZ + phi.ToString("0.0000") + 
                    LZ + (180 * phi / Math.PI).ToString("0.00"));
            }
            return sb.ToString();
        }

        public static string ToMyString(this double[] x, bool bo_horizontal = true)
        {
            StringBuilder sb = new StringBuilder();
            string dir = " ";
            if (!bo_horizontal)
                dir = Environment.NewLine;
            for (var i = 0; i < x.Length; i++)
                sb.Append(x[i].ToString("0.0000") + dir);
            return sb.ToString();
        }

        public static double CalcPolygonArea(double[] x, double[] y)
        {
            if ((x == null) || (y == null)) return 0.0;  
            int n = Math.Min(x.Length, y.Length);        
            if (n < 3) return 0.0;                       
            double area = 0.0;                              
            for (int i = 0; i < n; i++)
                area += (y[i] + y[(i + 1) % n]) * (x[i] - x[(i + 1) % n]);
            return Math.Abs(area / 2.0);                    
        }

        public static string test_CalcPolygonArea()
        {            
            double[] y = new double[] { 0, 10, 10,  0, -10, 0 };
            double[] x = new double[] { 0, 10, 20, 20,  10, 0 };
            return CalcPolygonArea(x, y).ToString();
        }
    }
}


Quellcode ausblenden C#-Code
<Window x:Name="main_window" x:Class="convex_line_of_point_set.MainWindow"
        xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
        xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
        xmlns:d="http://schemas.microsoft.com/expression/blend/2008"
        xmlns:mc="http://schemas.openxmlformats.org/markup-compatibility/2006"
        xmlns:local="clr-namespace:convex_line_of_point_set"
        mc:Ignorable="d"
        Title="convex line" Height="555.419" Width="641.85" WindowStartupLocation="CenterScreen" Background="{DynamicResource {x:Static SystemColors.ActiveCaptionBrushKey}}" SizeChanged="main_window_SizeChanged" >
    <Grid Margin="0">
        <Grid.ColumnDefinitions>
            <ColumnDefinition/>
            <ColumnDefinition Width="150"/>
        </Grid.ColumnDefinitions>
        <Grid.RowDefinitions>
            <RowDefinition/>
            <RowDefinition Height="70"/>
        </Grid.RowDefinitions>
        <StackPanel Margin="5" Grid.Row="1" Orientation="Horizontal" Grid.ColumnSpan="3">
            <Button x:Name="bt_clear" Content=" clear canvas " Margin="5,0,0,0" Click="bt_clear_Click" VerticalAlignment="Top"/>
            <Button x:Name="bt_punkte" Content=" draw new points " Margin="5,0,0,0" Click="bt_punkte_Click" VerticalAlignment="Top"/>
            <Button x:Name="bt_run" Content=" draw connected convex line " Margin="5,0,0,0" Click="bt_run_Click" VerticalAlignment="Top"/>
            <Button x:Name="bt_by_step" Content=" step by step " Width="75" Click="bt_by_step_Click" VerticalAlignment="Top"/>
            <StackPanel VerticalAlignment="Center">
                <Label Content="0    1     2" Margin="0" HorizontalAlignment="Center" RenderTransformOrigin="0.5,0.5" ToolTip="xy(1) rphi_zyl(2) rph_euclid(3)" />
                <StackPanel Orientation="Horizontal">
                    <RadioButton x:Name="rb_xy" VerticalAlignment="Center" IsChecked="True" HorizontalAlignment="Center" Margin="5" />
                    <RadioButton x:Name="rb_rphi_zyl" HorizontalAlignment="Center" VerticalAlignment="Center" Margin="5"/>
                    <RadioButton x:Name="rb_rphi_euc" HorizontalAlignment="Center" VerticalAlignment="Center" Margin="5"/>
                </StackPanel>
            </StackPanel>

            <TextBox x:Name="tb_anzahl" TextWrapping="Wrap" Width="50" Margin="15,0,0,0" Text="50" TextChanged="tb_anzahl_TextChanged" VerticalAlignment="Top"/>
        </StackPanel>
        <Border x:Name="main_border" BorderBrush="Black" BorderThickness="5" Margin="5,5,0,4">
            <Canvas x:Name="MyCanvas" Background="#FF11F58E"/>
        </Border>
        <TextBox x:Name="tb_1" Grid.Column="1" Margin="5" TextWrapping="Wrap" VerticalScrollBarVisibility="Auto" Background="Blue" Foreground="#FFE6E608" BorderThickness="1"/>
    </Grid>
</Window>

3 Kommentare
vote_ok
von KawaiiShox (280 Punkte) - 23.06.2017 um 12:09 Uhr
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 .


Quellcode ausblenden 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;
        }
    }