Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Convex Hull | Reply
Name
Convex Hull

Problem
How to construct a convex hull of a set of points on a plane.

Solution
A convex hull of a set of points on a plane is such a convex polygon with minimal possible area that every point of the given set is either inside of it or on its boundary. In a case where this set has no three points aren’t on the same line, a convex hull is a degenerate polygon (i.e. a segment) covering all these points with minimal possible perimeter (i.e. double-length of a segment).

As we construct the convex hull as a sequence of its vertices, let’s consider for simplicity there should be no angles of 180° in our convex hull.

A simple brute force method is such. For every pair of vertices A and B let’s check if other points of the set are in the same half plane relative to a line AB, and if some points are on that line, they are on a segment AB. If this condition is true, the segment AB is one of edges of the convex hull. This takes O(N3) time, where N is the number of points in the given set.

Jarvis’s march for constructing a convex hull is the most popular method of doing this.
Here we construct the convex hull, adding its vertices consequently. First we find a point which is guaranteed a vertex of the convex hull – for example, the point with minimal x-coordinate, and if there are several, the one with minimal y-coordinate among them – let’s call it P1. Then at every i-th iteration we find such a point Pi, that the angle between vectors Pi-1Pi and Pi-2Pi-1 is minimal possible, and if there are several – the most distant from Pi-1. (And at the iteration 2 we can use as P0 a point with coordinates (xP1-c; yP1) where c is some positive number – to find a vector forming minimal angle with positive direction of OX axis.) We stop this process when we find out that the best candidate for the next Pi is the first point P1. So the time complexity of this algorithm is O(NM), where N is the total number of points in the set considered, and M is the number of points in the convex hull.

