C# :: Aufgabe #176 :: Lösung #2

3 Lösungen Lösungen öffentlich
#176

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.
#2
vote_ok
von hollst (7810 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>

Kommentare:

Für diese Lösung gibt es noch keinen Kommentar

Bitte melden Sie sich an um eine Kommentar zu schreiben.
Kommentar schreiben