将凹壳算法转换为c＃
所以我试图翻译这里的凹形船体算法： http ： //repositorium.sdum.uminho.pt/bitstream/1822/6429/1/ConcaveHull_ACM_MYS.pdf
（第65页）
我已经阅读了整个事情，但我无法弄清楚如何实现sortByAngle和angle ，我不知道我应该在它们内部做什么方法。 这是我到目前为止：
//Main method public static Vertex[] ConcaveHull(Vertex[] points, int k = 3) { if (k < 3) throw new ArgumentException("K is required to be 3 or more", "k"); List hull = new List(); //Clean first, may have lots of duplicates Vertex[] clean = RemoveDuplicates(points); if (clean.Length < 3) throw new ArgumentException("At least 3 dissimilar points reqired", "points"); if (clean.Length == 3)//This is the hull, its already as small as it can be. return clean; if (clean.Length 0)) { if (step == 5) dataset = Add(dataset, firstPoint); Vertex[] kNearestPoints = nearestPoints(dataset, currentPoint, k); Vertex[] cPoints = sortByAngle(kNearestPoints, currentPoint, previousAngle); bool its = true; i = 0; while ((its) && (i < cPoints.Length)) { i++; int lastPoint = 0; if (cPoints[0] == firstPoint) lastPoint = 1; int j = 2; its = false; while ((!its) && (j 0) { allInside = new Polygon(dataset).Contains(currentPoint); //TODO havent finished ray casting yet. i--; } if (!allInside) return ConcaveHull(points, k + 1); return hull.ToArray(); } private static Vertex[] Add(Vertex[] vs, Vertex v) { List n = new List(vs); n.Add(v); return n.ToArray(); } private static Vertex[] RemoveIndex(Vertex[] vs, int index) { List removed = new List(); for (int i = 0; i < vs.Length; i++) if (i != index) removed.Add(vs[i]); return removed.ToArray(); } private static Vertex[] RemoveDuplicates(Vertex[] vs) { List clean = new List(); VertexComparer vc = new VertexComparer(); foreach (Vertex v in vs) { if (!clean.Contains(v, vc)) clean.Add(v); } return clean.ToArray(); } private static Vertex[] nearestPoints(Vertex[] vs, Vertex v, int k) { Dictionary lengths = new Dictionary(); List n = new List(); double[] sorted = lengths.Keys.OrderBy(d => d).ToArray(); for (int i = 0; i = x2) { if (!(x2 <= x && x <= x1)) { return false; } } else { if (!(x1 <= x && x = y2) { if (!(y2 <= y && y <= y1)) { return false; } } else { if (!(y1 <= y && y = x4) { if (!(x4 <= x && x <= x3)) { return false; } } else { if (!(x3 <= x && x = y4) { if (!(y4 <= y && y <= y3)) { return false; } } else { if (!(y3 <= y && y <= y4)) { return false; } } } return true; } private static double angle(Vertex v1, Vertex v2) { // TODO fix Vertex v3 = new Vertex(v1.X, 0); if (Orientation(v3, v1, v2) == 0) return 180; double b = EuclideanDistance(v3, v1); double a = EuclideanDistance(v1, v2); double c = EuclideanDistance(v3, v2); double angle = Math.Acos((Math.Pow(a, 2) + Math.Pow(b, 2) - Math.Pow(c, 2)) / (2 * a * b)); if (Orientation(v3, v1, v2) 0) return -1;//Left if (Orin < 0) return 1;//Right return 0;//Colinier }
我知道这里有很多代码。 但是我不确定我是否可以展示上下文以及没有它的情况。
其他课程：
public class Polygon { private Vertex[] vs; public Polygon(Vertex[] Vertexes) { vs = Vertexes; } public Polygon(Bounds bounds) { vs = bounds.ToArray(); } public Vertex[] ToArray() { return vs; } public IEnumerable Edges() { if (vs.Length > 1) { Vertex P = vs[0]; for (int i = 1; i < vs.Length; i++) { yield return new Edge(P, vs[i]); P = vs[i]; } yield return new Edge(P, vs[0]); } } public bool Contains(Vertex v) { return RayCasting.RayCast(this, v); } } public class Edge { public Vertex A = new Vertex(0, 0); public Vertex B = new Vertex(0, 0); public Edge() { } public Edge(Vertex a, Vertex b) { A = a; B = b; } public Edge(double ax, double ay, double bx, double by) { A = new Vertex(ax, ay); B = new Vertex(bx, by); } } public class Bounds { public Vertex TopLeft; public Vertex TopRight; public Vertex BottomLeft; public Vertex BottomRight; public Bounds() { } public Bounds(Vertex TL, Vertex TR, Vertex BL, Vertex BR) { TopLeft = TL; TopRight = TR; BottomLeft = BL; BottomRight = BR; } public Vertex[] ToArray() { return new Vertex[] { TopLeft, TopRight, BottomRight, BottomLeft }; } } public class Vertex { public double X = 0; public double Y = 0; public Vertex() { } public Vertex(double x, double y) { X = x; Y = y; } public static Vertex[] Convert(string vs) { vs = vs.Replace("[", ""); vs = vs.Replace("]", ""); string[] spl = vs.Split(';'); List nvs = new List(); foreach (string s in spl) { try { nvs.Add(new Vertex(s)); } catch { } } return nvs.ToArray(); } public static string Stringify(Vertex[] vs) { string res = "["; foreach (Vertex v in vs) { res += v.ToString(); res += ";"; } res = res.RemoveLastCharacter(); res += "]"; return res; } public static string ToString(Vertex[] array) { string res = "["; foreach (Vertex v in array) res += v.ToString() + ","; return res.RemoveLastCharacter() + "]"; } /* //When x y return 1 public static int Compare(Vertex x, Vertex y) { //To find lowest if (xX < yX) { return -1; } else if (xX == yX) { if (xY < yY) { return -1; } else if (xY == yY) { return 0; } else { return 1; } } else { return 1; } } */ public static int CompareY(Vertex a, Vertex b) { if (aY < bY) return -1; if (aY == bY) return 0; return 1; } public static int CompareX(Vertex a, Vertex b) { if (aX < bX) return -1; if (aX == bX) return 0; return 1; } public double distance (Vertex b){ double dX = bX - this.X; double dY = bY - this.Y; return Math.Sqrt((dX*dX) + (dY*dY)); } public double slope (Vertex b){ double dX = bX - this.X; double dY = bY - this.Y; return dY / dX; } public static int Compare(Vertex u, Vertex a, Vertex b) { if (aX == bX && aY == bY) return 0; Vertex upper = new Vertex(); Vertex p1 = new Vertex(); Vertex p2 = new Vertex(); upper.X = (uX + 180) * 360; upper.Y = (uY + 90) * 180; p1.X = (aX + 180) * 360; p1.Y = (aY + 90) * 180; p2.X = (bX + 180) * 360; p2.Y = (bY + 90) * 180; if(p1 == upper) return -1; if(p2 == upper) return 1; double m1 = upper.slope(p1); double m2 = upper.slope(p2); if (m1 == m2) { return p1.distance(upper) < p2.distance(upper) ? -1 : 1; } if (m1 0) return -1; if (m1 > 0 && m2 m2 ? -1 : 1; } public static Vertex UpperLeft(Vertex[] vs) { Vertex top = vs[0]; for (int i = 1; i top.Y || (temp.Y == top.Y && temp.X < top.X)) { top = temp; } } return top; } }
只是关于约定的注释：你应该用大写开始函数名，用小写开始变量。 在函数sortByAngle ，您可以同时参考参数angle和函数angle 。
假设Angle(...)仅用于计算两点之间的角度：
private static double Angle(Vertex v1, Vertex v2) { return Math.Atan2(v2.Y - v1.Y, v2.X - v1.X); }
将给出从v1到v2的角度，以-pi和+ pi之间的弧度表示。 不要混合度和弧度。 我的建议是始终使用弧度，并且只有在必要时才转换为人类可读输出的度数。
private static Vertex[] SortByAngle(Vertex[] vs, Vertex v, double angle) { List vertList = new List (vs); vertList.Sort((v1, v2) => AngleDifference(angle, Angle(v, v1)).CompareTo(AngleDifference(angle, Angle(v, v2)))); return vertList.ToArray(); }
使用List.Sort从顶点和自身以及angle之间的最大角度差到最小角度差来对顶点进行排序。 v1和v2的顺序在输入元组中交换以降序排序，即最大差异。 角度之间的差异计算如下：
private static double AngleDifference(double a, double b) { while (a < b - Math.PI) a += Math.PI * 2; while (b < a - Math.PI) b += Math.PI * 2; return Math.Abs(a - b); }
前两行确保角度相差不超过180度。
你有错误
private static Vertex[] nearestPoints(Vertex[] vs, Vertex v, int k) { Dictionary lengths = new Dictionary(); List n = new List (); double[] sorted = lengths.Keys.OrderBy(d => d).ToArray(); for (int i = 0; i < k; i++) { n.Add(lengths[sorted[i]]); } return n.ToArray(); }
根据代码，如果你有几个相同距离的顶点，函数只返回一个。 由于Dictionary使用唯一键。
顺便说一下，有没有人完成这个？
我现在没有时间阅读这篇论文，但是根据我对conVEX船体算法的了解，我假设您正在寻找下一个要连接的点的特定方向的点。
如果是这种情况，“角度”将是船体最近的线段的角度，并且您希望按照它们与该线的角度对点进行排序。 因此，您需要计算线（在船体上）和一组线（从当前点到正在考虑的每个其他点）之间的角度。 计算的角度是正还是负取决于您是顺时针还是逆时针。 要计算角度，请查看以下内容：
计算两条线之间的角度而不必计算斜率？ （JAVA）
然后按角度排序。
那个怎么样？
private List sortClockwiseFromCentroid(List points, Vector center) { points = points.OrderBy(x => Math.Atan2(xX - center.X, xY - center.Y)).ToList(); return points; }