86 lines
2.3 KiB
Groovy
86 lines
2.3 KiB
Groovy
class ConvexHull {
|
|
private static class Point implements Comparable<Point> {
|
|
private int x, y
|
|
|
|
Point(int x, int y) {
|
|
this.x = x
|
|
this.y = y
|
|
}
|
|
|
|
@Override
|
|
int compareTo(Point o) {
|
|
return Integer.compare(x, o.x)
|
|
}
|
|
|
|
@Override
|
|
String toString() {
|
|
return String.format("(%d, %d)", x, y)
|
|
}
|
|
}
|
|
|
|
private static List<Point> convexHull(List<Point> p) {
|
|
if (p.isEmpty()) return Collections.emptyList()
|
|
p.sort(new Comparator<Point>() {
|
|
@Override
|
|
int compare(Point o1, Point o2) {
|
|
return o1 <=> o2
|
|
}
|
|
})
|
|
List<Point> h = new ArrayList<>()
|
|
|
|
// lower hull
|
|
for (Point pt : p) {
|
|
while (h.size() >= 2 && !ccw(h.get(h.size() - 2), h.get(h.size() - 1), pt)) {
|
|
h.remove(h.size() - 1)
|
|
}
|
|
h.add(pt)
|
|
}
|
|
|
|
// upper hull
|
|
int t = h.size() + 1
|
|
for (int i = p.size() - 1; i >= 0; i--) {
|
|
Point pt = p.get(i)
|
|
while (h.size() >= t && !ccw(h.get(h.size() - 2), h.get(h.size() - 1), pt)) {
|
|
h.remove(h.size() - 1)
|
|
}
|
|
h.add(pt)
|
|
}
|
|
|
|
h.remove(h.size() - 1)
|
|
return h
|
|
}
|
|
|
|
// ccw returns true if the three points make a counter-clockwise turn
|
|
private static boolean ccw(Point a, Point b, Point c) {
|
|
return ((b.x - a.x) * (c.y - a.y)) > ((b.y - a.y) * (c.x - a.x))
|
|
}
|
|
|
|
static void main(String[] args) {
|
|
List<Point> points = Arrays.asList(new Point(16, 3),
|
|
new Point(12, 17),
|
|
new Point(0, 6),
|
|
new Point(-4, -6),
|
|
new Point(16, 6),
|
|
|
|
new Point(16, -7),
|
|
new Point(16, -3),
|
|
new Point(17, -4),
|
|
new Point(5, 19),
|
|
new Point(19, -8),
|
|
|
|
new Point(3, 16),
|
|
new Point(12, 13),
|
|
new Point(3, -4),
|
|
new Point(17, 5),
|
|
new Point(-3, 15),
|
|
|
|
new Point(-3, -9),
|
|
new Point(0, 11),
|
|
new Point(-9, -3),
|
|
new Point(-4, -2),
|
|
new Point(12, 10))
|
|
|
|
List<Point> hull = convexHull(points)
|
|
println("Convex Hull: $hull")
|
|
}
|
|
}
|