ウィキペディアの擬似コードからグラハム スキャンを実装しようとしていますが、物事を C# に変換する際に少し問題が発生しています。見ていただいてもよろしいでしょうか？
ここに私が持っているものがあります:
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);
}
}
そして、このクラスを利用しています：
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;
}
}
コードは爆発するのが好きです。主な理由は、すべてが異なる多数の疑似実装を読んだためであり、物事を十分に説明しているものはありません。配列の境界外エラーが発生しています。これは、coordinatesize、coordinatesize + 1、coordizesize - 1、coordizesize + killme のいずれであるかもわかりません。元は 'N' または 'N' でした。 +1' ですが、ご覧のとおり、私はこの翻訳についてゆっくりと気を失いつつあります。