- only works with positive integers
- fails to end if the start point (the left most point) is not on the convex hull
However it may be useful to some people and it is at least a record of what I've tried. So on to the program.
As noted in a previous blog entry I used this when creating the area maps for UK postcodes. It didn't show the area very well, after all most areas are concave hulls, but did at least make nice maps.
The algorithm is just an implementation of the determinant method of calculating the convex hull. Google 'java convex hull' for some good websites showing the details. The only problem with these websites is that they never showed the code used - none that I saw anyway. In any case, where is the fun in having something spelled out to you (oh the irony). Listed next is what I came up with.
private ArrayList<Point> calcVHull(ArrayList<Point> listPoints){
//Calculate convex vector of points
ArrayList<Point> hullPoints = new ArrayList<>();
Point lp = new Point(Integer.MAX_VALUE,0);
Point rp = new Point(0,0);
Point np = new Point();
//Calculate leftmost and rightmost points - lp and rp
for(int i=0;i<listPoints.size();i++){
if(listPoints.get(i).x<=lp.x){
lp.move(listPoints.get(i).x, listPoints.get(i).y);
}
if(listPoints.get(i).x>=rp.x){
rp.move(listPoints.get(i).x, listPoints.get(i).y);
}
}
//So calculate determinant and find the point for which every det is positive
hullPoints.add(new Point(lp));
np.setLocation(lp);
do {
for(int i=0;i<listPoints.size();i++){
boolean nextPoint = true;
if(np.x==listPoints.get(i).x && np.y==listPoints.get(i).y){
continue;
}
for(int j=0;j<listPoints.size();j++){
if(i==j || (np.x==listPoints.get(j).x && np.y==listPoints.get(j).y)){
continue;
}
long det = (long) np.x*((long) listPoints.get(i).y-(long) listPoints.get(j).y)+ (long) listPoints.get(i).x*((long) listPoints.get(j).y- (long) np.y)+ (long) listPoints.get(j).x*((long) np.y- (long) listPoints.get(i).y);
if(det<0){
nextPoint = false;
break;
}
}
if(nextPoint){
np.setLocation(listPoints.get(i));
hullPoints.add(new Point(np.x,np.y));
//System.out.println(np.x + ";" + np.y);
break;
}
}
//This condition does not work well. It will sometimes never end
//if the left most point is not on the convex hull
} while (!(np.x==lp.x && np.y==lp.y));
return hullPoints;
}
Performance
The chart below shows the time taken in seconds to calculate the hull with the number of points in the area along the x-axis.
The time taken is largely irrelevant as your computer will be different to mine. What is more important is the shape of the line. The order is roughly n*log(n) - which surprised me. I thought it would scale as the square of the number of points.
Limitations
As stated earlier, this will only work with integers. It should be fairly easy to convert doubles to integers though if you don't mind limiting the accuracy. So if the numbers you were dealing with had only 2 decimal places you'd multiply the numbers by 100.
The bigger problem is the fact that the algorithm will never end if the starting point is not on the hull. It only becomes a problem when the left-most point lies in a straight line with 2 other points that are part of the convex hull. This happens very rarely but will occur more often when there are a lot of points within a small area. I guess one way around this could be to split the points into a top half of points and a bottom half of points along a line between the left-most and right-most points. Calculate the convex hulls for both of these and combine. This is also one way of speeding up the algorithm but I decided not to implement this. There's no guarantee that this wouldn't also create starting points that aren't on the hull.
The other guaranteed way to stop this happening would be to check for duplicate points every time a point is added to the hull. I'm not sure what this would do to the speed though. One to test.
No comments:
Post a Comment