3
\$\begingroup\$

This is my "naive" implementation of a convex hull algorithm. By naive I mean that I am not using any of the advanced algorithms that exist to solve this problem.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Drawing;
using System.Linq;

namespace SO
{
    static class Extensions
    {
        public static IEnumerable<Point> GetConvexEnvelope(this IEnumerable<Point> points)
        {
            if (points == null)
                throw new ArgumentNullException("points");

            var pointsList = points.ToList();

            if (pointsList.Count < 4)
                return pointsList;

            var envelope = new Stack<Point>();

            //Any point with minimum X is, by definition, part of the envelope so we pick the first one we find.
            envelope.Push(pointsList.OrderBy(p => p.X).First());


            //Two valid consecutive envelope points will define a ray that has all remaining points of the set on only one side or are collinear.
            //We find new envelope points simply checking rays from last identified envelope point to remaining non envelope points.
            //We add the first valid ray's end point to the envelope and continue from there.
            //Ordering valid rays by length is necessary to avoid skipping collinear envelope points. Cost should be low as typically collinear points will be scarce.
            //If no valid ray is found we are done.
            while (true)
            {
                var rays = (from ray in
                                (from second in pointsList.Except(envelope)
                                 select new Ray(envelope.Peek(), second))
                            let possibleEndPoints = pointsList.Except(new Point[] { ray.Start, ray.End })
                            where possibleEndPoints.All(p => ray.GetProjectionSign(p) >= 0) ||
                                  possibleEndPoints.All(p => ray.GetProjectionSign(p) <= 0)
                            select ray).OrderBy(r => r.LengthSquared).ToList();

                if (rays.Count > 0)
                {
                    envelope.Push(rays[0].End);
                }
                else
                {
                    break;
                }
            }

            return envelope;
        }

        private struct Ray
        {
            private readonly double slope;

            public Point Start { get; private set; }
            public Point End { get; private set; }
            public double LengthSquared { get { return Math.Pow(End.Y - Start.Y, 2) + Math.Pow(End.X - Start.X, 2); } } //No need evaluating true length for ordering purposes.

            public Ray(Point start, Point end)
                : this()
            {
                Debug.Assert(end != start, "Specified points must not be equal.");

                Start = start;
                End = end;
                slope = (double)(End.Y - Start.Y) / (End.X - Start.X);
            }

            public int GetProjectionSign(Point p)
            {
                return Start.X == End.X ? Math.Sign(p.X - Start.X) : Math.Sign(p.Y - Start.Y - slope * (p.X - Start.X));

            }
        }
    }
}

Without changing the nature of the algorithm, I'd appreciate any optimizations in the code. I am pretty new to System.Linq and I'm not sure of all the performance implications when using language integrated queries so any guidelines or advice will be greatly appreciated.

I do not have any performance goals in mind. I'm mainly interested in optimizing the code and learn in the process.

Here is a quickly built windows forms to visually test the algorithm:

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Drawing;
using System.Drawing.Drawing2D;
using System.Linq;
using System.Windows.Forms;

namespace SO
{
    public partial class Main : Form
    {
        public Main(Func<Rectangle, IEnumerable<Point>> randomPointCollectionCreator)
        {
            Debug.Assert(randomPointCollectionCreator!=null);
            InitializeComponent();
            pointCollectionCreator = randomPointCollectionCreator;
        }

        private readonly Func<Rectangle, IEnumerable<Point>> pointCollectionCreator;
        private IEnumerable<Point> points;
        private Point[] envelope; 

        protected override void OnPaint(PaintEventArgs e)
        {
            base.OnPaint(e);

            if (points != null)
            {
                using (var pen = new Pen(Color.Red))
                {
                    foreach (var point in points)
                    {
                        e.Graphics.DrawEllipse(pen, point.X - 2, point.Y - 2, 4, 4);
                    }

                    if (envelope != null)
                    {
                        var path = new GraphicsPath();
                        path.AddLines(envelope);
                        path.CloseFigure();
                        e.Graphics.DrawPath(pen, path);
                    }
                }
            }
        }

        private void Main_Click(object sender, EventArgs e)
        {
            var bounds = ClientRectangle;
            bounds.Inflate(-50, -50);
            points = pointCollectionCreator(bounds);
            envelope = points.GetConvexEnvelope().ToArray();
            this.Invalidate(this.ClientRectangle);
        }       
    }

