0
我試圖從維基百科僞代碼實施格雷厄姆掃描，並且遇到了將事情轉化爲C＃的一些麻煩。也許你不介意看看？在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;
}
}
代碼喜歡爆炸，主要是因爲我讀過一打僞實現，都不同的，沒有任何解釋過於充分的東西。我得到了一個數組越界的錯誤，我甚至不知道應該是座標系，座標系+1還是座標系-1，或座標系+ killme->原來是'N'或'N +1「，但正如你所看到的，我正在慢慢失去對這種翻譯的想法。
你能告訴我它在哪裏爆炸嗎？ – doctorlove
您是否嘗試過[this]（http://my-bsc-thesis.googlecode.com/svn/trunk/KinectFingerDetection/KinectControl.Core/Detection/GrahamScan.cs）？ –
目前它在'coordinatesarray [0] = coordinatesarray [coordinatesize];'上爆炸行索引超出範圍異常（它應該，因爲它顯然訪問數組外）。我遇到的問題的一部分是翻譯此代碼：「讓N =點數」和「讓點[N + 1] =點數組......」就像他們使用的是基於0的數據，然後是1有時索引。 – user978122