# Convex envelope algorithm of random set of points

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
{

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 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.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();
}
}
}


            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].

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 !