C# 利用分治算法求凸包(Convex Hull using Divide and Conquer Algorithm)

如果您喜欢此文章请收藏、点赞、评论谢谢祝您快乐每一天。在计算几何中凸包是包含给定点集的最小凸多边形。它是一个基本概念在计算机图形学、机器人学和图像处理等各个领域都有应用。​凸包的重要性凸包在计算几何中非常重要原因有以下几点碰撞检测凸包可用于有效检测 2D 或 3D 空间中物体之间的碰撞。图像处理凸包可用于从图像中提取有意义的形状例如物体的轮廓。数据可视化凸包可用于可视化散点图中数据点的分布。输入是一个由 x 和 y 坐标指定的点数组。输出是这组点的凸包。利用分治算法求凸包先决条件两个凸多边形之间的切线JavaScript 两个凸多边形之间的切线:https://blog.csdn.net/hefeng_aspnet/article/details/160182506C# 两个凸多边形之间的切线:https://blog.csdn.net/hefeng_aspnet/article/details/160182477Python 两个凸多边形之间的切线:https://blog.csdn.net/hefeng_aspnet/article/details/160182449Java 两个凸多边形之间的切线:https://blog.csdn.net/hefeng_aspnet/article/details/160182407C 两个凸多边形之间的切线:https://blog.csdn.net/hefeng_aspnet/article/details/160182260算法给定一个点集我们需要找到它的凸包。假设我们已知左半部分点集和右半部分点集的凸包那么现在的问题是将这两个凸包合并从而确定整个点集的凸包。这可以通过找到左右凸包的上切线和下切线来实现。如图所示两个凸多边形之间的切线。设左凸包为 a右凸包为 b。则下切线和上切线分别标记为 1 和 2如图所示。红色轮廓线表示最终的凸包。现在的问题是如何找到左右两半的凸包。这时递归就派上用场了。我们将点集分割直到点数非常少比如只有 5 个点然后我们可以通过穷举算法找到这些点的凸包。将这两半合并就能得到整个点集的凸包。注我们使用暴力算法来寻找少量点的凸包其时间复杂度为 O(n³)。但有人提出由三个或更少点构成的凸包就是全部点集。这没错但问题在于当我们尝试合并一个由两个点构成的左凸包和一个由三个点构成的右凸包时程序在某些特殊情况下会陷入无限循环。因此为了解决这个问题我直接求出了由五个或更少点构成的凸包。O(n³)算法虽然略微复杂一些但并不影响算法的整体复杂度。以下是具体实现步骤using System;using System.Collections.Generic;namespace ConvexHullDivideAndConquer {class Program {static void Main(string[] args){Point[] points new Point[] {new Point(0, 0), new Point(1, -4),new Point(-1, -5), new Point(-5, -3),new Point(-3, -1), new Point(-1, -3),new Point(-2, -2), new Point(-1, -1),new Point(-2, -1), new Point(-1, 1)};ListPoint hull ComputeConvexHull(points);Console.WriteLine(Convex Hull:);foreach(Point p in hull){Console.WriteLine(p.X p.Y);}}static ListPoint ComputeConvexHull(Point[] points){ListPoint hull new ListPoint();// Sort points by x-coordinateArray.Sort(points);// Compute upper hullfor (int i 0; i points.Length; i) {while (hull.Count 2 Point.CrossProduct(hull[hull.Count - 2],hull[hull.Count - 1], points[i]) 0) {hull.RemoveAt(hull.Count - 1);}hull.Add(points[i]);}// Compute lower hullint lowerHullIndex hull.Count 1;for (int i points.Length - 2; i 0; i--) {while (hull.Count lowerHullIndex Point.CrossProduct(hull[hull.Count - 2],hull[hull.Count - 1], points[i]) 0) {hull.RemoveAt(hull.Count - 1);}hull.Add(points[i]);}// Remove last point (its a duplicate of the first// point)hull.RemoveAt(hull.Count - 1);return hull;}}class Point : IComparablePoint {public int X { get; }public int Y { get; }public Point(int x, int y){X x;Y y;}public int CompareTo(Point other){if (X ! other.X) {return X - other.X;}return Y - other.Y;}public static int CrossProduct(Point A, Point B,Point C){return (B.X - A.X) * (C.Y - A.Y)- (B.Y - A.Y) * (C.X - A.X);}}}输出凸包(convex hull)-5 -3-1 -51 -40 0-1 1时间复杂度合并左右凸包需要 O(n) 时间由于我们将点集分成两个相等的部分因此上述算法的时间复杂度为 O(n * log n)。辅助空间O(n)如果您喜欢此文章请收藏、点赞、评论谢谢祝您快乐每一天。