http://www.algorithmist.com/index.php/Monotone_Chain_Convex_Hull.java
/* This is an implementation of Monotone Chain Convex Hull algorithm in Java.
* It takes O( NlogN ) in sorting & O(N) in actual convex hull finding for N points.
* Author - Nikhil Garg
* Email - nikhilgarg28@gmail.com
* This code is not heavily commented. To understand it, refer to pseudocode.
*/
class Point implements Comparable<Point>
{
int x,y;
Point(int x, int y)
{
this.x = x;
this.y = y;
}
// sort first on x then on y
public int compareTo(Point other)
{
if( x == other.x)
return y - other.y;
else
return x - other.x;
}
// cross product of two vectors
public int cross( Point p)
{
return x * p.y - y * p.x;
}
// subtraction of two points
public Point sub( Point p)
{
return new Point( x - p.x, y - p.y );
}
}
public Point[] findHull( Point[] points)
{
int n = points.length;
Arrays.sort( points);
Point[] ans = new Point[2 * n]; // In between we may have a 2n points
int k = 0;
int start = 0; // start is the first insertion point
for(int i = 0; i < n; i ++) // Finding lower layer of hull
{
Point p = points[i];
while( k - start >= 2 && p.sub( ans[k-1] ).cross(p.sub( ans[k-2] ) ) > 0 )
k--;
ans[k++] = p;
}
k--; // drop off last point from lower layer
start = k ;
for(int i = n-1 ; i >= 0 ; i --) // Finding top layer from hull
{
Point p = points[i];
while( k - start >= 2 && p.sub( ans[k-1] ).cross(p.sub( ans[k-2] ) ) > 0 )
k--;
ans[k++] = p;
}
k--; // drop off last point from top layer
Point [] ret = new Point[k]; // ret would contain our convex hull to be returned.
for(int i = 0 ; i < k; i++)
ret[i] = ans[i];
return ret;
}
分享到:
相关推荐
前端开源库-monotone-chain-convex-hull单调链凸壳,单调链凸壳算法
信息安全_数据安全_Error_Detection_in_Monotone_Span 漏洞分析 信息保护 内网安全 移动安全 安全编码
Efficient Finite Abstraction of Mixed Monotone Systems.
高级java笔试题 个人博客 c++ c++primer - c++primer顺序容器与关联容器的一些用法 effective c++ - effective c++笔记归纳 Data Structures and Algorithm Analysis 数据结构与一些算法,来自算法导论,数据结构与...
Contents 1 Introduction 1 1.1 Majorization Theory 1 1.2 Matrix-Monotone Functions 3 1.3 Classification and Organization 4 ...6.2 Convex Optimization 134 7 Acknowledgments 141 References
Monotone
Xu jinchao A monotone finite element scheme for convection-diffusion equations
describtion of the monotone trianglution and partitioning
一类e-凹-凸混合单调算子新不动点定理,杜新生,,混合单调算子是一类重要的非线性算子,广泛存在于非线性微分方程和积分方程的研究中。在半序Banch空间中研究混合单调算子,一般要�
Hal L. Smith-Monotone Dynamical Systems_ An Introduction to the Theory of Competitive and Cooperative Systems.djvu
In this paper, we propose an algorithm for solving systems of monotone equations. The method is a combination of the well-known PRP method and the hyperplane projection method. We prove that the ...
A structure of minimal 2 class is given.According to this and the result of reference, a relationship befween the two theorems of monotone classes is proved.
We added three new chapters: Chapter 22 on monotone chains, Chapter 23 on the exclusion process, and Chapter 24 that relates mixing times and hitting time parameters to stationary stopping times....
Shape Preservation of Convex or Concave Data. Rational Histosplines. Exponential Spline Interpolants. First Derivatives as Unknowns. Second Derivatives as Unknowns. Periodic Exponential Spline ...
Sux4J, Sux4J是将简洁的数据结构引入Java的努力 欢迎使用 Sux4J 。Sux4J 是把简洁的数据结构给Java带来的努力。 目前,它提供了许多相关的...压缩列表和 [[monotone] 最小完美hash]函数。seba ( mailto:sebastiano.v
矩阵理论教材参考
monotone_mixture 具有单调形状约束的部分线性模型混合的驱动程序和模型定义。 要实现:用mono_reg()作为模型参数从flexmix包中调用flexmix() 。 例如,对flexmix()的以下调用会生成一个包含6个成分的模型,每个...
「云安全」Error_Detection_in_Monotone_Span_Programs_with_Application_to_Communication-Efficient_Multiparty_Computation - 勒索病毒 数据安全 安全资讯 安全人才 技术分析数据安全
课程涵盖礼品包装(Jarvis March)、Graham Scan、Quickhull、Monotone Chain、Melkman、Sklansky、Kirkpatrick & Seidel(终极版),最后是 Chan 的算法。 Chan 算法(以其发明者 Timothy M. Chan 命名)是一种...
Monotone Minimal Perfect Hashing: Searching a Sorted Table with O(1) AccessesDjamal Belazzougui∗ Paolo Boldi† Rasmus Pagh‡ Sebastiano Vigna†Abstract A minimal perfect hash function maps a set S of...