static List compute(ArrayList points)
{
if(points.size() < 3) return points;
Collections.sort(points);
LinkedList upper = new LinkedList();
LinkedList lower = new LinkedList();
for( Point point : points)
{
upper.add(point);
while(upper.size() >= 3 && !rightTurn(upper))
{
upper.remove(upper.size() - 2);
}
}
for( int i = points.size() - 1; i >= 0; i--)
{
lower.add(points.get(i));
while(lower.size() >= 3 && !rightTurn(lower))
{
lower.remove(lower.size() - 2);
}
}
lower.remove(0);
lower.remove(lower.size() - 1);
upper.addAll(lower);
return upper;
}
Wednesday, December 21, 2005
Convex Hull. Yay!
Subscribe to:
Post Comments (Atom)
2 comments:
Um...what?
I left out some stuff there. First, here's a point (static because it's an inner class):
public static class Point implements Comparable
{
int x;
int y;
public int compareTo(Object o)
{
Point other = (Point)o;
if(x < other.x) return -1;
if(x > other.x) return 1;
return y - other.y;
}
Point(int x,int y)
{
this.x = x;
this.y = y;
}
public boolean onRight(Point src,Point dest)
{
int det = dest.x * y - dest.y * x;
det += src.x * dest.y - src.y * dest.x;
det -= src.x * y - src.y * x;
System.out.println("onRight: " + this + " :::: " + src + " :: " + dest + " was " + det);
return det <= 0;
}
public String toString()
{
return "(" + x + "," + y + ")";
}
}
Next, the rightTurn utility function:
static boolean rightTurn(List<Point> l)
{
return l.get(l.size() - 1).onRight(l.get(l.size() - 3),l.get(l.size() - 2));
}
Post a Comment