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

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.
#3
3 Kommentare
vote_ok
von KawaiiShox (330 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;
        }
    }
    


Kommentare:

hollst

Punkte: 9460

491 Aufgaben
93 Lösungen
85 Kommentare

#1
26.06.2017 um 20:18 Uhr
Hallo,

bitte auch noch den Designer.cs-File posten, sonst lässt das Ganze ja nicht nachvollziehen,

Gruß, hollst!
post_arrow
454 0

KawaiiShox

Punkte: 330

1 Aufgaben
6 Lösungen
1 Kommentare

#2
27.06.2017 um 09:49 Uhr
Wie gewünscht hier noch die Designer.cs:
Quellcode ausblenden C#-Code
namespace WindowsFormsApplication1
{
    partial class Form1
    {
        /// <summary>
        /// Erforderliche Designervariable.
        /// </summary>
        private System.ComponentModel.IContainer components = null;

        /// <summary>
        /// Verwendete Ressourcen bereinigen.
        /// </summary>
        /// <param name="disposing">True, wenn verwaltete Ressourcen gelöscht werden sollen; andernfalls False.</param>
        protected override void Dispose(bool disposing)
        {
            if (disposing && (components != null))
            {
                components.Dispose();
            }
            base.Dispose(disposing);
        }

        #region Vom Windows Form-Designer generierter Code

        /// <summary>
        /// Erforderliche Methode für die Designerunterstützung.
        /// Der Inhalt der Methode darf nicht mit dem Code-Editor geändert werden.
        /// </summary>
        private void InitializeComponent()
        {
            this.components = new System.ComponentModel.Container();
            this.panel1 = new System.Windows.Forms.Panel();
            this.button1 = new System.Windows.Forms.Button();
            this.timer1 = new System.Windows.Forms.Timer(this.components);
            this.button2 = new System.Windows.Forms.Button();
            this.listBox1 = new System.Windows.Forms.ListBox();
            this.SuspendLayout();
            // 
            // panel1
            // 
            this.panel1.BorderStyle = System.Windows.Forms.BorderStyle.FixedSingle;
            this.panel1.Location = new System.Drawing.Point(13, 13);
            this.panel1.Name = "panel1";
            this.panel1.Size = new System.Drawing.Size(259, 236);
            this.panel1.TabIndex = 0;
            // 
            // button1
            // 
            this.button1.Location = new System.Drawing.Point(12, 265);
            this.button1.Name = "button1";
            this.button1.Size = new System.Drawing.Size(145, 23);
            this.button1.TabIndex = 1;
            this.button1.Text = "Punkte einzeichnen";
            this.button1.UseVisualStyleBackColor = true;
            this.button1.Click += new System.EventHandler(this.button1_Click);
            // 
            // timer1
            // 
            this.timer1.Interval = 10;
            this.timer1.Tick += new System.EventHandler(this.timer1_Tick);
            // 
            // button2
            // 
            this.button2.Location = new System.Drawing.Point(12, 294);
            this.button2.Name = "button2";
            this.button2.Size = new System.Drawing.Size(145, 23);
            this.button2.TabIndex = 2;
            this.button2.Text = "Hülle einzeichen";
            this.button2.UseVisualStyleBackColor = true;
            this.button2.Click += new System.EventHandler(this.button2_Click);
            // 
            // listBox1
            // 
            this.listBox1.FormattingEnabled = true;
            this.listBox1.Location = new System.Drawing.Point(311, 13);
            this.listBox1.Name = "listBox1";
            this.listBox1.Size = new System.Drawing.Size(190, 238);
            this.listBox1.TabIndex = 3;
            // 
            // Form1
            // 
            this.AutoScaleDimensions = new System.Drawing.SizeF(6F, 13F);
            this.AutoScaleMode = System.Windows.Forms.AutoScaleMode.Font;
            this.ClientSize = new System.Drawing.Size(513, 323);
            this.Controls.Add(this.listBox1);
            this.Controls.Add(this.button2);
            this.Controls.Add(this.button1);
            this.Controls.Add(this.panel1);
            this.Name = "Form1";
            this.Text = "Form1";
            this.Load += new System.EventHandler(this.Form1_Load);
            this.ResumeLayout(false);

        }

        #endregion

        private System.Windows.Forms.Panel panel1;
        private System.Windows.Forms.Button button1;
        private System.Windows.Forms.Timer timer1;
        private System.Windows.Forms.Button button2;
        private System.Windows.Forms.ListBox listBox1;
    }
}


post_arrow
457 0

hollst

Punkte: 9460

491 Aufgaben
93 Lösungen
85 Kommentare

#3
27.06.2017 um 10:44 Uhr
Hallo,

gut, bekommt man jetzt zum Laufen, wenn man noch das

this.timer1.Tick Event hinzufügt.

Bitte noch Zeile 42

Quellcode ausblenden C#-Code
Random r = new Random();


vor die for-Schleife ziehen, sonst werden die Zufallszahlen ziemlich unzufällig.

Gruß hollst
post_arrow
458 0
Bitte melden Sie sich an um eine Kommentar zu schreiben.
Kommentar schreiben