Graham’s scan is somewhat more difficult, but somewhat faster method of solving this problem. We describe it here mostly for other programming competitions formats than TopCoder Algorithm, because it’s hard to think of a problem of this format where O(NM) time complexity isn’t sufficient.
Here first we find a point P1 which is guaranteed a vertex of the convex hull, as in Jarvis’s march. Then we sort all other points Pi by an angle forming by a vector P1Pi with coordinate axes. Then we start scanning from the triple of points (P1, P2, P3) and going in the next manner. For every triple (Pi, Pj, Pk) the point Pj is under investigation: namely, if we going along the perimeter counterclockwise and the oriented square of triangle PiPjPk is positive, it’s OK, and the next triple is (Pj, Pk, Pnext[k]). But if the oriented square is negative, we eliminate Pj, and the next triple is (Pprev[i], Pi, Pk) – with an exception for triples where i is 1 – we don’t ever investigate the first vertex, the next triple instead is (Pi, Pk, Pnext[k]). (Here “prev” and “next” means the previous and next point to the given one those haven’t been eliminated yet. We should initialize them as next[i] = i mod N + 1 and prev[i] = (i + N – 2) mod N + 1 and recount them for the time O(1) when eliminating a vertex.) We stop this process when we reach the end of the cycle, i.e. when we go to investigate the vertex 1 when come to it from another side. (To provide the absence of 180° angles, we should sort first sequence of vertices P2, …, Pf, for which angle forming by vectors P0Pi and coordinate axis are the same, by increasing of lengths P0Pi, and last analogical sequence of vertices Pl, …, PN by decreasing of these length, and eliminate a point Pj when considering a triple (Pi, Pj, Pk) even when a square of triangle PiPjPk is equal to zero.) All points those aren’t eliminated when we stop the scan form the convex hull. As the scan itself takes O(N) time, the time complexity of the whole algorithm is O(N*logN) because of beforehand sorting.
Re: Convex Hull (response to post by Ferlon) | Reply
Discussion
A good example is ExtendableTriangles problem. Instead of counting extendable triangles directly, we just subtract a number of non-extendable triangles from a total number of triangles (which is NRNGNB – a product of numbers of points of corresponding color). So, which triangles are non-extendable? The necessary, but not sufficient requirement for triangle to be non-extendable is that every its vertex is on a boundary of a convex hull of points of the same color. So for every of three colors we should construct a convex hull, and we should allow 180° angles here. So, if N is the maximum of a number of rows and a number of columns, a time complexity of this part is O(N3) if we use Jarvis’s march – there are O(N2) points, and O(N) points in the convex hull. Then for every triangle formed by three points of different convex hulls we should check if it is really non-extendable, i.e. if we change one of its vertices to another of the same color, its square doesn’t increase. We cannot do this directly because of that there are about 200 points of the same color in every of three convex hull in the worst case, so O(N4) is too slow, but we can do some pre-calculation, namely, for every pair of points from two distinct convex hulls, we should find a maximal possible area of a triangle formed by these two and some third point from the third convex hull, and then check non-extendability of every triangle for O(1), so the whole time complexity is O(N3). Here is the code:
#include <string>
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;
const int c=50;
struct point {
	int x,y;
	point (int xx=0, int yy=0) {
		x=xx;
		y=yy;
	}
};
vector<int> r[3];
vector<point> a[3];
bool b[c*c];
short msq[3][c*c][c*c];
int n,m;
inline int f(char h) {
	if (h=='R') return 0; else
	if (h=='G') return 1; else
	return 2;
}
point operator - (const point &a, const point &b) {
	return point(a.x-b.x,a.y-b.y);
}
int operator * (const point &a, const point &b) {
	return a.x*b.x+a.y*b.y;
}
ll sqr(ll a) {
	return a*a;
}
ll dist2(const point &a, const point &b) {
	return sqr(a.x-b.x)+sqr(a.y-b.y);
}
inline int sign(int a) {
	if (a>0) return 1; else
	if (a<0) return -1; else
	return 0;
}
bool better(const point &j, const point &i, const point &p, const point &pp) {
	int r0i=(i-p)*(p-pp);
	int r0j=(j-p)*(p-pp);
	if (sign(r0i)!=sign(r0j)) return sign(r0i)<sign(r0j);
	ll ri=sqr((i-p)*(p-pp))*dist2(p,pp)*dist2(j,p);
	ll rj=sqr((j-p)*(p-pp))*dist2(p,pp)*dist2(i,p);
	if (ri!=rj) if (r0i>0) return ri<rj; else return ri>rj; else return dist2(j,p)<dist2(i,p);
}
short sq(const point &a, const point &b, const point &c) {
	return abs(a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y));
}
void get(int w) {
	int i,j;
	if (a[w].size()<=3) {
		for (i=0; i<a[w].size(); ++i) r[w].push_back(i);
		return;
	}
	r[w].push_back(0);
	point p(a[w][0].x,a[w][0].y-10);
	memset(b,0,sizeof(b));
	while (1) {
		i=-1;
		for (j=0; j<a[w].size(); ++j)
			if (j!=r[w][r[w].size()-1] && !b[j] && (i==-1 || better(a[w][j],a[w][i],a[w][r[w][r[w].size()-1]],p)))
				i=j;
		p=a[w][r[w][r[w].size()-1]];
		if (i==0) break;
		b[i]=1;
		r[w].push_back(i);
	}
}
class ExtendableTriangles {
public:
	int getCount (vector<string> s) {
		int i,j,k;
		n=s.size();
		m=s[0].size();
		int area;
		for (i=0; i<3; ++i) a[i].clear();
		for (i=0; i<3; ++i) r[i].clear();
		for (i=0; i<n; ++i)
			for (j=0; j<m; ++j)
				a[f(s[i][j])].push_back(point(i,j));
		for (i=0; i<3; ++i) get(i);
		int ans=a[0].size()*a[1].size()*a[2].size();		
		for (i=0; i<r[0].size(); ++i) {
			for (j=0; j<r[1].size(); ++j) {
				msq[0][i][j]=0;
				for (k=0; k<r[2].size(); ++k)
					msq[0][i][j]=max(msq[0][i][j],sq(a[0][r[0][i]],a[1][r[1][j]],a[2][r[2][k]]));
			}
			for (k=0; k<r[2].size(); ++k) {
				msq[1][i][k]=0;
				for (j=0; j<r[1].size(); ++j)
					msq[1][i][k]=max(msq[1][i][k],sq(a[0][r[0][i]],a[1][r[1][j]],a[2][r[2][k]]));
			}
		}
		for (j=0; j<r[1].size(); ++j) {
			for (k=0; k<r[2].size(); ++k) {
				msq[2][j][k]=0;
				for (i=0; i<r[0].size(); ++i)
					msq[2][j][k]=max(msq[2][j][k],sq(a[0][r[0][i]],a[1][r[1][j]],a[2][r[2][k]]));
			}
		}
		for (i=0; i<r[0].size(); ++i)
			for (j=0; j<r[1].size(); ++j)
				for (k=0; k<r[2].size(); ++k) {
					area=sq(a[0][r[0][i]],a[1][r[1][j]],a[2][r[2][k]]);
					if (area<msq[0][i][j] || area<msq[1][i][k] || area<msq[2][j][k]) continue;
					--ans;
				}
		return ans;
	}
};

Also there is an example of a hard problem where there is an easy part of constructing a convex hull – NCool.
RSS