c# - 凹包算法从伪代码到C#

Question

我正在尝试按照描述转换算法 here (第 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));
        }
    }

Answer 1

我已经实现了这个algorithm via JavaScript ，也许它会对你有所帮助。 There您可以看到将凸包转换为凹包的函数。我的算法实现与论文中的算法不完全相同，但它是基于它的。

在我的实现中，我跳过了 localMaximumDistance 的计算 :-) 并决定首先我需要看看我的算法没有 localMaximumDistance 会出错的用例。