I'm trying to implement a Graham Scan from the Wikipedia pseudo-code, and am running into a little trouble translating things into C#. Perhaps you wouldn't mind taking a look?
Here's what I have:
public class GrahamScan
{
public static List<CoordinatesD> Scan(List<CoordinatesD> coordinateslist)
{
int coordinatesize = coordinateslist.Count;
CoordinatesD[] coordinatesarray = new CoordinatesD[coordinatesize];
for (int i = 0; i < coordinatesize; i++)
{
coordinatesarray[i] = coordinateslist[i];
}
//swap points[1] with the point with the lowest y-coordinate;
int lowestyindex = LowestY(coordinatesarray);
Swap(coordinatesarray[0], coordinatesarray[lowestyindex]);
//sort points by polar angle with points[1];
coordinatesarray = SortByPolarAngle(coordinatesarray[0], coordinateslist);
// We want points[0] to be a sentinel point that will stop the loop.
coordinatesarray[0] = coordinatesarray[coordinatesize];
// M will denote the number of points on the convex hull.
int numpointsonhull = 1;
for (int i = 2; i < coordinatesize; i++)
{
// Find next valid point on convex hull.
while(CCW(coordinatesarray[numpointsonhull-1], coordinatesarray[numpointsonhull], coordinatesarray[i]) <= 0)
{
if(numpointsonhull > 1)
{
numpointsonhull -= 1;
}
// All points are collinear
else if (i == coordinatesize)
{
break;
}
else
{
i += 1;
}
}
// Update M and swap points[i] to the correct place.
numpointsonhull += 1;
//swap(points[M],points[i]);
Swap(coordinatesarray[numpointsonhull], coordinatesarray[i]);
}
List<CoordinatesD> pointsonhulllist = new List<CoordinatesD>();
for (int i = 0; i < numpointsonhull; i++)
{
pointsonhulllist.Add(coordinatesarray[i]);
}
return pointsonhulllist;
}
/// <summary>
/// Swaps two points.
/// </summary>
/// <param name="p1"></param>
/// <param name="p2"></param>
private static void Swap(CoordinatesD p1, CoordinatesD p2)
{
CoordinatesD temp = p1;
p1 = p2;
p2 = temp;
}
/// <summary>
/// Attempts to Sort by Polar Angle, with respect to p1.
/// </summary>
/// <param name="p1"></param>
/// <param name="points"></param>
/// <returns></returns>
private static CoordinatesD[] SortByPolarAngle(CoordinatesD p1, List<CoordinatesD> points)
{
CoordinatesD[] sortedpoints = new CoordinatesD[points.Count];
int sortedpointiterator = 0;
while(true)
{
int current = 0;
for (int i = 0; i < points.Count; i++)
{
if (p1.PolarAngle - points[i].PolarAngle < p1.PolarAngle - points[current].PolarAngle)
{
current = i;
}
}
sortedpoints[sortedpointiterator] = points[current];
sortedpointiterator++;
points.RemoveAt(current);
if (points.Count == 0)
{
break;
}
}
return sortedpoints;
}
/// <summary>
/// Finds the index of the CoordinateD with the lowest Y.
/// </summary>
/// <param name="coords"></param>
/// <returns></returns>
private static int LowestY(CoordinatesD[] coords)
{
int index = 0;
for (int i = 0; i < coords.Length; i++)
{
if(coords[i].Y < coords[index].Y)
{
index = i;
}
}
return index;
}
// Three points are a counter-clockwise turn if ccw > 0, clockwise if
// ccw < 0, and collinear if ccw = 0 because ccw is a determinant that
// gives the signed area of the triangle formed by p1, p2 and p3.
private static double CCW(CoordinatesD p1, CoordinatesD p2, CoordinatesD p3)
{
return (p2.X - p1.X) * (p3.Y - p1.Y) - (p2.Y - p1.Y) * (p3.X - p1.X);
}
}
And it's making use of this class:
public class CoordinatesD : iCoordinates
{
private double latitude = 0.0;
private double longitude = 0.0;
public enum ServiceType { Google = 0, Bing = 1 };
public double Latitude
{
get { return latitude; }
}
public double Longitude
{
get { return longitude; }
}
public double X
{
get { return longitude; }
}
public double Y
{
get { return latitude; }
}
public double PolarAngle { get { return CalculatePolarAngle(); } }
public CoordinatesD(double latitude, double longitude)
{
this.latitude = latitude;
this.longitude = longitude;
}
private double CalculatePolarAngle()
{
double polarangle = Math.Atan(latitude / longitude);
if (polarangle > 0.0)
{
return polarangle;
}
return polarangle + Math.PI;
}
public CoordinatesD Change(double changelat, double changelong)
{
CoordinatesD newCoordinates = new CoordinatesD(this.latitude + changelat, this.longitude + changelong);
return newCoordinates;
}
public string ToJScriptString(ServiceType service)
{
string jscriptstring = string.Empty;
switch (service)
{
case ServiceType.Bing:
jscriptstring = String.Format("new Microsoft.Maps.Location({0},{1})", this.latitude.ToString(), this.longitude.ToString());
break;
case ServiceType.Google:
jscriptstring = String.Format("new google.maps.LatLng({0},{1})", this.latitude.ToString(), this.longitude.ToString());
break;
default:
break;
}
return jscriptstring;
}
}
The code likes to explode, mostly because I've read a dozen pseudo implementations that are all different, and none which explain things too adequately. I'm getting an out of bounds error for the array, which, I'm not even sure should be coordinatesize, or coordinatesize + 1, or coordinatesize - 1, or coordinatesize + killme -> originally it was 'N' or 'N+1', but as you can see, I'm slowly losing my mind of this translation.
This question may well be dead, however it showed up in StackOverflow's "Related" questions, because I added a c# implementation of Graham's scan here: Graham scan issue at high amount of points. The Wikipedia algorithm does in fact have bugs in case of points collinear with each other and the starting minimum point.