点。在按夹角大小分类，得到分类表。 Step5：用格雷厄姆算法的到p1，p2的凸壳
1.数据结构。
程序实现
2.算法的选择。
3编写程序。
三 维 空 间 的 凸 壳
数据挖掘的简单运用
多维空间概述 一维 二维 三维 四维（事实上网络数据的维数较高）
聚类分析 如何把数据归类？
算法设计与分析
Step1:在p1内部找一点p Step2：if p不属于p2 goto step4 Else goto step3 Step3：p在p2的内部，用p连接p1，p2的各个顶点并按各个夹角排序。
得到p1，p2的一个分类表。 Goto step5. Step4：计算p到p2的正切线，得到u，v，删除uv链上的点保留u，v顶
西七620制作
3P4 4 5Fra bibliotekP5p1
P3
P 2
P 2
1
图一
图二
图三
图四
格雷厄姆算法
一： 找初始点： 先从这一系列的点中找到Y轴最小的点，如果存在相等的纵坐标的值，则取 X值最小的点P0。 显然P0是凸壳CHS（S）中的点。
二：以p0为定点连接其他的点，形成n-1条线段，计算各线段与x轴的夹 角，并按夹角的大小和线段的长度排序。
三：若夹角相同，则删除线段最短的点。这样得到一个新的序列。 p0，p1到pm，其中p0，p1，和pm必为凸壳中的点。
四：再从p3，开始重复二和三，直到遍所有点，最后剩下的点，就是所求的凸壳。
凸壳问题分治法的过程
划分过程
p1 p14
归并过程
Divide and Conquer: Step1：把S中的点按x坐标进行排序。 Step2：划分成两个子集S1，S2. Step3：P1=CH(S1)和P2=CH(S2). Step：合并P1，P2得到解集P.
凸壳问题的常用方法
卷包裹法 格雷厄姆算法 分治法
卷包裹法
一： 找初始点： 先从这一系列的点中找到Y轴最小的点，如果存在相等的Y值，则取 X值最小的点P0。 显然P0是凸壳CHS（S）中的点。
二： 以P0为定点，连接P0和其他的点，的到n-1条直线段，计算各线段的 角度，将角度最小的点P1加入到凸壳序列中，并以P1为定点，重复二。 直到回到初始点P0.
……
Si的解
子集解的合并
问S的题解S
……
问题Sn
……
Sn的解
凸壳问题
问题要求： 给定一个点集
s
{
p, 1
p , 2
pn}，求一个
最小凸边形包含S中所有的点，组成这个凸边形的点的集合就是凸 壳，用CHS(S)表示（Convex hull的英文缩写）。
上图所示的凸壳为：CHS(S)={ p1,p3,p10,p12,p0 }
关于凸壳问题的分治法
分治法的求解过程
一般来说，分治法的求解过程由以下三个阶段组成： (1)划分 (2)求解子问题 (3)合并
二分：
子问题1 的规模是n/2 子问题1的解
原问题 的规模是n
子问题2 的规模是n/2
子问题2的解
原问题的解
问题的分解
问题S
问题S1
问题S2
……
问题Si
S1的解
S2的解
子问题求 解