快速凸包算法
Ⅰ 离散点外包凸多边形生成算法（C#或者C++），要有详细代码和说明，最好有可运行的样例程序好的另外加分，急
find&&find_if
临时对象——构造函数的调用.根据若干个离散点创建最大外包凸多边形图形算法
//卷包裹法---创建最大外包凸多边形
//stdafx.h
#define PI 3.1415926
#define NULL 0
#define LEN sizeof(struct XYpoint)
long pointSum;
struct XYpoint
{
double x;
double y;
struct XYpoint *next;
};
XYpoint *creat(void);
struct XYpoint *insert(struct XYpoint *head2,struct XYpoint *p);
struct XYpoint *del(struct XYpoint *head,struct XYpoint *p);
struct XYpoint *miny(struct XYpoint *head);
double angle(struct XYpoint *a,struct XYpoint *b,struct XYpoint *c);
double dis(struct XYpoint *a,struct XYpoint *b);
struct XYpoint *tank( struct XYpoint *head ,struct XYpoint *head2);
struct XYpoint *convexHull( struct XYpoint *head ,struct XYpoint *head2);
void print(struct XYpoint *head2);
//stdafx.cpp
#include "stdafx.h"
#include <math.h>
#include <vector>
//using namespace std;
struct XYpoint *creat(void)
{
struct XYpoint *head;
struct XYpoint *p1,*p2;
FILE *fp;
if((fp=fopen("in_put.txt","r"))==NULL)
{
printf("can not open the file\n");
exit(0);
}
pointSum=0;
p1=p2=(struct XYpoint *)malloc(LEN);
fscanf(fp,"%lf,%lf",&p1->x,&p1->y);
head=NULL;
while(!feof(fp))
{
pointSum=pointSum+1;
if(pointSum==1)
head=p1;
else
p2->next=p1;
p2=p1;
p1=(struct XYpoint *)malloc(LEN);
fscanf(fp,"%lf,%lf",&p1->x,&p1->y);
}
p2->next=NULL;
fclose(fp);
return(head);
}
struct XYpoint *insert(struct XYpoint *head2,struct XYpoint *p)
{
struct XYpoint *p1,*p0;
p0=p;
p1=head2;
while(p1->next!=NULL)
{
p1=p1->next;
}
p1->next=p0;
p0->next=NULL;
if (head2->next==NULL)
printf("not been insert!\n");
return (head2);
}
struct XYpoint *del(struct XYpoint *head,struct XYpoint *p)
{
struct XYpoint *p0,*p1;
if(head==NULL)
{
printf("\nlist null\n");
goto end;
}
p0=head;
while((p->x!=p0->x||p->y!=p0->y)&&p0->next!=NULL)
{
p1=p0;
p0=p0->next;
}
if(p->x==p0->x&&p->y==p0->y)
{
if(p0==head)
head=p0->next;
else
p1->next=p0->next;
}
else
printf("not been found!\n");
end:
return (head);
}
struct XYpoint *miny(struct XYpoint *head)
{
double min;
struct XYpoint *p,*p1;
p=head;
min=p->y;
p1=p;
p=p->next;
while (p!=NULL)
{
if (min>p->y)
{min=p->y,p1=p;}
else if(min==p->y&&p1->x>p->x)
{min=p->y,p1=p;}
else p=p->next;
}
return(p1);
}
double angle(struct XYpoint *a,struct XYpoint *b,struct XYpoint *c)
{
struct XYpoint *p0,*p1,*p2;
double dsx,dsy,dex,dey,cosfi,norm,fi;
p0=a;
p1=b;
p2=c;
dsx=p1->x-p0->x;
dsy=p1->y-p0->y;
dex=p2->x-p1->x;
dey=p2->y-p1->y;
cosfi=dsx*dex+dsy*dey;
norm=(dsx*dsx+dsy*dsy)*(dex*dex+dey*dey);
cosfi/=sqrt( norm );
fi=acos(cosfi);
if(cosfi<=-1) fi=PI;
if(cosfi>=1) fi=0;
return(fi);
}
double dis(struct XYpoint *a,struct XYpoint *b)
{
struct XYpoint *p1,*p2;
double dsx,dsy,dx;
p1=a;
p2=b;
dsx=p2->x-p1->x;
dsy=p2->y-p1->y;
dx=sqrt(dsx*dsx+dsy*dsy);
return(dx);
}
struct XYpoint *tank( struct XYpoint *head ,struct XYpoint *head2)
{
double minfi,fi;
double dx,dy;
struct XYpoint *p,*p1,*p2;
p2=p=head;
p1=head2;
minfi=PI;
while(p!=NULL)
{
dx=p->x-p1->x;
dy=p->y-p1->y;
if(dx!=0)
{
fi=atan(dy/dx);
if(fi<0)
fi=fi+PI;
}
else if(dx==0&&dy==0) fi=PI;
else fi=PI/2.0;
if(minfi>=fi)
{
minfi=fi;p2=p;
}
p=p->next;
}
return (p2);
}
struct XYpoint *convexHull( struct XYpoint *head ,struct XYpoint *head2)
{
double min;
double tempAngle;
struct XYpoint *lastP,*nowP,*p,*p1,*p2;
p=head;
nowP=p1=head2;
lastP=nowP;
p1=p1->next;
nowP=p1;
while(p1->next!=NULL)
{
p1=p1->next;
lastP=nowP;
nowP=p1;
}
min=angle(lastP,nowP,p);
p2=p;
p=p->next;
while(p!=NULL)
{
tempAngle=angle(lastP,nowP,p);
if (min>tempAngle)
{
min=tempAngle;
p2=p;
p=p->next;
}
else if(min==tempAngle)
{
if(dis(nowP,p2)<dis(nowP,p))
p2=p;
p=p->next;
}
else
{
p=p->next;
}
}
return(p2);
}
void print(struct XYpoint *head2)
{
FILE *fp;
struct XYpoint *p;
p=head2;
if((fp=fopen("out_put.txt","w"))==NULL)
{
printf("can not open the file\n");
exit(0);
}
fprintf(fp,"%ld",pointSum);
fprintf(fp,"\n");
while(p!=NULL)
{
fprintf(fp,"%lf,%lf",p->x,p->y);
fprintf(fp,"\n");
p=p->next;
}
fclose(fp);
}
/*
int _tmain(int argc, _TCHAR* argv[])
{
struct XYpoint *head ,*head2,*pp,*qq;
head=creat();
pp=miny(head);
head2=(struct XYpoint *)malloc(LEN);
head2->x=pp->x;
head2->y=pp->y;
head2->next=NULL;
pp=tank(head,head2);
qq=(struct XYpoint *)malloc(LEN);
qq->x=pp->x;
qq->y=pp->y;
qq->next=NULL;
head2=insert(head2,qq);
head=del(head,pp);
pp=convexHull(head,head2);
do
{
qq=(struct XYpoint *)malloc(LEN);
qq->x=pp->x;
qq->y=pp->y;
qq->next=NULL;
head2=insert(head2,qq);
head=del(head,pp);
pp=convexHull(head,head2);
}while(!(head2->x==pp->x&&head2->y==pp->y));
print(head2);
return 0;
}
*/
//view.h
class CCreateHullView : public CView
{
private:
int m_nPtnum;
XYpoint *m_pPtHead;
XYpoint *m_pHullHead;
};
//view.cpp
CCreateHullView::CCreateHullView()
{
// TODO: add construction code here
m_nPtnum = 0;
m_pPtHead = NULL;
m_pHullHead = NULL;
}
CCreateHullView::~CCreateHullView()
{
if (m_nPtnum > 0)
{
XYpoint *p = m_pPtHead;
while (NULL != p)
{
m_pPtHead = p->next;
p->next = NULL;
delete p;
p = m_pPtHead;
}
m_pPtHead = NULL;
m_nPtnum = 0;
p = m_pHullHead;
while (NULL != p)
{
m_pHullHead = p->next;
p->next = NULL;
delete p;
p = m_pHullHead;
}
m_pHullHead = NULL;
}
}
void CCreateHullView::OnLButtonDown(UINT nFlags, CPoint point)
{
// TODO: Add your message handler code here and/or call default
if (0 == m_nPtnum)
{
m_pPtHead = new XYpoint;
m_pPtHead->x = point.x;
m_pPtHead->y = point.y;
m_pPtHead->next = NULL;
m_nPtnum++;
}
XYpoint *p = new XYpoint;
p->x = point.x;
p->y = point.y;
p->next = m_pPtHead;
m_pPtHead = p;
m_nPtnum++;
Invalidate();
CView::OnLButtonDown(nFlags, point);
}
void CCreateHullView::OnCreateHull()
{
// TODO: Add your command handler code here
if (0 < m_nPtnum)
{
struct XYpoint *head ,*head2,*pp,*qq;
head = m_pPtHead;
pp = miny(head);
head2=(struct XYpoint *)malloc(LEN);
head2->x=pp->x;
head2->y=pp->y;
head2->next=NULL;
pp=tank(head,head2);
qq=(struct XYpoint *)malloc(LEN);
qq->x=pp->x;
qq->y=pp->y;
qq->next=NULL;
head2=insert(head2,qq);
head=del(head,pp);
pp=convexHull(head,head2);
do
{
qq=(struct XYpoint *)malloc(LEN);
qq->x=pp->x;
qq->y=pp->y;
qq->next=NULL;
head2=insert(head2,qq);
head=del(head,pp);
pp=convexHull(head,head2);
}while(!(head2->x==pp->x&&head2->y==pp->y));
//print(head2);
m_pHullHead = head2;
Invalidate();
}
}
void CCreateHullView::OnDraw(CDC* pDC)
{
CCreateHullDoc* pDoc = GetDocument();
ASSERT_VALID(pDoc);
// TODO: add draw code for native data here
XYpoint *p = NULL;
if (0 < m_pHullHead)
{
p = m_pHullHead;
pDC->Rectangle((int)(m_pHullHead->x) - 2, (int)(m_pHullHead->y) - 2, (int)(m_pHullHead->x) + 2, (int)(m_pHullHead->y) + 2);
pDC->MoveTo((int)(m_pHullHead->x), (int)(m_pHullHead->y));
p = m_pHullHead->next;
while (NULL != p)
{
pDC->Rectangle(
(int)(p->x) - 2,
(int)(p->y) - 2,
(int)(p->x) + 2,
(int)(p->y) + 2
);
pDC->LineTo(CPoint((int)p->x, (int)p->y));
p = p->next;
}
p = m_pHullHead;
pDC->LineTo(CPoint((int)p->x, (int)p->y));
}
p = m_pPtHead;
while (NULL != p)
{
pDC->Rectangle(
(int)(p->x) - 2,
(int)(p->y) - 2,
(int)(p->x) + 2,
(int)(p->y) + 2
);
// pDC->FillSolidRect(
// (int)(p->x) - 2,
// (int)(p->y) - 2,
// (int)(p->x) + 2,
// (int)(p->y) + 2,
// RGB(225, 0, 0)
// );
p = p->next;
}
}
不知道可以不，应该可以运行吧，你先试试
Ⅱ 一个关于melkman凸包算法的问题
Melkman只能用在简单多边形上。
Ⅲ 凸包的发展历史,急需，越详细越好，谢谢！！！！
⒈对于一个集合D，D中任意有限个点的线性组合的全体称为D的凸包。 ⒉对于一个集合D，所有包含D的凸集之交称为D的凸包。 可以证明，上述两种定义是等价的 概念
1 点集Q的凸包（convex hull）是指一个最小凸多边形，满足Q中的点或者在多边形边上或者在其内。右图中由红色线段表示的多边形就是点集Q={p0,p1,...p12}的凸包。 2 一组平面上的点，求一个包含所有点的最小的凸多边形，这就是凸包问题了。这可以形象地想成这样：在地上放置一些不可移动的木桩，用一根绳子把他们尽量紧地圈起来，并且为凸边形，这就是凸包了。编辑本段平面凸包求法常见求法
2.0 Graham's Scan法求解凸包问题
概念 凸包（Convex Hull）是一个计算几何（图形学）中的概念。用不严谨的话来讲，给定二维平面上的点集，凸包就是将最外层的点连接起来构成的凸多边型，它能包含点集中所有点的。严谨的定义和相关概念参见维基网络：凸包。 这个算法是由数学大师葛立恒（Graham）发明的，他曾经是美国数学学会（AMS）主席、AT&T首席科学家以及国际杂技师协会（IJA）主席。（太汗了，这位大牛还会玩杂技~） 问题 给定平面上的二维点集，求解其凸包。 过程 ⒈ 在所有点中选取y坐标最小的一点H，当作基点。如果存在多个点的y坐标都为最小值，则选取x坐标最小的一点。坐标相同的点应排除。然后按照其它各点p和基点构成的向量<H,p>；与x轴的夹角进行排序，夹角由大至小进行顺时针扫描，反之则进行逆时针扫描。实现中无需求得夹角，只需根据向量的内积公式求出向量的模即可。以下图为例，基点为H，根据夹角由小至大排序后依次为H，K，C，D，L，F，G，E，I，B，A，J。下面进行逆时针扫描。 ⒉ 线段<H,K>；一定在凸包上，接着加入C。假设线段<K,C>；也在凸包上，因为就H，K，C三点而言，它们的凸包就是由此三点所组成。但是接下来加入D时会发现，线段<K,D>；才会在凸包上，所以将线段<K,C>；排除，C点不可能是凸包。 ⒊ 即当加入一点时，必须考虑到前面的线段是否会出现在凸包上。从基点开始，凸包上每条相临的线段的旋转方向应该一致，并与扫描的方向相反。如果发现新加的点使得新线段与上线段的旋转方向发生变化，则可判定上一点必然不在凸包上。实现时可用向量叉积进行判断，设新加入的点为pn + 1，上一点为pn，再上一点为pn - 1。顺时针扫描时，如果向量<pn - 1,pn>；与<pn,pn + 1>；的叉积为正（逆时针扫描判断是否为负），则将上一点删除。删除过程需要回溯，将之前所有叉积符号相反的点都删除，然后将新点加入凸包。 在上图中，加入K点时，由于线段<H,K>；相对于<H,C>；为顺时针旋转，所以C点不在凸包上，应该删除，保留K点。接着加入D点，由于线段<K,D>；相对<H,K>；为逆时针旋转，故D点保留。按照上述步骤进行扫描，直到点集中所有的点都遍例完成，即得到凸包。 复杂度 这个算法可以直接在原数据上进行运算，因此空间复杂度为O⑴。但如果将凸包的结果存储到另一数组中，则可能在代码级别进行优化。由于在扫描凸包前要进行排序，因此时间复杂度至少为快速排序的O(nlgn）。后面的扫描过程复杂度为O(n），因此整个算法的复杂度为O(nlgn）。 ⒉1凸包最常用的凸包算法是Graham扫描法和Jarvis步进法。 对于一个有三个或以上点的点集Q，过程如下： 计算点集最右边的点为凸包的顶点的起点，如上图的P3点。 Do For i = 0 To 总顶点数 计算有向向量P3->Pi If 其余顶点全部在有向向量P3->Pi的左侧或右侧，则Pi点为凸包的下一顶点 Pi点加入凸包列表 GoTo 1 End If Next Exit Do 1: Loop 此过程执行后，点按极角自动顺时针或逆时针排序，只需要按任意两点的次序就可以了。而左侧或右侧的判断可以用前述的矢量点积性质实现。
特殊算法
⒉2求凸包有很多方法，不过最适合OIer和ACMer的估计还是Graham's Scan这个方法了。它的大致方法是这样的：首先，找到所有点中最左边的（y坐标最小的），如果y坐标相同，找x坐标最小的；以这个点为基准求所有点的极角（atan2(y-y0,x-x0）），并按照极角对这些点排序，前述基准点在最前面，设这些点为P[0]..P[n-1]；建立一个栈，初始时P[0]、P[1]、P[2]进栈，对于P[3..n-1]的每个点，若栈顶的两个点与它不构成“向左转”的关系，则将栈顶的点出栈，直至没有点需要出栈以后将当前点进栈；所有点处理完之后栈中保存的点就是凸包了。 如何判断A、B、C构成的关系不是向左转呢？如果b-a与c-a的叉乘小于0就不是。a与b的叉乘就是a.x*b.y-a.y*b.x。 上面的这个Graham的实现比我原来按照USACO里的课文写得简单多了，主要是它通过简单的预处理保证了P[0]、P[1]以及P[n-1]肯定是凸包里的点，这样就可以避免在凸包“绕回来”的时候繁杂的处理。
中心法
先构造一个中心点，然后将它与各点连接起来，按斜率递增的方法，求出凸包上部；再按斜率递减的方法，求出凸包下部。
水平法
从最左边的点开始，按斜率递增的方法，求出凸包上部；再按斜率递减的方法，求出凸包下部。水平法较中心法减少了斜率无限大的可能，减少了代码的复杂度。编辑本段代码例代码一
（在编辑器中将"_ "(下划线+空格）替换成两个空格即可编译； 注意要去掉开通的双字节中文空格，蛋疼的网络。）
Ⅳ 求大神详细讲解c/c++/pascal凸包算法
实这个算法是在一年前得某场比赛中临时雹肆抱佛脚学的，今天重新的来温习了一遍
如何来理解凸包？一组平面上的点，求一个包含所有点的最小的凸多边形，这就是凸包问题了。这可以形象地想成这样：在地上放置一些不可移动的木桩，用一根绳子把他们尽量紧地圈起来，这就是凸包了，网络中的这张图很生动+活泼+形象，所以你懂的锋肆族
好说完这个我们首先要来了解下极角排序和左转判定
极角排序：就是选取一个最左的点，按y最小，其次x最小来定义，接下来所有的点针对该点的射线，
按角度由小到大，若相同按距离由近到远来排序
左转判定：这个和叉积有关，对于向量p1(x1,y1),p2(x2,y2)如果x1*y2-x2*y1>0,则从p1到p2左转
我学的是Graham算法，那么接下来来介绍下该算法
（1）选取最下左的点P0
（2）计算出每个点相对于P0的角度和距离(利用这个来排序)排序
（3）设点数为n，将p[n-1]和p[0]入栈，判断点集合是否为一条直线（初银弊始k=2表示当前凸包的大小）
（4）i从1到n-1遍历，对于p[k-1],p[k-2],p[i]若满足左转，将p[i]压入栈
否则i--，k--
（5）k--,返回k表示凸包的点数
下面是我写的模板
int Polygon::Graham(Polygon &con){//别用自己做对象
int t=0,i;
Point tmp;
//先y最小再x最小
for(i=1;i<n;i++)if(p[i]<p[t])t=i;
swap(p[t],p[0]);
for(i=0;i<n;i++){
tmp=p[i]-p[0];
p[i].dis=tmp.Len2();
p[i].angle=atan2(tmp.y,tmp.x);
}
sort(p,p+n,_cmp);
//for(int i=0;i<n;i++)p[i].out();
//cout<<"***"<<endl;
int k=0;
con.p[k++]=p[n-1];
con.p[k++]=p[0];
if(Sig(p[1].angle-p[n-1].angle)==0)con.p[k++]=p[n-1];//凸包为一线段
else{
for(i=1;i<n;i++){
//con[k-1].out();
//con[k-2].out();
//p[i].out();
if(Sig(Cross(con.p[k-1],con.p[k-2],p[i]))>0)con.p[k++]=p[i];
else {i--;k--;}
//cout<<"---"<<endl;
//for(int j=0;j<k;j++)con[j].out();
//system("pause");
}
}
return con.n=--k;
}
/*
9
1 4
3 6
5 7
2 2
3 3
5 4
8 3
9 6
7 1
*/
摘自http://blog.csdn.net/foreverlin1204/article/details/6221986
Ⅳ matlab如何求大量数据中分布最多的范围及中心点。
楼主是不是想求出一个最小半径的圆，圆内包含所有的点？这个问题很有趣。
寻找这个圆的时候注意一下几点：
1.这个圆必然穿过图中某些靠外围的点，这样才是最小半径的圆。
2.几何中我们知道，三个点可以确定一个圆, 我们就是需要找出这三个点来.
算法如下：1.先求这些点对应的凸包，已经有现成的算法。
2.生成凸包后，在看凸包上哪三点确定的圆可以包含凸包。
当然如果楼主讨论的不是以上所述，而是模式分类的话，建议看看数据分类方法。可以搜索关键字：Gaussian mixtrual model, expectation-maximization algorithm 和 k-mean algorithm 学习下相关的知识。
Ⅵ C++ 散点聚类凸包相交问题
这个问题是衫陵可以做的，首先要确定的是两类点有两个凸包，需要分别求解。这个是二维点集生成平面图形的问题，解决你给的这个问题的方法有很多。我给个思路，在搏枯凸包（Convex Hull）的生成过程中，采用的是从某一个基点（比如最左下角的点），将所有其他点与该点连线的斜率均计算出来，按照一定的顺序（比如斜率从小到大或银戚的顺序）将各个点连接起来，这个是原始的凸包算法，这个算法中只考虑了斜率，没考虑两个点距离。因此，你这个问题需要把两点间距离考虑进来，把距离d和斜率k综合考虑。具体实现过程你可以自己完成了，顺便多说一句，最好把d设置成一个可变化的量，比如当寻找到的下一个点是个错误的点，那么就把d变化为原来的1.2倍再尝试。
Ⅶ origin怎么找两条线距离最远的点
这是一个计算几何学问题，可以使用一些算法来解决。以下是其中一种可能的解决方案：
假设有运冲n个点，可以首先使用暴力方法找到所有点对之间的距离毁漏，并记录最大距离d。然后，从这些点中任选两个距离为d的点作为起始点。
接下来，将剩余的点分别与这两个点计算距离，如果当前点到距离更远的那个点的距离比当前最大距离更大，则更新最大距离，并将该点作为新的终点。重复该步骤直到遍历完所有的点，旁余歼即可找到两条线距离最远的点。
上述算法的时间复杂度为O(n^2)，在数据量较小的情况下可行。但如果数据量很大，可以考虑使用优化算法，如kd-tree或Voronoi图等，以降低时间复杂度
Ⅷ 跪求matlab 凸包算法 算多边形面积
Matlab算法
x和y代表你画的散点的横纵坐标向量，当然肯定是等长度的。
plot(x,y, '*', 'markersize',10);
dt = DelaunayTri(x,y);
k = convexHull(dt);
plot(x,y, '.', 'markersize',10);
hold on;
plot(x(k), y(k), 'r');
Perimeter = sqrt(diff(x(k))*diff(x(k))'+ diff(y(k))*diff(y(k))'); % 周长
area=abs(trapz(x(k),y(k)))%面积
就是先把散点的区域用凸多边形画出来，然后再求多边形的面积和周长。
Ⅸ 如何用python实现凸包算法
#include #include #include using namespace std; typedef double Type; // 注意下面的fabs(). const int maxn = 1005; const double EPS = 1e-8; const double Pi = acos(-1.0); struct Point { Type x, y; Point () {} Point (Type & x
Ⅹ java凸包算法
源码一 JarvisMarch java
package nvex;
import static java lang Math abs;
import java util Iterator;
import java util LinkedList;
import java util List;
public class JarvisMarch {
private int count;
public int getCount() {
扮亏return count;
}
public void setCount(int count) {
unt = count;
}
private static int MAX_ANGLE = ;
private double currentMinAngle = ;
穗缺谈private List<Point> hullPointList;
private List<Integer> indexList;
private PointFactory pf;
private Point[] ps;
public Point[] getPs() {
return ps;
}
private int firstIndex;
public int getFirstIndex() {
return firstIndex;
}
public JarvisMarch() {
this( );
}
public JarvisMarch(int count) {
pf = PointFactory getInstance(count);
猜碰initialize();
}
public JarvisMarch(int[] x int[] y) {
pf = PointFactory getInstance(x y);
initialize();
}
private void initialize() {
hullPointList = new LinkedList<Point>();
indexList = new LinkedList<Integer>();
firstIndex = pf getFirstIndex();
ps = pf getPoints();
addToHull(firstIndex);
}
private void addToHull(int index) {
indexList add(index);
hullPointList add(ps[index]);
}
public int calculateHull() {
for (int i = getNextIndex(firstIndex); i != firstIndex; i = getNextIndex(i)) {
addToHull(i);
}
showHullPoints();
return ;
}
private void showHullPoints() {
Iterator<Point> itPoint = erator();
Iterator<Integer> itIndex = erator();
Point p;
int i;
int index = ;
System out println( The hull points is: > );
while (itPoint hasNext()) {
i = itIndex next();
p = itPoint next();
System out print(i + :( + p getX() + + p getY() + ) );
index++;
if (index % == )
System out println();
}
System out println();
System out println( **************************************************************** );
System out println( The count of all hull points is + index);
}
public int getNextIndex(int currentIndex) {
double minAngle = MAX_ANGLE;
double pseudoAngle;
int minIndex = ;
for (int i = ; i < ps length; i++) {
if (i != currentIndex) {
pseudoAngle = getPseudoAngle(ps[i] getX() ps[currentIndex] getX()
ps[i] getY() ps[currentIndex] getY());
if (pseudoAngle >= currentMinAngle && pseudoAngle < minAngle) {
minAngle = pseudoAngle;
minIndex = i;
} else if (pseudoAngle == minAngle){
if((abs(ps[i] getX() ps[currentIndex] getX()) >
abs(ps[minIndex] getX() ps[currentIndex] getX()))
|| (abs(ps[i] getY() ps[currentIndex] getY()) >
abs(ps[minIndex] getY() ps[currentIndex] getY()))){
minIndex = i;
}
}
}
}
currentMinAngle = minAngle;
return minIndex;
}
public double getPseudoAngle(double dx double dy) {
if (dx > && dy >= )
return dy / (dx + dy);
if (dx <= && dy > )
return + (abs(dx) / (abs(dx) + dy));
if (dx < && dy <= )
return + (dy / (dx + dy));
if (dx >= && dy < )
return + (dx / (dx + abs(dy)));
throw new Error( Impossible );
}
}
源码二 Point java
package nvex;
public class Point {
// 定义点的x y坐标 之所以是int类型 是为了日后可以在计算机屏幕上进行可视化
private int x;
private int y;
// x y的get方法
public int getX() {
return x;
}
public int getY() {
return y;
}
// 定义点到屏幕边缘的距离
private static double PADDING = ;
// 点在屏幕中的范围
private static double POINT_RANGE = ( PADDING * );
// 默认构造方法 产生随机点
public Point() {
this x = (int) ((Math random() * POINT_RANGE) + PADDING);
this y = (int) ((Math random() * POINT_RANGE) + PADDING);
}
// 带参构造方法 可以实现手动输入固定点
public Point(int x int y) {
this x = x;
this y = y;
}
// 覆写hashCode()和equals()方法 实现比较和Hash
@Override
public int hashCode() {
final int prime = ;
int result = ;
result = prime * result + x;
result = prime * result + y;
return result;
}
@Override
public boolean equals(Object obj) {
Point other = (Point) obj;
if ((x == other x) && (y == other y))
return true;
return false;
}
}
源码三 PointFactory java
package nvex;
public class PointFactory {
/**
* 单例模式 大批量产生Point 也可以手动产生Point
*/
private Point[] points = null;
private int newIndex;
private int firstIndex = ;
public Point[] getPoints() {
return points;
}
public int getFirstIndex() {
return firstIndex;
}
public static PointFactory getInstance() {
return new PointFactory();
}
public static PointFactory getInstance(int count) {
return new PointFactory(count);
}
public static PointFactory getInstance(int[] x int[] y) {
return new PointFactory(x y);
}
private PointFactory() {
this( );
}
private PointFactory(int count) {
points = new Point[count];
for (int i = ; i < count; i++) {
points[i] = new Point();
newIndex = i;
validatePoints();
}
firstIndex = getFirstPoint();
}
public PointFactory(int[] x int[] y) {
points = new Point[y length];
for (int i = ; i < y length; i++) {
points[i] = new Point(x[i] y[i]);
}
firstIndex = getFirstPoint();
}
private void validatePoints() {
for(int i = ; i < newIndex; i++) {
if(points[i] equals(points[newIndex])) {
points[newIndex] = new Point();
validatePoints();
}
}
}
public int getFirstPoint() {
int minIndex = ;
for (int i = ; i < points length; i++) {
if (points[i] getY() < points[minIndex] getY()) {
minIndex = i;
} else if ((points[i] getY() == points[minIndex] getY())
&& (points[i] getX() < points[minIndex] getX())) {
minIndex = i;
}
}
return minIndex;
}
}
源码四 Test java（主函数）
package nvex;
public class Test {
public static void main(String[] args) {
long start = System currentTimeMillis();
JarvisMarch j = new JarvisMarch( );
Point[] points = j getPs();
int firstIndex = j getFirstIndex();
// for (int i = ; i < points length; i++) {
// System out print(i + :( + points[i] getX() + + points[i] getY() + ) );
// if((i+ ) % == ) {
// System out println();
// }
// }
// System out println();
// System out println( ***************************************************************** );
System out println( the first point is: + firstIndex + :( +
points[firstIndex] getX() + + points[firstIndex] getY() + ) );
System out println( ***************************************************************** );
j calculateHull();
System out println( The total running time is + (System currentTimeMillis() start) + millis );
}
lishixin/Article/program/Java/hx/201311/26948