由N个点组成的凸多边形的问题(100分求不够再加，顶着有分)

Question

由N个点组成的凸多边形,如何把顶点的点找出来
在线等 谢谢大家

Answer 1

点是按顺序排列的话就好办了
循环所有点，
if(求斜率(点[i-1],点[i]) != 求斜率(点[i],点[i+1])
顶点list.add(点[i]);

Answer 2

你的问题应该叫做：求最小的凸多边形（Convex Hull）这里有一个O(n)的算法：
The convex hull of a simple polygon can be constructed in O(n) time. The basic idea is very simple. Starting from the leftmost vertex, at each step one looks at three consecutive vertices of the polygon. If the resulting angle is concave, then the middle point is discarded and the next (along the polygon) vertex is added to the triple to be tested. If the angle is convex, then the whole triple is shifted by one vertex along the polygon. However quite a few published articles overlooked a possibility that deletion of a vertex from a polygon may result in a self-intersecting polygon, rendering further flow of the algorithm invalid. Fortunately, this case may also be handled efficiently.
http://en.wikipedia.org/wiki/Convex_hull_algorithms源自http://www.technodabble.com/polygon/的伪代码：polygon = pointWithMinimumXCoordinate();
points.removePointWithMinimumXCoordinate();
while(points.hasMorePoints()) {
   farthestPoint = null;
   maximumDistance = 0;
   foreach point in points {
      foreach side in polygon {
         minimumDistance = HUGE_NUMBER;
         if (distanceFromPointToSide(point, side) < minimumDistance) {
            minimumDistance = distanceFromPointToSide(point, side);
         }
      }
      if (minimumDistance < maximumDistance) {
         farthestPoint = point;
         maximumDistance = minimumDistance;
      }
   }
   polygon.insert(farthestPoint);
   points.removePointsContainedBy(polygon);
}

Answer 3

指定一个任意点p1，然后求它与所有其余点的斜率。
与其的斜率相同的那些点在p1所在的边上，其余点的斜率都是唯一的。
求出这条边(s1)上横(纵)坐标最大的点跟横(纵)坐标最小的点，得到两个顶点。接下来在p1的唯一斜率中找这样的斜率：比s1的斜率大，但是与s1斜率差最小。
与p1形成这个斜率的点p2在s1的临边上。
这样可以得到s1的临边，依次类推，所有边都能得到。麻烦一定是很麻烦的。

Answer 4

兄台
又见你
学GIS的
这个我想的话
最笨的是：一个点一个点的比较
还有可以先建立一个空间索引（网格），先剔除一些不可能的点，缩小搜索范围
还有个想法：你觉得泰森多边形能不能解决这个问题（突然想到的，随便说说）

Answer 5

凸多边形简单啊，只要找出边线上的点的集合，再按y坐标从上到下遍历一遍找出斜率的转折点就是顶点了。找边线更简单，遍历所有的点，每个y坐标值只取x最大和最小的两个点即可。

Answer 6

∽∝∞∽∝∞∽∝∞∽∝∞∽∝∞∽∝∞∽∝∞∽∝∞∽∝∞∽∝∞∽∝∞∽∝∞∽∝∞∽∝∞∽∝∞∽∝∞力争成为中国最大的架构师群联盟，架构师技术交流群：28995710正式开放！！！已经上传的顶级软件产品的架构分析,本群资料仅供研究学习，不得商用！！！
google 、
eBay、
Youtube、
淘宝等
......
技术文章包括：
《自己动手写操作系统》
《搜索引擎-原理、技术与系统》
《企业应用架构模式》
......
重要的RUP实例
设计模式精解
......
资料陆续上传中
∽∝∞∽∝∞∽∝∞∽∝∞∽∝∞∽∝∞∽∝∞∽∝∞∽∝∞∽∝∞∽∝∞∽∝∞∽∝∞∽∝∞∽∝∞∽∝∞

Answer 7

谢谢大哥的关注，最笨的是：一个点一个点的比较 和12楼的哥们思路差不多，再就是空间索引我还没有接触过，不会用 
还有就是泰森多边形我baidu 了一下
  荷兰气候学家A·H·Thiessen提出了一种根据离散分布的气象站的降雨量来计算平均降雨量的方法，即将所有相邻气象站连成三角形，作这些三角形各边的垂直平分线，于是每个气象站周围的若干垂直平分线便围成一个多边形。用这个多边形内所包含的一个唯一气象站的降雨强度来表示这个多边形区域内的降雨强度，并称这个多边形为泰森多边形。
       泰森多边形的特性是：
       1、每个泰森多边形内仅含有一个离散点数据；
       2、泰森多边形内的点到相应离散点的距离最近；
       3、位于泰森多边形边上的点到其两边的离散点的距离相等。
       泰森多边形可用于定性分析、统计分析、邻近分析等。例如，可以用离散点的性质来描述泰森多边形区域的性质；可用离散点的数据来计算泰森多边形区域的数据；判断一个离散点与其它哪些离散点相邻时，可根据泰森多边形直接得出，且若泰森多边形是n边形，则就与n个离散点相邻；当某一数据点落入某一泰森多边形中时，它与相应的离散点最邻近，无需计算距离。
        在泰森多边形的构建中，首先要将离散点构成三角网。这种三角网称为Delaunay三角网。

Answer 8

代码供你参考，采用分而治之算法，比较快，是O(n*log n）级别。
另外你需要一个Geometry.cs的文件, 80行左右,在http://topic.csdn.net/u/20080410/09/e8add01d-ac9e-405d-ac02-520502432fcc.html可以找到。两个文件就可以在.Net2下编译运行了。using System;
using System.Drawing;
using System.Windows.Forms;public class UTestForm : Form
{
    public UTestForm()
    {
        this.Text = "Click in the body";
    }
    protected override void OnMouseClick(MouseEventArgs e)
    {
        Random random = new Random();
        Rectangle rect = this.ClientRectangle;
        rect.Inflate(-50, -50);        int dots = random.Next(10, 50);
        Vec2[] points = new Vec2[dots];
        for (int i = 0; i < points.Length; i++)
        {
            points[i] = new Vec2(random.Next(rect.Left, rect.Right), random.Next(rect.Top, rect.Bottom));
        }
        Vec2[] hull = Helper.ConvexHullHelper.GetConvexHull(points);        using (Graphics g = this.CreateGraphics())
        {
            OnPaintBackground(new PaintEventArgs(g, rect));
            foreach (Vec2 point in points)
            {
                g.DrawEllipse(Pens.Red, point.x, point.y, 1, 1);
            }
            PointF[] polygon = new PointF[hull.Length];
            for (int i = 0; i < polygon.Length; i++)
            {
                polygon[i].X = hull[i].x;
                polygon[i].Y = hull[i].y;
            }
            g.DrawPolygon(Pens.Blue, polygon);
        }    }
    [STAThread]
    static void Main()
    {
        Application.Run(new UTestForm());
    }
}namespace Helper
{
    using System.Collections.Generic;
    using PointList = System.Collections.Generic.LinkedList<Vec2>;
    using PointNode = System.Collections.Generic.LinkedListNode<Vec2>;    class ConvexHullHelper
    {
        public static Vec2[] GetConvexHull(Vec2[] points)
        {
            Line top2bottom = GetExtremes(points);            PointList hull = new PointList();
            List<Vec2> allPoints = new List<Vec2>(points);            PointNode first = hull.AddLast(top2bottom.p1);
            PointNode middle = hull.AddLast(top2bottom.p2);
            PointNode last = hull.AddLast(top2bottom.p1);            ConstructLeftHull(allPoints, hull, first, middle);
            ConstructLeftHull(allPoints, hull, middle, last);            hull.RemoveLast();
            Vec2[] result = new Vec2[hull.Count];
            hull.CopyTo(result, 0);
            return result;
        }        static Line GetExtremes(Vec2[] points)
        {
            Vec2 topLeft = new Vec2(float.MaxValue, float.MaxValue);
            Vec2 bottomRight = new Vec2(float.MinValue, float.MinValue);            foreach (Vec2 point in points)
            {
                if (point.y < topLeft.y) topLeft = point;
                else if (point.y == topLeft.y && point.x < topLeft.x) topLeft = point;                if (point.y > bottomRight.y) bottomRight = point;
                else if (point.y == bottomRight.y && point.x > bottomRight.x) bottomRight = point;
            }
            return new Line(topLeft, bottomRight);
        }        static void ConstructLeftHull(List<Vec2> points, PointList hull, PointNode start, PointNode end)
        {
            Line ray = new Line(start.Value, end.Value);
            List<Vec2> leftPoints = new List<Vec2>();            Vec2 furthestPoint = new Vec2();
            float maxDistance = float.MinValue;            foreach (Vec2 point in points)
            {
                float distance = (point - ray.p1) * ray.Normal();
                if (distance > 0.00001)
                {
                    leftPoints.Add(point);
                    if (distance > maxDistance)
                    {
                        maxDistance = distance;
                        furthestPoint = point;
                    }
                }
            }            if (leftPoints.Count > 0)
            {
                PointNode middle = hull.AddAfter(start, furthestPoint);
                ConstructLeftHull(leftPoints, hull, start, middle);
                ConstructLeftHull(leftPoints, hull, middle, end);
            }
        }
    }
}