    partial class Main
    {
        /// <summary>
        /// Required designer variable.
        /// </summary>
        private System.ComponentModel.IContainer components = null;

        /// <summary>
        /// Clean up any resources being used.
        /// </summary>
        /// <param name="disposing">true if managed resources should be disposed; otherwise, false.</param>
        protected override void Dispose(bool disposing)
        {
            if (disposing && (components != null))
            {
                components.Dispose();
            }
            base.Dispose(disposing);
        }

        #region Windows Form Designer generated code

        /// <summary>
        /// Required method for Designer support - do not modify
        /// the contents of this method with the code editor.
        /// </summary>
        private void InitializeComponent()
        {
            this.SuspendLayout();
            // 
            // Main
            // 
            this.AutoScaleDimensions = new System.Drawing.SizeF(6F, 13F);
            this.AutoScaleMode = System.Windows.Forms.AutoScaleMode.Font;
            this.ClientSize = new System.Drawing.Size(780, 558);
            this.FormBorderStyle = System.Windows.Forms.FormBorderStyle.Fixed3D;
            this.Name = "Main";
            this.Text = "Main";
            this.Click += new System.EventHandler(this.Main_Click);
            this.ResumeLayout(false);

        }

        #endregion
    }
}

And to start it up:

namespace SO
{
    static class Program
    {
        public static void Main()
        {
            Func<Rectangle, IEnumerable<Point>> pointCreator =
                (Rectangle bounds) =>
                {
                    int counter = 0;
                    int maxCounter = 600;

                    var r = new Random();
                    var points = new List<Point>(maxCounter);
                    int rangeX = bounds.Right - bounds.Left;
                    int rangeY = bounds.Bottom - bounds.Top;

                    while (true)
                    {
                        if (counter == maxCounter)
                            return points;

                        points.Add(new Point(bounds.Left + r.Next(0, rangeX + 1), bounds.Top + r.Next(0, rangeY + 1)));
                        counter++;
                    }
                };

            var main = new Main(pointCreator);
            main.ShowDialog();
        }
    }
}
\$\endgroup\$
1
\$\begingroup\$
            var pointsList = points.ToList();

What is pointsList used for? I see:

            if (pointsList.Count < 4)
                return pointsList;
            envelope.Push(pointsList.OrderBy(p => p.X).First());
                                (from second in pointsList.Except(envelope)
                                 select new Ray(envelope.Peek(), second))
                            let possibleEndPoints = pointsList.Except(new Point[] { ray.Start, ray.End })

In my opinion it shouldn't be a list at all, but an ISet<Point> from which the main loop removes used points. In the worst case that would be a significant performance improvement over the first pointsList.Except. A small subtlety would be in the sign test, which would then have to use points instead of possibleEndPoints.


            //Any point with minimum X is, by definition, part of the envelope so we pick the first one we find.
            envelope.Push(pointsList.OrderBy(p => p.X).First());

Yes-ish. The main loop takes into account collinear points: it wouldn't be too hard to do so here as well.


                var rays = (from ray in
                                (from second in pointsList.Except(envelope)
                                 select new Ray(envelope.Peek(), second))
                            let possibleEndPoints = pointsList.Except(new Point[] { ray.Start, ray.End })
                            where possibleEndPoints.All(p => ray.GetProjectionSign(p) >= 0) ||
                                  possibleEndPoints.All(p => ray.GetProjectionSign(p) <= 0)
                            select ray).OrderBy(r => r.LengthSquared).ToList();

                if (rays.Count > 0)
                {
                    envelope.Push(rays[0].End);
                }
                else
                {
                    break;
                }

Why call ToList()? Here it probably doesn't make much difference, because OrderBy is greedy, but in general it's better Linq style to use First() or FirstOrDefault() rather than ToList()[0].

\$\endgroup\$
0
\$\begingroup\$

this is not a definitive answer but reading your code, the following comes to mind :

I bet that Math.Pow(x,2) is less efficient than x * x ...

public double LengthSquared { get { return Math.Pow(End.Y - Start.Y, 2) + Math.Pow(End.X - Start.X, 2); } }

and regarding

possibleEndPoints.All(p => ray.GetProjectionSign(p) >= 0) || possibleEndPoints.All(p => ray.GetProjectionSign(p) <= 0)

I suggest to invert the conditions to something like

.Any(p => ray.GetProjectionSign(p) >0) &&  ...

Checking for one item to fullfill a condition should be faster than checking for all items.

Hope this helps !

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.