- 浏览: 41348 次
文章分类
- 全部博客 (28)
- java (28)
- 样式和主题 (1)
- 项目创建 (1)
- Java字节码(.class文件)格式详解(一) (1)
- 一次定时任务 (1)
- 数组最大连续子序列和 (1)
- jquery-ajax (1)
- ORACLE中一个字符占多少字节 (1)
- Java网络编程 (1)
- Melkman凸包算法的Java实现 (1)
- ios UITableViewCell 文字缩进 (1)
- Websphere6.1静默安装(转) (1)
- newInstance() 和 new 有什么区别? (1)
- 项目管理规范 RUP管理实施中角色的划分 (1)
- 做了几天关于地理信息系统的软件测试工作 (1)
- 一边播放RM文件 一边播放相应的PPT文件 编程实现 (1)
- iPhone消息推送机制实现与探讨 (1)
- 详解C#中访问私有成员 (1)
- linux命令 (1)
- length & substr (1)
- javascript图片库 (1)
- remount failed: Operation not permitted (1)
- iBATIS报ORA-01745: 无效的主机/绑定变量名 异常 (1)
- Java NIO ByteBuffer (1)
- 【转】深入浅出Node.js 持续更新中 (1)
- gson (1)
- Jsp文件中播发视频文件 (1)
- pycetr: 从html文档中提取文档内容 (1)
- [jquery]IE与Chrome下text()方法获取textarea值不一致 (1)
最新评论
-
ygsilence:
factory是什么?
newInstance() 和 new 有什么区别? -
Simon.C:
清了那些多余的HTML标签吧……
Java NIO ByteBuffer -
eagle59:
不错,!希望下次可以排好版。
newInstance() 和 new 有什么区别? -
liudeh_009:
理解得不错
newInstance() 和 new 有什么区别?
坐标对象:
?
public class Point{ private float x; //X坐标 private float y; //Y坐标 private double arCos; //与P0点的角度 public float getX() { return x; } public void setX(float x) { this.x = x; } public float getY() { return y; } public void setY(float y) { this.y = y; } public double getArCos() { return arCos; } public void setArCos(double arCos) { this.arCos = arCos; } }
?算法与测试:
package Melkman; import java.io.BufferedReader; import java.io.File; import java.io.FileNotFoundException; import java.io.FileReader; import java.io.IOException; import java.util.ArrayList; import java.util.List; /** * Melkman求凸包算法 * @author zl */ public class Melkman { private Point[] pointArray;//坐标数组 private final int N;//数据个数 private int D[]; // 数组索引 public Melkman(List<Point> pList) { this.pointArray = new Point[pList.size()]; N = pList.size(); int k = 0; for (Point p : pList) { pointArray[k++] = p; } D = new int[2 * N]; } /** * 求凸包点 * * @return 所求凸包点 */ public Point[] getTubaoPoint() { // 获得最小的Y,作为P0点 float minY = pointArray[0].getY(); int j = 0; for (int i = 1; i < N; i++) { if (pointArray[i].getY() < minY) { minY = pointArray[i].getY(); j = i; } } swap(0, j); // 计算除第一顶点外的其余顶点到第一点的线段与x轴的夹角 for (int i = 1; i < N; i++) { pointArray[i].setArCos(angle(i)); } quickSort(1, N - 1); // 根据所得到的角度进行快速排序 int bot = N - 1; int top = N; D[top++] = 0; D[top++] = 1; int i; for (i = 2; i < N; i++) {// 寻找第三个点 要保证3个点不共线!! if (isLeft(pointArray[D[top - 2]], pointArray[D[top - 1]], pointArray[i]) != 0) break; D[top - 1] = i; // 共线就更换顶点 } D[bot--] = i; D[top++] = i; // i是第三个点 不共线!! int t; if (isLeft(pointArray[D[N]], pointArray[D[N + 1]], pointArray[D[N + 2]]) < 0) { // 此时队列中有3个点,要保证3个点a,b,c是成逆时针的,不是就调换ab t = D[N]; D[N] = D[N + 1]; D[N + 1] = t; } for (i++; i < N; i++) { // 如果成立就是i在凸包内,跳过 //top=n+3 bot=n-2 if (isLeft(pointArray[D[top - 2]], pointArray[D[top - 1]], pointArray[i]) > 0 && isLeft(pointArray[D[bot + 1]], pointArray[D[bot + 2]], pointArray[i]) > 0) { continue; } //非左转 则退栈 while (isLeft(pointArray[D[top - 2]], pointArray[D[top - 1]], pointArray[i]) <= 0) { top--; } D[top++] = i; //反向表非左转 则退栈 while (isLeft(pointArray[D[bot + 1]], pointArray[D[bot + 2]], pointArray[i]) <= 0) { bot++; } D[bot--] = i; } // 凸包构造完成,D数组里bot+1至top-1内就是凸包的序列(头尾是同一点) Point[] resultPoints = new Point[top - bot - 1]; int index = 0; for (i = bot + 1; i < top - 1; i++) { System.out.println(pointArray[D[i]].getX() + "," + pointArray[D[i]].getY()); resultPoints[index++] = pointArray[D[i]]; } return resultPoints; } /** * 判断ba相对ao是不是左转 * * @return 大于0则左转 */ private float isLeft(Point o, Point a, Point b) { float aoX = a.getX() - o.getX(); float aoY = a.getY() - o.getY(); float baX = b.getX() - a.getX(); float baY = b.getY() - a.getY(); return aoX * baY - aoY * baX; } /** * 实现数组交换 * * @param i * @param j */ private void swap(int i, int j) { Point tempPoint = new Point(); tempPoint.setX(pointArray[j].getX()); tempPoint.setY(pointArray[j].getY()); tempPoint.setArCos(pointArray[j].getArCos()); pointArray[j].setX(pointArray[i].getX()); pointArray[j].setY(pointArray[i].getY()); pointArray[j].setArCos(pointArray[i].getArCos()); pointArray[i].setX(tempPoint.getX()); pointArray[i].setY(tempPoint.getY()); pointArray[i].setArCos(tempPoint.getArCos()); } /** * 快速排序 * * @param top * @param bot */ private void quickSort(int top, int bot) { int pos; if (top < bot) { pos = loc(top, bot); quickSort(top, pos - 1); quickSort(pos + 1, bot); } } /** * 移动起点,左侧为小,右侧为大 * * @param top * @param bot * @return 移动后的位置 */ private int loc(int top, int bot) { double x = pointArray[top].getArCos(); int j, k; j = top + 1; k = bot; while (true) { while (j < bot && pointArray[j].getArCos() < x) j++; while (k > top && pointArray[k].getArCos() > x) k--; if (j >= k) break; swap(j, k); } swap(top, k); return k; } /** * 角度计算 * * @param i 指针 * @return */ private double angle(int i) { double j, k, m, h; j = pointArray[i].getX() - pointArray[0].getX(); k = pointArray[i].getY() - pointArray[0].getY(); m = Math.sqrt(j * j + k * k); // 得到顶点i 到第一顶点的线段长度 if (k < 0) j = (-1) * Math.abs(j); h = Math.acos(j / m); // 得到该线段与x轴的角度 return h; } public static void main(String args[]) { // File file = new File("G:/yl.txt"); File file = new File("G:/data.txt"); BufferedReader br = null; try { br = new BufferedReader(new FileReader(file)); } catch (FileNotFoundException e) { e.printStackTrace(); } List<Point> pointList = new ArrayList<Point>(); String str = null; try { str = br.readLine(); } catch (IOException e) { e.printStackTrace(); } while (str != null) { String[] s = str.split("\\t", 2); float x = Float.parseFloat(s[0].trim()); float y = Float.parseFloat(s[1].trim()); Point p = new Point(); p.setX(x); p.setY(y); // System.out.println("文件数据:" + x + ", " + y); pointList.add(p); try { str = br.readLine(); } catch (IOException e) { e.printStackTrace(); } } System.out.println("数据个数:" + pointList.size()); Melkman m = new Melkman(pointList); m.getTubaoPoint(); } }
?
发表评论
-
[jquery]IE与Chrome下text()方法获取textarea值不一致
2012-02-08 12:33 1359[size=small;]<br>[/si ... -
pycetr: 从html文档中提取文档内容
2012-02-07 13:39 945html文档中通常夹杂着各种广告,相关性链接等,提取正 ... -
Jsp文件中播发视频文件
2012-02-04 15:54 929详情请转至:↓ http://blog.sina.co ... -
gson
2012-02-04 13:09 3870最近的项目,接口传输格式用JSON,试用了一下goog ... -
【转】深入浅出Node.js 持续更新中
2012-02-03 14:09 1024深入浅出Node.js(一):什么是Node.js h ... -
Java NIO ByteBuffer
2012-02-03 12:13 1568<span class="Apple- ... -
iBATIS报ORA-01745: 无效的主机/绑定变量名 异常
2012-02-01 10:09 5315今天发现发现线上报出一个异常: <br /> ... -
remount failed: Operation not permitted
2012-01-31 15:28 2087<span style="font-s ... -
javascript图片库
2012-01-11 13:58 799今天做了一个点击一个链接就在相应位置出现图片的DEMO ... -
length & substr
2011-12-21 13:08 853oracle中substr函数的用法 In ora ... -
linux命令
2011-12-21 12:19 953本章主要介绍Linux 的常用命令,其中主要有 文件 ... -
详解C#中访问私有成员
2011-12-20 11:29 829首先我必须承认访问一个类的私有成员不是什么好做法。大 ... -
iPhone消息推送机制实现与探讨
2011-12-20 10:24 1456最近两天在研究ios的消息推送机制。研究这个东西,还是 ... -
一边播放RM文件 一边播放相应的PPT文件 编程实现
2011-12-16 16:17 997应用情景:<br> 在制作网络课件的过程中 ... -
做了几天关于地理信息系统的软件测试工作
2011-12-15 16:59 981又忙活了几天。每天早早的就起床,到软件测试所在地,然后 ... -
项目管理规范 RUP管理实施中角色的划分
2011-12-15 09:39 770</span></font>& ... -
newInstance() 和 new 有什么区别?
2011-12-12 14:04 1548在初始化一个类, ... -
Websphere6.1静默安装(转)
2011-12-09 15:59 877<span style="color: ... -
ios UITableViewCell 文字缩进
2011-12-08 17:34 1201【前提】 UITableViewCell 原 ... -
Java网络编程
2011-12-07 16:31 849[img][/img]<ol> & ...
相关推荐
// 实现算法步骤... } } ``` **相关文档资料** 在学习和实现Melkman凸包算法时,相关文档资料是非常宝贵的资源。它们通常包括算法的详细解释、伪代码、示例以及可能的优化技巧。你可以查找学术论文、专业书籍...
poj1113 melkman算法求凸包, 使用STL
凸包melkman算法cpp实现,通过poj1113题测试
本程序是基于C语言的凸包算法(Graham)实现,能够直接编译运行,计算凸包的点为随机生成。该程序为控制台应用程序,输出结果有凸包顶点坐标、以及一个50*50的矩阵,其中0表示空白点,1表示随机生成的点集,2表示...
本项目“NX8_hull.zip”涉及到的是利用C#实现的一个特定算法,即Melkman算法,该算法主要用于计算二维几何对象的凸包(Convex Hull)。在计算机图形学、地理信息系统和机器学习等领域,凸包问题是非常重要的基础问题...
Melkman的凸包算法是一种高效计算简单多边形链(或简单多边形)的凸包的线性时间算法。该算法由Arieh D. Melkman提出,并基于前人工作的基础上发展而来。在计算机图形学、几何建模等领域有着广泛的应用。 #### 基本...
课程涵盖礼品包装(Jarvis March)、Graham Scan、Quickhull、Monotone Chain、Melkman、Sklansky、Kirkpatrick & Seidel(终极版),最后是 Chan 的算法。 Chan 算法(以其发明者 Timothy M. Chan 命名)是一种...
10. **凸包MelkMan算法的实现**:专门针对动态更新的点集寻找凸包的一种高效算法。 11. **凸多边形的直径**:即凸多边形中最远两点间的距离,可以通过扫描线算法求解。 12. **求凸多边形的重心**:可以通过计算所有...
Melkman 的算法可视化找到简单多边形凸包的最佳方法的动态可视化。 要在本地运行,请执行npm install && browserify melkman.js -o bundle.js && wget http://d3js.org/d3.v3.js并打开您喜欢的Web服务器。贡献如果你...
11. **凸包MelkMan算法的实现**: - 特别适用于动态凸包问题。 12. **凸多边形的直径**: - 指凸多边形中最远两点之间的距离。 13. **求凸多边形的重心**: - 计算多边形顶点坐标的平均值作为重心位置。 以上是对...
凸包算法是计算几何中的一个重要工具,它的作用是找到一组点的最小凸包,从而简化问题的复杂度,常见的算法有Graham扫描法和Melkman算法,这些都需要处理三点共线等异常情况。 计算几何在ACM竞赛中的应用不仅限于纯...
3. **凸包算法**:凸包是包围一个几何对象的最小凸集,常用算法有Graham扫描算法和Melkman算法,用于降低复杂度。 4. **线段相交**:判断两条线段是否相交,需要处理各种边界和特殊情况。 5. **多边形的相交**:在三...