C# 找到给定点集的简单闭合路径（Find Simple Closed Path for a given set of points）

 给定一组点，将这些点连接起来而不相交

例子： 

输入：points[] = {(0, 3), (1, 1), (2, 2), (4, 4),
                   (0, 0), (1, 2), (3, 1}, {3, 3}};

输出：按以下顺序连接点将
        不造成任何交叉
       {(0, 0), (3, 1), (1, 1), (2, 2), (3, 3),
        （4，4），（1，2），（0，3）}
        
我们强烈建议您最小化浏览器并先自己尝试一下。

这个想法是使用排序。 

通过比较所有点的 y 坐标来找到最底部的点。如果有两个点的 y 值相同，则考虑 x 坐标值较小的点。将最底部的点放在第一个位置。 

考虑剩余的 n-1 个点，并围绕 points[0] 按照极角逆时针顺序排列它们。如果两个点的极角相同，则将最近的点放在最前面。

遍历排序数组（按角度升序排序）产生简单的闭合路径。

如何计算角度？ 
一种解决方案是使用三角函数。 
观察：我们不关心角度的实际值。我们只想按角度排序。 
想法：使用方向来比较角度，而无需实际计算它们！

以下是上述想法的实现:

using System;
using System.Collections.Generic;
 
public class Point {
    public int x, y;
    public Point(int x, int y)
    {
        this.x = x;
        this.y = y;
    }
}
 
public class ClosestPath {
    static Point p0;
 
    static int dist(Point p1, Point p2)
    {
        return (p1.x - p2.x) * (p1.x - p2.x)
            + (p1.y - p2.y) * (p1.y - p2.y);
    }
 
    static int orientation(Point p, Point q, Point r)
    {
        int val = (q.y - p.y) * (r.x - q.x)
                  - (q.x - p.x) * (r.y - q.y);
        if (val == 0)
            return 0; // collinear
        return (val > 0)
            ? 1
            : 2; // clockwise or counterclockwise
    }
 
    static int compare(Point p1, Point p2)
    {
        int o = orientation(p0, p1, p2);
        if (o == 0)
            return (dist(p0, p2) >= dist(p0, p1)) ? -1 : 1;
        return (o == 2) ? -1 : 1;
    }
 
    static void printClosedPath(List<Point> points, int n)
    {
        // Find the bottommost point
        int ymin = points[0].y;
        int min = 0;
        for (int i = 1; i < n; i++) {
            int y = points[i].y;
            if ((y < ymin)
                || (ymin == y
                    && points[i].x < points[min].x)) {
                ymin = points[i].y;
                min = i;
            }
        }
 
        // Place the bottom-most point at first position
        Point temp = points[0];
        points[0] = points[min];
        points[min] = temp;
 
        // Sort n-1 points with respect to the first point.
        // A point p1 comes before p2 in sorted output if p2
        // has larger polar angle (in counterclockwise
        // direction) than p1
        p0 = points[0];
        points.Sort(compare);
 
        // Now stack has the output points, print contents
        // of stack
        for (int i = 0; i < n; i++) {
            Console.Write("(" + points[i].x + ", "
                          + points[i].y + "), ");
        }
    }
 
    public static void Main()
    {
        List<Point> points = new List<Point>() {
            new Point(0, 3), new Point(1, 1),
                new Point(2, 2), new Point(4, 4),
                new Point(0, 0), new Point(1, 2),
                new Point(3, 1), new Point(3, 3)
        };
        int n = points.Count;
 
        printClosedPath(points, n);
    }
}
// This code is contributed by user_dtewbxkn77n 

 输出： 

(0, 0), (3, 1), (1, 1), (2, 2), (3, 3),
（4，4），（1，2），（0，3），
如果我们使用 O(nLogn) 排序算法对点进行排序，则上述解决方案的时间复杂度为 O(n Log n)。
辅助空间： O(1)，因为没有占用额外空间。

来源： 
http://www.dcs.gla.ac.uk/~pat/52233/slides/Geometry1x1.pdf