Convex hull: the smallest polygon that covers all the points in the given set.
Application: Farthest pair problem, shortest Path across the boundary.
Algorithm: Find the point with the lowest y-coordinates p, then iterate through all the points in the order of polar-angle relative to the p. Check if they can form a counter clock wise angle with the previous point, if so include it in the context hull, otherwise discard it. There is a video clip explaining the convex hull algorithm
https://www.youtube.com/watch?v=0HZaRu5IupM
import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; import java.util.Stack; public class ConvexHull { //assume no duplicate points public static void main(String [] args) { ArrayList<Point> points = new ArrayList<Point> (); points.add(new Point(0, 0)); points.add(new Point(1, 1)); points.add(new Point(3, 10)); points.add(new Point(8, 7)); points.add(new Point(11, 8)); points.add(new Point(12, 1)); ArrayList<Point> result = new ArrayList<Point>(); //check if there are more than three points in the array if (points.size() < 3) { System.out.println("Too few points"); return; } //find the point with the lowest y int oIndex = 0; for (int i = 1; i < points.size(); i++) { if (points.get(i).y < points.get(oIndex).y) oIndex = i; } //remove the origin points and put it into the stack final Point origin = points.get(oIndex); points.remove(oIndex); //stack that we use to iterate through the Stack<Point> hullStack = new Stack<Point>(); hullStack.push(origin); //put origin point in stack //sort the points according to their polarity relative to origin Collections.sort(points, new Comparator<Point>() { @Override public int compare(Point p1, Point p2) { float polar1 = getPolar(origin, p1); float polar2 = getPolar(origin, p2); if (polar1 > polar2) return -1; else if (polar1 < polar2) return 1; return 0; } }); //add origin to as the last element points.add(origin); for (Point p : points) { Point pre = hullStack.pop(); while(!hullStack.isEmpty() && !isLeftTurn(hullStack.peek(), pre, p)) { pre = hullStack.pop();//discard the pre and take new top of the stack as pre } hullStack.push(pre); hullStack.push(p); } //remove the duplicate origin hullStack.pop(); while(!hullStack.isEmpty()) { result.add(hullStack.pop()); } } private static float getPolar(Point start, Point end) { //get the cosin between end and start float r = ((end.x - start.x)*(end.x - start.x) + (end.y - start.y)*(end.y - start.y)); return (float) ((end.x - start.x)/Math.pow(r, 0.5)); } private static boolean isLeftTurn(Point a, Point b, Point c) { if ((c.y - a.y)/(c.x - a.x) > (b.y - a.y)/(b.x - a.x)) return true; return false; } }
The above program shows an way get a convex hull from a set of points.
The running time is dominated by the sorting so it is nlogn.
Two things need to pay attention:
1. the original point is the one with the lowest y coordinate. So all the other point was above it. We want the points to be sorted according to the polar angle relative to the original point, in the order of counterclockwise. So we should use cosin which on the uppper part of coordinate system, decrease in the order of counterclock direction.
2. To find out whether we make a left (counter clock wise) turn in a three point a->b->c, there is a simple way. We should check if (c.y – a.y)*(b.x – a.x) – (b.y – a.y)*(c.x – a.x). If it is equals to 0, then a, b and c are on the same line. if positive, it is making a left turn, otherwise it is making a right turn.
From:
https://hellosmallworld123.wordpress.com/2014/08/01/convex-hull-algorithm/
相关推荐
Melkman的凸包算法 We describe an algorithm, due to Melkman (and based on work by many others), which computes the convex hull of a simple polygonal chain (or simple polygon) in linear time.
此代码提供了计算一组点的直线度的可能性,这些点是从 excel 文件导入的。 它使用凸包算法
An in-place algorithm is one in... In this paper we describe three in-place algorithms for computing the convex hull of a planar point set. All three algorithms are optimal, some more so than others. . .
C++ Implementation of the convex-hull algorithm for a list of 2D points. Based on the quick-hull algorithm.
Machine learning algorithms, especially support vector machines (SVMs), were ... For non-separable problems, it needs to perform appropriate convex hull transformation, i.e., so-called scaled convex hu
凸包 这个程序是我为 CSCE 411: Design and Analysis of Algorithms 开发的。 它使用 Graham's Scan 或 Jarvis' March 计算一组随机生成的点的凸包。... java ConvexHull <points> <iterations> <display> <algorithm>
Convex Hull Heaps Algorithm Heaps Algorithm Iterative Inversions Kth Order Statistic Max Difference Pair Max Subarray Sum Mergesort Peak Power 最近的一对点 凸包 堆算法 堆算法迭代 第 K...
该网站可用于可视化多种算法,包括排序,寻路和ConvexHull。 您可以在这里访问它: : 演算法 排序 选择排序 合并排序 快速排序 寻找路径 Dijkstra的算法 凸包 格雷厄姆的扫描 安装 在计算机上安装Node 从克隆此...
17.2 Convex Hull 17.3 Triangulation 17.4 Voronoi Diagrams 17.5 Nearest Neighbor Search 17.6 Range Search 17.7 Point Location 17.8 Intersection Detection 17.9 Bin Packing 17.10 Medial-Axis ...
自己学习计算几何已经是研究生时候的事情,课程更偏向于对诸如Convex hull, Delaunay triangulation, Voronoi diagram等问题的formulation, algorithm design和complexity analysis,几乎没有涉及任何实际的应用场景...
英文第二版 目录 . . . . . . . ....2.8 War Story: Mystery of the Pyramids ....2.9 Advanced Analysis (*) ....2.10 Exercises ....3.1 Contiguous vs....3.2 Stacks and Queues ....3.3 Dictionaries ....3.4 Binary Search Trees ....
:tear-off_calendar: 2020....│ ├── ConvexHull.swift │ └── KMeans.swift ├──:file_folder: CoreData │ ├── CoreDataContainer.swift │ ├── CoreDataLayer.swift │ └──:file_folder: Mod
33.3 Finding the convex hull 1029 33.4 Finding the closest pair of points 1039 34 NP-Completeness 1048 34.1 Polynomial time 1053 34.2 Polynomial-time verification 1061 34.3 NP-completeness and ...
本文包括图像分割、特征提取和分类等图像处理过程,用于胎儿的异常检测。 它使用凸包算法来分割图像。 凸包集形成一个最小的凸多边形,其中包含所有点集。我们项目的主要目的是使用超声图像检测胎儿的异常。...
33.3 Finding the convex hull 1029 33.4 Finding the closest pair of points 1039 34 NP-Completeness 1048 34.1 Polynomial time 1053 34.2 Polynomial-time verification 1061 34.3 NP-completeness and ...
33.2 Determining whether any pair of segments intersects 1021 33.3 Finding the convex hull 1029 33.4 Finding the closest pair of points 1039 34 NP-Completeness 1048 34.1 Polynomial time 1053 34.2 ...
33.3 Finding the convex hull 947 33.4 Finding the c1osest pair of points 957 34 NP-Completeness 966 34.1 Polynomial time 971 34.2 Polynomial-time verification 979 34.3 NP-completeness and reducibility...
33.3 Finding the convex hull 1029 33.4 Finding the closest pair of points 1039 34 NP-Completeness 1048 34.1 Polynomial time 1053 34.2 Polynomial-time verification 1061 34.3 NP-completeness and ...
Scaling and seam carving are commonly used algorithm in image resizing, but scaling is not suitable for the case that the resize ratio is not uniformity, seam carving will also has a bad effect on ...