翻译凹壳算法到C＃ [英] Translating concave hull algorithm to c#
本文介绍了翻译凹壳算法到C＃的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
所以，我想在这里翻译找到了凹壳的algorith： HTTP：/ /repositorium.sdum.uminho.pt/bitstream/1822/6429/1/ConcaveHull_ACM_MYS.pdf
（第65页）
香港专业教育学院通过整个事情读，但我无法弄清楚如何实施 sortByAngle 和角度，即时通讯不肯定我应该将其内部做什么方法。这是我到目前为止有：
//主要方法
公共静态顶点[] ConcaveHull（顶点[]分，INT K = 3）
{
如果（K 3;）
抛出新的ArgumentException（K需要为3个或更多，K）;
名单，LT;顶点>船体=新的List<&顶点GT;（）;
//清洁第一，可能有很多重复的
顶点[] =干净RemoveDuplicates（点）;
如果（clean.Length 3;）
抛出新的ArgumentException（至少有3点不同reqired，分）;
如果（clean.Length == 3）//这是船体，其已经小，因为它可以。
返回干净;
如果（clean.Length&所述K）
抛出新的ArgumentException（K必须等于或小于接着相异点的量，点）;
顶点firstPoint =清洁[0]; // TODO找到中间点
hull.Add（firstPoint）;
顶点currentPoint = firstPoint;
顶点[]数据集= RemoveIndex（清洁，0）;
双previousAngle = 0;
INT步= 2;
INT I;
而（（（currentPoint = firstPoint）||（步骤== 2））及！及（dataset.Length大于0））
{
如果（步骤== 5 ）
=数据添加（数据集，firstPoint）;
顶点[] = kNearestPoints nearestPoints（数据集，currentPoint，K）;
顶点[] = cPoints sortByAngle（kNearestPoints，currentPoint，previousAngle）;
布尔其= TRUE;
I = 0;
，而（（ITS）及及（I< cPoints.Length））
{
I ++;
INT lastPoint = 0;
如果（cPoints [0] == firstPoint）
lastPoint = 1;
INT J = 2;
=的虚假;
，而（！（它的）及及（J< hull.Count - lastPoint））
{
它= intersectsQ（船体[一步 - 1 - 1]，cPoints [0 ]，船体[一步 - 我 - J - 1]，船体[一步 - J - 1]）;
J ++;
}
}
如果（ITS）
{
返回ConcaveHull（点，K + 1）;
}
currentPoint = cPoints [0];
hull.Add（currentPoint）;
previousAngle =角度（船体[一步 - 1]，船体[一步 - 2]）;
数据= RemoveIndex（数据集，0）;
步骤++;
}
布尔allInside = TRUE;
I = dataset.Length;
，而（allInside&安培;&安培; I&0）
{
allInside =新的多边形（集）。载有（currentPoint）; // TODO还没有完成的光线投射呢。
我 - ;
}
如果（！allInside）
返回ConcaveHull（点，K + 1）;
返回hull.ToArray（）;
}
私有静态顶点[]添加（顶点[] VS，顶点v）
{
名单，LT;顶点> N =新的List<&顶点GT;（VS）;
n.Add（五）;
返回n.ToArray（）;
}
私有静态顶点[] RemoveIndex（顶点[] VS，INT指数）
{
名单，LT;顶点>删除=新的List<&顶点GT;（）;
的for（int i = 0; I< vs.Length;我++）
如果（I =指数！）
removed.Add（VS [I]）;
返回removed.ToArray（）;
}
私有静态顶点[] RemoveDuplicates（顶点[] VS）
{
名单，LT;顶点>干净=新的List<&顶点GT;（）;
VertexComparer VC =新VertexComparer（）;
的foreach（在VS顶点v）
{
如果
clean.Add（V）（clean.Contains（V，VC）！）;
}
返回clean.ToArray（）;
}
私有静态顶点[] nearestPoints（顶点[] VS，顶点v，INT K）
{
字典<双，顶点>长度=新词典<双，顶点>（）;
名单，LT;顶点> N =新的List<&顶点GT;（）;
双击[] =排序lengths.Keys.OrderBy（D => D）.ToArray（）;
的for（int i = 0; I< k;我++）
{
n.Add（长度[排列[I]）;
}
返回n.ToArray（）;
}
私有静态顶点[] sortByAngle（顶点[] VS，顶点v，双角）
{
// TODO
返回新顶点[] {};
}
私人静态布尔intersectsQ（顶点V1，顶点V2，顶点V3，顶点V4）
{
返回intersectsQ（新边缘（V1，V2）新的边缘（V3，V4））;
}
私人静态布尔intersectsQ（沿E1，E2边）
{
双X1 = e1.A.X;
双X2 = e1.B.X;
双X3 = e2.A.X;
双X4 = e2.B.X;
双Y1 = e1.A.Y;
双Y2 = e1.B.Y;
双Y3 = e2.A.Y;
双Y4 = e2.B.Y;
变种X =（（X1 * Y2 - Y1 * X2）*（×3 - ×4） - （X1 - ×2）*（×3 * Y4 - Y3 *×4））/（（X1 - X2 ）*（Y3 - Y4） - （Y1 - Y2）*（X3 - X4））;
变种Y =（（X1 * Y2 - Y1 * X2）*（Y3 - Y4） - （Y1 - Y2）*（×3 * Y4 - Y3 *×4））/（（X1 - ×2）*（Y3 - Y4） - （Y1 - Y2）*（X3 - X4））;
如果（double.IsNaN（X）|| double.IsNaN（y））为
{
返回false;
}
，否则
{
如果（X1> = X2）
{
如果（（X2<！= X&放大器;&安培; X < = X1））{返回false; }
}
，否则
{
如果（（X1<！= X&放大器;&安培; X< = X））{返回false; }
}
如果（Y> = Y2）
{
如果（（Y2<！= Y&放大器;&安培; Y< = Y1））{返回false ; }
}
，否则
{
如果（（Y1<！= Y&放大器;&安培; Y< = Y2））{返回false; }
}
如果（X3> = X4）
{
如果（（X4<！= X&放大器;&安培; X< = X3））{返回false ; }
}
，否则
{
如果（（X3<！= X&放大器;&安培; X< = X4））{返回false; }
}
如果（Y3> = Y4）
{
如果（（Y4<！= Y&放大器;&安培; Y< = Y3））{返回false ; }
}
，否则
{
如果（（Y3<！= Y'放大器;&安培;&ŸLT = Y4））{返回false; }
}
}
返回真;
}
私有静态双角（顶点V1，V2的顶点）
{
// TODO修复
顶点V3 =新的顶点（V1.X ，0）;
如果（方向（V3，V1，V2）== 0）
返回180;
双B = EuclideanDistance（V3，V1）;
双击一个= EuclideanDistance（V1，V2）;
双c = EuclideanDistance（V3，V2）;
双角= Math.Acos（（Math.Pow（一，2）+ Math.Pow（B，2） - Math.Pow（C，2））/（2 * A * B））;
如果（方向（V3，V1，V2）小于0）
角= 360 - 角;
返回角;
}
私有静态双EuclideanDistance（顶点V1，V2的顶点）
{
返回的Math.sqrt（Math.Pow（（V1.X - V2.X ），2）+ Math.Pow（（v1.Y - v2.Y），2））;
}
公共静态双重定向（顶点P1，P2顶点，顶点P）
{
双奥林=（p2.X - p1.X）*（ PY - p1.Y） - （PX - p1.X）*（p2.Y - p1.Y）;
如果（奥林大于0）
返回-1; //左
如果（奥林℃下）
返回1; //对
返回0; // Colinier
}
我知道有一个代码加载在这里。但是我不知道我是否能显示的背景下，我有没有它的东西。
其他类：
公共类多边形
{
私人顶点[] VS;
公共多边形（顶点[]顶点）
{
VS =顶点;
}
公共多边形（边界边界）
{
VS = bounds.ToArray（）;
}
公共顶点[] ToArray的（）
{
收益与;
}
公开的IEnumerable<边及GT;边缘（）
{
如果（vs.Length→1）
{
顶点P = VS [0];
的for（int我= 1; I< vs.Length;我++）
{
收益返回新的边缘（P，VS [I]）;
P = VS [I]
}
收益返回新的边缘（P，VS [0]）;
}
}
公共BOOL包含（顶点v）
{
返回RayCasting.RayCast（这一点，V）;
}
}
公共类边缘
{
公共顶点A =新的顶点（0，0）;
公共顶点B =新顶点（0，0）;
公共边缘（）{}
公共边缘（A顶点，顶点B）
{
A = A;
B =;
}
公共边缘（双斧，双唉，双BX，用双）
{
A =新的顶点（AX，AY）;
B =新的顶点（BX，BY）;
}
}
公共类界限
{
公共顶点左上;
公共顶点TopRight;
公共顶点BOTTOMLEFT;
公共顶点BottomRight;
公共边界（）{}
公共边界（TL顶点，顶点TR，BL顶点，顶点BR）
{
左上= TL;
TopRight = TR;
BOTTOMLEFT = BL;
BottomRight = BR;
}
公共顶点[] ToArray的（）
{
返回新顶点[] {左上，TopRight，BottomRight，BOTTOMLEFT};
}
}
公共类顶点
{
公共双X = 0;
公共双Y = 0;
公共顶点（）{}
公共顶点（双X，双Y）
{
X = X;
Y = Y;
}
公共静态顶点[]转换（字符串VS）
{
VS = vs.Replace（[，）;
VS = vs.Replace（]，）;
的String [] SPL = vs.Split（';'）;
名单，LT;顶点> NVS =新的List<&顶点GT;（）;
的foreach（字符串s在SPL）
{
试
{
nvs.Add（新顶点（S））;
}
抓
{
}
}
返回nvs.ToArray（）;
}
公共静态字符串字符串化（顶点[] VS）
{
字符串资源=[;
的foreach（在VS顶点v）
{
RES + = v.ToString（）;
RES + =;
}
解析度= res.RemoveLastCharacter（）;
RES + =];
返回水库;
}
公共静态字符串的ToString（顶点[]数组），
{
字符串资源=[;
的foreach（数组中的顶点v）
RES + = v.ToString（）+，;
返回res.RemoveLastCharacter（）+];
}
/ *
//当X; Ÿ返回-1
//当x ==Ÿ返回0
//当x> Ÿ回报1
公共静态INT比较（顶点的x，顶点Y）
{
//要找到最低
如果（XX< YX）
{
返回-1;
}
，否则如果（x.x代表== y.X）
{
如果（X.Y< y.Y）
{
返回-1;
}
，否则如果（X.Y == y.Y）
{
返回0;
}
，否则
{
返回1;
}
}
，否则
{
返回1;
}
}
* /
公共静态INT CompareY（A顶点，顶点B）
{
如果（AY<通过）
返回-1;
如果（a.Y == b.Y）
返回0;
返回1;
}
公共静态INT COMPAREX（A顶点，顶点B）
{
如果（a.X< b.X）
返回-1;
如果（a.X == b.X）
返回0;
返回1;
}
公共双距离（顶点B）{
双dX的= b.X - this.X;
双DY = b.Y - this.Y;
返回的Math.sqrt（（DX * DX）+（DY * DY））;
}
公共双坡（顶点B）{
双dX的= b.X - this.X;
双DY = b.Y - this.Y;
返回DY / DX;
}
公共静态INT比较（顶点u，A顶点，顶点B）
{
如果（AX == BX和放大器;&安培;一条Y ==通过）返回0;
顶点上=新的顶点（）;
顶点P1 =新的顶点（）;
顶点P2 =新的顶点（）;
upper.X =（u.X + 180）* 360;
upper.Y =（u.Y + 90）* 180;
p1.X =（a.X + 180）* 360;
p1.Y =（a.Y + 90）* 180;
p2.X =（b.X + 180）* 360;
p2.Y =（b.Y + 90）* 180;
如果（P1 ==上部）返回-1;
如果（P2 ==上部）返回1;
双M1 = upper.slope（P1）;
双平方米= upper.slope（P2）;
如果（M1 == M2）
{
返回p1.distance（上）LT; p2.distance（上部）？ -1：1;
}
如果（M1&下; = 0&放大器;&放大器; 2&0）返回-1;
如果（M1大于0&放大器;&安培; m 2的= 0）返回-1;
返回M1> M2？ -1：1;
}
公共静态顶点UpperLeft（顶点[] VS）
{
顶点顶部= VS [0];
的for（int i = 1; I< vs.Length;我++）
{
顶点TEMP = VS [I]
如果（temp.Y> top.Y ||（temp.Y == top.Y&放大器;&安培; temp.X< top.X））
{
=顶部温度;
}
}
返回顶部;
}
}
解决方案
在会议刚一说明：你应该开始用大写的函数名和变量用小写。在功能 sortByAngle ，你有一个参考参数角度和功能角度同时
假设角度（...）只是为了计算角度两点之间：
私有静态双角（顶点V1，顶点V2）
{
返回数学.Atan2（v2.Y - v1.Y，V2.X - V1.X）;
}
会给你的角度 V1 为 V2 ，在-pi和+ PI之间的弧度。不要混合度，弧度。我的建议是，必须使用弧度，并且仅在必要时为人类可读的输出转换为度。
私有静态顶点[] SortByAngle（顶点[] VS，顶点v，双角）
{
名单，LT;顶点> vertList =新的List<&顶点GT;（VS）;
vertList.Sort（（V1，V2）=方式> AngleDifference（角度，角度（V，V1））的CompareTo（AngleDifference（角度，角度（V，V2））））;
返回vertList.ToArray（）;
}
使用 List.Sort 从最大到顶点之间本身角度至少角差点键，以及顶点排序。 V1 和 V2 在输入元组交换顺序，首先降序排序，也就是最大的区别。角之间的差值，像这样：
私有静态双AngleDifference（双一，双二）
{
在（A< b - Math.PI）A + = Math.PI * 2;
，而（B< A - Math.PI）B + = Math.PI * 2;
返回Math.Abs（A - B）;
}
前两行确保角度不超过180度的间隔。
So I am trying to translate the algorith found here for concave hulls: http://repositorium.sdum.uminho.pt/bitstream/1822/6429/1/ConcaveHull_ACM_MYS.pdf
(Page 65)
Ive read through the entire thing but I cant figure out how to implement sortByAngle and angle, im not to sure what method I should do inside of them. This is what I have so far:
//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<Vertex> hull = new List<Vertex>();
//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 < k)
throw new ArgumentException("K must be equal to or smaller then the amount of dissimilar points", "points");
Vertex firstPoint = clean[0]; //TODO find mid point
hull.Add(firstPoint);
Vertex currentPoint = firstPoint;
Vertex[] dataset = RemoveIndex(clean, 0);
double previousAngle = 0;
int step = 2;
int i;
while (((currentPoint != firstPoint) || (step == 2)) && (dataset.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 < hull.Count - lastPoint))
{
its = intersectsQ(hull[step - 1 - 1], cPoints[0], hull[step - i - j - 1], hull[step - j - 1]);
j++;
}
}
if (its)
{
return ConcaveHull(points, k + 1);
}
currentPoint = cPoints[0];
hull.Add(currentPoint);
previousAngle = angle(hull[step - 1], hull[step - 2]);
dataset = RemoveIndex(dataset, 0);
step++;
}
bool allInside = true;
i = dataset.Length;
while (allInside && i > 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<Vertex> n = new List<Vertex>(vs);
n.Add(v);
return n.ToArray();
}
private static Vertex[] RemoveIndex(Vertex[] vs, int index)
{
List<Vertex> removed = new List<Vertex>();
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<Vertex> clean = new List<Vertex>();
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<double, Vertex> lengths = new Dictionary<double, Vertex>();
List<Vertex> n = new List<Vertex>();
double[] sorted = lengths.Keys.OrderBy(d => d).ToArray();
for (int i = 0; i < k; i++)
{
n.Add(lengths[sorted[i]]);
}
return n.ToArray();
}
private static Vertex[] sortByAngle(Vertex[] vs, Vertex v, double angle)
{
//TODO
return new Vertex[]{};
}
private static bool intersectsQ(Vertex v1, Vertex v2, Vertex v3, Vertex v4)
{
return intersectsQ(new Edge(v1, v2), new Edge(v3, v4));
}
private static bool intersectsQ(Edge e1, Edge e2)
{
double x1 = e1.A.X;
double x2 = e1.B.X;
double x3 = e2.A.X;
double x4 = e2.B.X;
double y1 = e1.A.Y;
double y2 = e1.B.Y;
double y3 = e2.A.Y;
double y4 = e2.B.Y;
var x = ((x1 * y2 - y1 * x2) * (x3 - x4) - (x1 - x2) * (x3 * y4 - y3 * x4)) / ((x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4));
var y = ((x1 * y2 - y1 * x2) * (y3 - y4) - (y1 - y2) * (x3 * y4 - y3 * x4)) / ((x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4));
if (double.IsNaN(x) || double.IsNaN(y))
{
return false;
}
else
{
if (x1 >= x2)
{
if (!(x2 <= x && x <= x1)) { return false; }
}
else
{
if (!(x1 <= x && x <= x2)) { return false; }
}
if (y1 >= y2)
{
if (!(y2 <= y && y <= y1)) { return false; }
}
else
{
if (!(y1 <= y && y <= y2)) { return false; }
}
if (x3 >= x4)
{
if (!(x4 <= x && x <= x3)) { return false; }
}
else
{
if (!(x3 <= x && x <= x4)) { return false; }
}
if (y3 >= 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)
angle = 360 - angle;
return angle;
}
private static double EuclideanDistance(Vertex v1, Vertex v2)
{
return Math.Sqrt(Math.Pow((v1.X - v2.X), 2) + Math.Pow((v1.Y - v2.Y), 2));
}
public static double Orientation(Vertex p1, Vertex p2, Vertex p)
{
double Orin = (p2.X - p1.X) * (p.Y - p1.Y) - (p.X - p1.X) * (p2.Y - p1.Y);
if (Orin > 0)
return -1;//Left
if (Orin < 0)
return 1;//Right
return 0;//Colinier
}
I know that there is a load of code here. But im not sure if I can show the context and what I have without it.
Other classes:
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<Edge> 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<Vertex> nvs = new List<Vertex>();
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
//When x == y return 0
//When x > y return 1
public static int Compare(Vertex x, Vertex y)
{
//To find lowest
if (x.X < y.X)
{
return -1;
}
else if (x.X == y.X)
{
if (x.Y < y.Y)
{
return -1;
}
else if (x.Y == y.Y)
{
return 0;
}
else
{
return 1;
}
}
else
{
return 1;
}
}
*/
public static int CompareY(Vertex a, Vertex b)
{
if (a.Y < b.Y)
return -1;
if (a.Y == b.Y)
return 0;
return 1;
}
public static int CompareX(Vertex a, Vertex b)
{
if (a.X < b.X)
return -1;
if (a.X == b.X)
return 0;
return 1;
}
public double distance (Vertex b){
double dX = b.X - this.X;
double dY = b.Y - this.Y;
return Math.Sqrt((dX*dX) + (dY*dY));
}
public double slope (Vertex b){
double dX = b.X - this.X;
double dY = b.Y - this.Y;
return dY / dX;
}
public static int Compare(Vertex u, Vertex a, Vertex b)
{
if (a.X == b.X && a.Y == b.Y) return 0;
Vertex upper = new Vertex();
Vertex p1 = new Vertex();
Vertex p2 = new Vertex();
upper.X = (u.X + 180) * 360;
upper.Y = (u.Y + 90) * 180;
p1.X = (a.X + 180) * 360;
p1.Y = (a.Y + 90) * 180;
p2.X = (b.X + 180) * 360;
p2.Y = (b.Y + 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 && m2 > 0) return -1;
if (m1 > 0 && m2 <= 0) return -1;
return m1 > m2 ? -1 : 1;
}
public static Vertex UpperLeft(Vertex[] vs)
{
Vertex top = vs[0];
for (int i = 1; i < vs.Length; i++)
{
Vertex temp = vs[i];
if (temp.Y > top.Y || (temp.Y == top.Y && temp.X < top.X))
{
top = temp;
}
}
return top;
}
}
解决方案
Just a note on convention: you should start function names with upper case, and variables with lower case. In the function sortByAngle, you have a reference to the parameter angle and the function angle simultaneously.
Assuming Angle(...) is simply meant to calculate the angle between two points:
private static double Angle(Vertex v1, Vertex v2)
{
return Math.Atan2(v2.Y - v1.Y, v2.X - v1.X);
}
will give you the angle from v1 to v2, in radians between -pi and +pi. Do not mix degrees and radians. My suggestion is to always use radians, and only convert to degrees if necessary for human-readable output.
private static Vertex[] SortByAngle(Vertex[] vs, Vertex v, double angle)
{
List<Vertex> vertList = new List<Vertex>(vs);
vertList.Sort((v1, v2) => AngleDifference(angle, Angle(v, v1)).CompareTo(AngleDifference(angle, Angle(v, v2))));
return vertList.ToArray();
}
uses List.Sort to sort the vertices from greatest to least angle difference between the vertices point and itself, and angle. The order of v1 and v2 are swapped in the input tuple to sort descending, that is, greatest difference first. The difference between angles is calculated like so:
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);
}
The first two lines ensure that the angles are not more than 180 degrees apart.
这篇关于翻译凹壳算法到C＃的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
