我正在尝试将此处描述的算法(第 12 页)从伪代码转换为有效的 C# 代码。该算法描述了如何通过将被认为太长的边缘分解为更小的边缘来将凸包“转换”为凹包。我理解作者提出的一般想法,但在将其转换为工作代码时遇到了麻烦。请看下面我到目前为止得到的代码,包括每个伪代码行开头的注释(//)。我遇到的问题与特定线路无关 - 尽管我确信当前计算“localMaximumDistance”的方法不正确。如果有人对如何解决这个问题有任何指示,我真的很想听听这些。(在伪代码中,这行写着“计算边缘的局部最大距离 d;”
提前感谢您的时间和反馈!:)
List<Line> concaveLineList = new List<Line>();
List<Line> sortedList = lineList.OrderByDescending(CalculateLength).ToList();
const int concaveTreshhold = 40;
PointCollection concavePointCollection = new PointCollection();
while (sortedList.Count > 0) {
Console.WriteLine(concaveLineList.Count.ToString());
//select the longest edge e from list A
Line longestLine = sortedList[0];
//remove edge e from list A
sortedList.RemoveAt(0);
//calculate local maximum distance d for edges - ???
//double localMaximumDistance = CalculateLength(longestLine);
List<Point<double>> nearbyPoints = new List<Point<double>>();
foreach (BallUc ballUc in ballUcList) {
if (Math.Abs(ballUc .CurrentPosition.X - longestLine.X1) > concaveTreshhold &&
Math.Abs(ballUc .CurrentPosition.Y - longestLine.Y1) > concaveTreshhold) {
nearbyPoints.Add(new Point<double>(ballUc.CurrentPosition.X, ballUc.CurrentPosition.Y));
}
}
double lineLenght = CalculateLength(longestLine);
double localMaximumDistance = lineLenght / nearbyPoints.Count + concaveTreshhold * 4; //this value is based on nothing currently..
if (lineLenght > localMaximumDistance) {
//find the point p with the smallest maximum angle a
Point smallestAnglePoint = new Point();
double? smallestAngle = null;
foreach (Point p in pointCollection) {
if ((p.X == longestLine.X1 && p.Y == longestLine.Y1) ||
(p.X == longestLine.X2 && p.Y == longestLine.Y2)) {
//these are the points already in the line.
}
else {
Line tempLine1 = new Line {X1 = p.X, X2 = longestLine.X1, Y1 = p.Y, Y2 = longestLine.Y1};
Line tempLine2 = new Line {X1 = p.X, X2 = longestLine.X2, Y1 = p.Y, Y2 = longestLine.Y2};
//calculate angle between the longest edge and the new edges
double angleInRadians1 = Math.Atan2(p.Y, p.X) - Math.Atan2(tempLine1.Y2, tempLine1.X2);
double angleInRadians2 = Math.Atan2(p.Y, p.X) - Math.Atan2(tempLine2.Y2, tempLine2.X2);
//select the largest angle of the two angles
double largestLocalAngle = Math.Max(angleInRadians1, angleInRadians2);
//in case of first calculation, smallestAngle is still null - in this case it should be assigned the value
//(this is probably not very elegant code)
if (smallestAngle == null) {
smallestAngle = largestLocalAngle;
smallestAnglePoint = p;
}
//we have to find the smallest angle.
else if (largestLocalAngle < smallestAngle) {
smallestAngle = largestLocalAngle;
smallestAnglePoint = p;
}
//double angleinDegrees = angleInRadians * 180 / Math.PI;
}
}
//TODO if angle a is small enough and point p is not on the boundary
//create edges e2 and e3 between point p and endpoints of edge e
Line e2 = new Line {
X1 = smallestAnglePoint.X,
Y1 = smallestAnglePoint.Y,
X2 = longestLine.X1,
Y2 = longestLine.Y1
};
sortedList.Add(e2);
Line e3 = new Line {
X1 = smallestAnglePoint.X,
Y1 = smallestAnglePoint.Y,
X2 = longestLine.X2,
Y2 = longestLine.Y2
};
sortedList.Add(e3);
//if edge e2 and e3 don't intersect any other edge
foreach (Line line in sortedList) {
Point lineInitialPoint = new Point(line.X1, line.Y1);
Point lineTerminalPoint = new Point(line.X2, line.Y2);
Point line2InitialPoint = new Point(e2.X1, e2.Y1);
Point line2TerminalPoint = new Point(e2.X2, e2.Y2);
Point line3InitialPoint = new Point(e2.X1, e2.Y1);
Point line3TerminalPoint = new Point(e2.X2, e2.Y2);
Point intersectionPoint = GetIntersection(line2InitialPoint, line2TerminalPoint, lineInitialPoint, lineTerminalPoint);
Point intersectionPoint2 = GetIntersection(line3InitialPoint, line3TerminalPoint, lineInitialPoint, lineTerminalPoint);
if ((Double.IsNaN(intersectionPoint.X) && Double.IsNaN(intersectionPoint.Y)) &&
(Double.IsNaN(intersectionPoint2.X) && Double.IsNaN(intersectionPoint2.Y))) {
//no intersection found, keep rolling..
//Console.WriteLine("no intersection found");
}
else {
//intersection found, lines no longer valid
Console.WriteLine("intersection found");
break;
}
concaveLineList.Add(e2);
concaveLineList.Add(e3);
}
}
//if edge e2 and e3 was not added to list A
else {
//add edge e to list B
concaveLineList.Add(longestLine);
concavePointCollection.Add(new Point(longestLine.X1, longestLine.Y1));
concavePointCollection.Add(new Point(longestLine.X2, longestLine.Y2));
}
}