网络上经常会遇到判断图形个数的题目，如下例：
如果我们要把图中所有三角形一个一个选出来，在已知每个交点的前提下，该如何用代码判断我们选的图形是否是三角形呢。如下图，如何把图3筛选出来呢？
这里需要用到两步：
1.得到所选图形（阴影部分）所包含的所有小图形的顶点集合，求集合的凸包，根据凸包顶点个数判定凸包围成的图形是否是三角形，若顶点个数不为3则不是三角形，如图（1）。
.2.若凸包围成的图形是三角形，判断凸包的面积与所选图形（所有选中的小图形面积之和）是否相等，若相等则所选图形是三角形，若不相等则不是三角形，如上图（2）。
二、求点的凸包——Graham's Scan法介绍（1） 什么是凸包
在二维欧几里得空间中，凸包可想象为一条刚好包着所有点的橡皮圈。
用不严谨的话来讲，给定二维平面上的点集，凸包就是将最外层的点连接起来构成的凸多边型，它能包含点集中所有的点。如下图红色部分：
（2） Graham's Scan法求凸包
这个算法是由数学大师葛立恒（Graham）发明的，算法思路如下：
1.找出所有点中y坐标最小的点，若y坐标最小的点有两个以上，则选择其中x坐标最小的点，将此点记为H；
2.设除H之外所有点的坐标集合为N{p1,p2,p3,p4,p5,p6,…}，分别计算向量< H,p1>，< H,p2>，< H,p3>极坐标的角度，对集合N按极坐标角度的大小排序，即以H为圆心，顺时针扫描各点，将扫描到的点依次加入集合中；如下图，排好序的坐标集合为N{a1，a2，a3，a4，a5，a6}，其中θ为向量< H,a1>极坐标的角度。
3.线段< H,a1>一定在凸包上，现在加入a2，假设a2也在凸包上，接下来加入a3，如果a3在向量<a1，a2>的左侧则判断a2不在凸包上，需将a2从凸包中移除，在此例中a3在向量<a1，a2>的右侧；然后加入a4，如果a4在向量<a2，a3>的左侧则判断a3不在凸包上，此例中a4在向量<a2，a3>的左侧，所以需将a3从凸包中移除，接下来需回溯判断a4在向量<a1，a2>的左侧还是右侧，决定是否要将a2移除…，即每加入一点时，必须考虑到前面的线段是否在凸包上。从基点开始，凸包上每条相临的线段的旋转方向应该一致，并与扫描方向相同。如果发现新加的点使得新线段与上线段的旋转方向发生变化，则可判定上一点必然不在凸包上。如下图：
当加入d点时，发现<c,d>和<b,c>的旋转方向不一致(d在<b,c>左侧)，则说明c点不在凸包上。
可用叉积来判断一个点在一个向量的左侧还是右侧，如上图，若<b,c>与<c,d>的叉积为正则d在<b,c>的右侧，若为负则在<b,c>的右侧，若为0，在d在<b,c>直线上。
复杂度
这个算法可以直接在原数据上进行运算，因此空间复杂度为O⑴。但如果将凸包的结果存储到另一数组中，则可能在代码级别进行优化。由于在扫描凸包前要进行排序，因此时间复杂度至少为快速排序的O(nlgn)。后面的扫描过程复杂度为O(n)，因此整个算法的复杂度为O(nlgn)。
三、求解凸包的javascript代码设数组points是存储所选图形的所有顶点的集合
1 var convexPoints=[];//用来存储凸包 2 var startPoint=getStartPoint(points);//得到y坐标最小的点 3 points.splice(points.indexOf(startPoint),1); 4 points.sort(compare);//按极坐标排序 5 convexPoints.push(startPoint); 6 convexPoints.push(points[0]); 7 8 for(i=1;i<points.length;i++){ 9 var vector1={ x:convexPoints[convexPoints.length-1].x-convexPoints[convexPoints.length-2].x, 10 y:convexPoints[convexPoints.length-1].y-convexPoints[convexPoints.length-2].y}; 11 12 var vector2={ x:points[i].x-convexPoints[convexPoints.length-1].x, 13 y:points[i].y-convexPoints[convexPoints.length-1].y}; 14 //若两个向量叉积小于0，则需将上一个点移除 15 while(getCross(vector1,vector2)<0){ 16 convexPoints.pop(); 17 vector1={ x:convexPoints[convexPoints.length-1].x-convexPoints[convexPoints.length-2].x, 18 y:convexPoints[convexPoints.length-1].y-convexPoints[convexPoints.length-2].y}; 19 vector2={ x:points[i].x-convexPoints[convexPoints.length-1].x, 20 y:points[i].y-convexPoints[convexPoints.length-1].y}; 21 } 22 convexPoints.push(points[i]); 23 }