找到给定点集的简单闭合路径-yiteyi-C++库

给定一组点，连接点而不交叉。

null

Simple Closed Path for a given set of points 1

例子：

Input: points[] = {(0, 3), (1, 1), (2, 2), (4, 4),
                   (0, 0), (1, 2), (3, 1}, {3, 3}};

Output: Connecting points in following order would
        not cause any crossing
       {(0, 0), (3, 1), (1, 1), (2, 2), (3, 3),
        (4, 4), (1, 2), (0, 3)}

我们强烈建议您尽量减少浏览器，并先自己尝试。 这个想法是使用排序。

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

find the bottom-most point by comparing y coordinate of all points

考虑其余的N-1点并用POLR角按点逆时针排序（0）。如果两点的马球角度相同，那么先把最近的一点放在第一位。
遍历排序的数组（按角度的递增顺序排序）会产生简单的闭合路径。

traversing the sorted array

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

下面是C++实现上述思想。

C++

                         // A C++ program to find simple closed path for n points                       
                         // for explanation of orientation()                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
                                   
                         struct                                     Point                       
                         {                       
                                                 int                                     x, y;                       
                         };                       
                                   
                         // A global point needed for  sorting points with reference                       
                         // to the first point. Used in compare function of qsort()                       
                         Point p0;                       
                                   
                         // A utility function to swap two points                       
                         int                                     swap(Point &p1, Point &p2)                       
                         {                       
                                                 Point temp = p1;                       
                                                 p1 = p2;                       
                                                 p2 = temp;                       
                         }                       
                                   
                         // A utility function to return square of distance between                       
                         // p1 and p2                       
                         int                                     dist(Point p1, Point p2)                       
                         {                       
                                                 return                                     (p1.x - p2.x)*(p1.x - p2.x) +                       
                                                 (p1.y - p2.y)*(p1.y - p2.y);                       
                         }                       
                                   
                         // To find orientation of ordered triplet (p, q, r).                       
                         // The function returns following values                       
                         // 0 --> p, q and r are collinear                       
                         // 1 --> Clockwise                       
                         // 2 --> Counterclockwise                       
                         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 counterclock wise                       
                         }                       
                                   
                         // A function used by library function qsort() to sort                       
                         //  an array of points with respect to the first point                       
                         int                                     compare(                                     const                                     void                                     *vp1,                                     const                                     void                                     *vp2)                       
                         {                       
                                                 Point *p1 = (Point *)vp1;                       
                                                 Point *p2 = (Point *)vp2;                       
                                   
                                                 // Find orientation                       
                                                 int                                     o = orientation(p0, *p1, *p2);                       
                                                 if                                     (o == 0)                       
                                                 return                                     (dist(p0, *p2) >= dist(p0, *p1))? -1 : 1;                       
                                   
                                                 return                                     (o == 2)? -1: 1;                       
                         }                       
                                   
                         // Prints simple closed path for a set of n points.                       
                         void                                     printClosedPath(Point points[],                                     int                                     n)                       
                         {                       
                                                 // Find the bottommost point                       
                                                 int                                     ymin = points[0].y, min = 0;                       
                                                 for                                     (                                     int                                     i = 1; i < n; i++)                       
                                                 {                       
                                                 int                                     y = points[i].y;                       
                                   
                                                 // Pick the bottom-most. In case of tie, chose the                       
                                                 // left most point                       
                                                 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                       
                                                 swap(points[0], points[min]);                       
                                   
                                                 // 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];                       
                                                 qsort                                     (&points[1], n-1,                                     sizeof                                     (Point), compare);                       
                                   
                                                 // Now stack has the output points, print contents                       
                                                 // of stack                       
                                                 for                                     (                                     int                                     i=0; i<n; i++)                       
                                                 cout <<                                     "("                                     << points[i].x <<                                     ", "                       
                                                 << points[i].y <<                                     "), "                                     ;                       
                         }                       
                                   
                         // Driver program to test above functions                       
                         int                                     main()                       
                         {                       
                                                 Point points[] = {{0, 3}, {1, 1}, {2, 2}, {4, 4},                       
                                                 {0, 0}, {1, 2}, {3, 1}, {3, 3}};                       
                                                 int                                     n =                                     sizeof                                     (points)/                                     sizeof                                     (points[0]);                       
                                                 printClosedPath(points, n);                       
                                                 return                                     0;                       
                         }                       

输出：

(0, 0), (3, 1), (1, 1), (2, 2), (3, 3),
(4, 4), (1, 2), (0, 3),

如果我们对排序点使用O（nLogn）排序算法，则上述解决方案的时间复杂度为O（nLogn）。

资料来源： http://www.dcs.gla.ac.uk/~pat/52233/slides/Geometry1x1。pdf 本文由 拉吉耶夫·阿格拉瓦尔 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章