凸包:令S是平面上的一个点集,封闭S中所有顶点的最小凸多边形,称为S的凸包。
如下图中由红线段表示的多边形就是点集Q={p0,p1,...p12}的凸包。
算法代码:
import java.util.*;
class Line {//线
Point p1, p2;
Line(Point p1, Point p2) {
this.p1 = p1;
this.p2 = p2;
}
}
class Point{//点
int x;
int y;
}
public class BaoLiTuBao {
List<Point> pts = null;//点集
List<Line> lines = new ArrayList<Line>();//点集pts的凸包
public void setPointList(List<Point> pts) {
this.pts = pts;
}
public List<Line> eval() {
lines.clear();
if (pts == null) { return lines; }
int n = pts.size();
int a, b, c, cc, l, r;
for (int i = 0; i < n; i++) {
for (int j = i+1; j < n; j++) {//穷举点集中任意两点组成的直线ax+by=c
a = pts.get(j).y - pts.get(i).y;//
b = pts.get(i).x - pts.get(j).x;
c = pts.get(i).x * pts.get(j).y -pts.get(i).y * pts.get(j).x;
l = r = 0;
int k;
for (k = 0; k < n; k++) {//穷举点集中的每一点
cc = a * pts.get(k).x + b * pts.get(k).y;
if (cc > c) l++;
else if (cc < c) r++;
if (l * r != 0) break;//直线两侧都有点,
}
if (k == n) {//凸包中添加一条边
lines.add(new Line(pts.get(i), pts.get(j)));
}
}
}
return lines;
}
}
未完待续。。。
- 大小: 7.1 KB
- 大小: 32.3 KB
分享到:
相关推荐
在计算机科学中,凸包问题是一项基础且重要的算法问题,特别是在几何计算和图形学领域。简单来说,给定一组在二维平面上的点,凸包问题是找到这些点构成的最小凸多边形,使得所有点都在这个多边形内或者在其边界上。...
蛮力法,也称为暴力法,是一种直接、直观的算法设计策略,通常用于解决简单问题或作为更复杂算法的基础。在求解凸包问题时,蛮力法的基本思路是遍历所有可能的点组合,找出能够形成凸包的点序列。 具体步骤如下: ...
在计算机科学领域,凸包问题是几何算法中的一个重要概念,它涉及到如何找到一组点集的最小边界,这个边界包围了所有点并且是凸的。在这个问题中,"凸包"指的是一个多边形,其包含了给定点集且任何两点之间的线段都在...
1. KMP算法:一种高效的字符串匹配算法,通过预处理构造部分匹配表避免冗余比较。 2. exKMP:扩展KMP算法,进一步优化了匹配过程。 3. AC自动机:用于字符串搜索的有限状态自动机,能够同时匹配多个模式串。 4. 后缀...
《ACM算法教程:算法设计PPT》是针对ACM(国际大学生程序设计竞赛)算法训练的一份宝贵资源,旨在帮助学习者提升算法设计能力和编程技能。这份教程以PPT的形式,深入浅出地讲解了ACM竞赛中常用且重要的算法思想与...
- **知识点**: 暴力算法。 - **描述**: 检查身份证号码的有效性。 - **难度级别**: 入门级。 - **解题思路**: 通过枚举检查所有可能的情况。 31. **1037 Guardian of Decency 图论:匈牙利算法求二分图的最大...
**割平面法** 是线性规划的一种扩展,它通过添加非基变量的不等式约束(割平面)来逐步逼近整数解的凸包。在MATLAB中,我们可以利用优化工具箱中的连续优化算法配合启发式策略来构造和添加割平面。首先,将整数规划...
10. **模拟和暴力求解**:在没有找到更优解法时,直接枚举或模拟所有可能的情况也是解决问题的一种方法,虽然效率较低,但在一些限制条件下仍能给出正确答案。 通过阅读《算法艺术与信息学竞赛》并结合习题提示,...
1. **枚举**:枚举是一种暴力求解的方法,尝试所有可能的解,适用于解空间有限的问题,例如`poj1753`和`poj2965`。 2. **贪心**:贪心策略是在每一步选择局部最优解,期望得到全局最优解。例如`poj1328`、`poj2109`...
2. **凸包问题**:找到凸包的多种算法,如Graham扫描法等。 3. **二维计算几何相关**:涉及点、线、多边形等问题。 4. **三维计算几何相关**:更复杂的几何问题。 5. **半平面交、旋转卡壳、三角剖分**:用于解决...
标题“brute-force-convex-hull”指向的是一个与计算几何相关的话题,具体来说是关于求解凸包的一种算法——暴力求解法。在计算几何中,凸包是一组点集中的最小边界,该边界将所有点包含在内且是凸的。这个话题可能...
通过Graham扫描法,可以在线性时间复杂度内求解,这是一种非常实用且效率高的算法,对于处理涉及几何形状的边界问题十分有效。 接着,退火算法被提及,它在解决优化问题时用于寻找近似全局最优解。尽管其精确性依赖...
素数打表是快速判断一个数是否为素数的常用手段,而位运算在优化算法中起到关键作用,如O(n)求解全部组合数。字符串处理中的O(n)求最长回文子串是字符串算法中的经典问题。 最后,LCA(最近公共祖先)是图论中的...