Minimum covering circle problem is a mathematical problem of computing the smallest circle that contains all of a given set of points in the Euclidean plane.
Write a program to implement smallest enclosing circle.
source Code
package com.dsacode.Algorithm.randomized; import java.util.ArrayList; import java.util.Collection; import java.util.Collections; import java.util.List; import java.util.Random; class Circle { public final Point c; public final double r; public Circle(Point c, double r) { this.c = c; this.r = r; } public boolean contains(Point p) { return c.distance(p) <= r ; } public boolean contains(Collection < Point > ps) { for (Point p : ps) { if (!contains(p)) return false; } return true; } public String toString() { return String.format("Circle(x=%g, y=%g, r=%g)", c.x, c.y, r); } } class Point { public final double x; public final double y; public Point(double x, double y) { this.x = x; this.y = y; } public Point subtract(Point p) { return new Point(x - p.x, y - p.y); } public double distance(Point p) { return Math.hypot(x - p.x, y - p.y); } public double cross(Point p) { return x * p.y - y * p.x; } public double norm() { return x * x + y * y; } public String toString() { return String.format("Point(%g, %g)", x, y); } } public class Smallestenclosingcircle { private static Random random = new Random(); public static Circle makeCircle(List < Point > points) { List < Point > shuffled = new ArrayList < Point >(points); Collections.shuffle(shuffled, new Random()); Circle c = null; for (int i = 0; i < shuffled.size(); i++) { Point p = shuffled.get(i); if (c == null || !c.contains(p)) c = makeCircleOnePoint(shuffled.subList(0, i + 1), p); } return c; } private static Circle makeCircleOnePoint(List < Point > points, Point p) { Circle c = new Circle(p, 0); for (int i = 0; i < points.size(); i++) { Point q = points.get(i); if (!c.contains(q)) { if (c.r == 0) c = makeDiameter(p, q); else c = makeCircleTwoPoints(points.subList(0, i + 1), p, q); } } return c; } private static Circle makeCircleTwoPoints(List < Point > points, Point p, Point q) { Circle temp = makeDiameter(p, q); if (temp.contains(points)) return temp; Circle left = null; Circle right = null; for (Point r : points) { Point pq = q.subtract(p); double cross = pq.cross(r.subtract(p)); Circle c = makeCircumcircle(p, q, r); if (c == null) continue; else if (cross > 0 && (left == null || pq.cross(c.c.subtract(p)) > pq .cross(left.c.subtract(p)))) left = c; else if (cross < 0 && (right == null || pq.cross(c.c.subtract(p)) < pq .cross(right.c.subtract(p)))) right = c; } return right == null || left != null && left.r <= right.r ? left : right; } static Circle makeDiameter(Point a, Point b) { return new Circle(new Point((a.x + b.x) / 2, (a.y + b.y) / 2), a.distance(b) / 2); } static Circle makeCircumcircle(Point a, Point b, Point c) { double d = (a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y)) * 2; if (d == 0) return null; double x = (a.norm() * (b.y - c.y) + b.norm() * (c.y - a.y) + c.norm() * (a.y - b.y)) / d; double y = (a.norm() * (c.x - b.x) + b.norm() * (a.x - c.x) + c.norm() * (b.x - a.x)) / d; Point p = new Point(x, y); return new Circle(p, p.distance(a)); } private static List < Point > makeRandomPoints(int n) { List < Point > result = new ArrayList < Point >(); if (random.nextDouble() < 0.2) { for (int i = 0; i < n; i++) result.add(new Point(random.nextInt(10), random.nextInt(10))); } else { for (int i = 0; i < n; i++) result.add(new Point(random.nextGaussian(), random .nextGaussian())); } return result; } private static Circle smallestEnclosingCircleNaive(List < Point > points) { if (points.size() == 0) return null; else if (points.size() == 1) return new Circle(points.get(0), 0); Circle best = null; for (int i = 0; i < points.size(); i++) { for (int j = i + 1; j < points.size(); j++) { Circle c = Smallestenclosingcircle.makeDiameter(points.get(i), points.get(j)); if (c.contains(points) && (best == null || c.r < best.r)) best = c; } } if (best != null) return best; for (int i = 0; i < points.size(); i++) { for (int j = i + 1; j < points.size(); j++) { for (int k = j + 1; k < points.size(); k++) { Circle c = Smallestenclosingcircle.makeCircumcircle( points.get(i), points.get(j), points.get(k)); if (c != null && c.contains(points) && (best == null || c.r < best.r)) best = c; } } } if (best == null) throw new AssertionError(); return best; } public static void main(String args[]) { for (int i = 0; i < 3; i++) { List < Point > points = makeRandomPoints(random.nextInt(30) + 1); Circle reference = smallestEnclosingCircleNaive(points); Circle actual = Smallestenclosingcircle.makeCircle(points); if (reference.c.x == actual.c.x) System.out.println("X co-ordinate equal"); if (reference.c.y == actual.c.y) System.out.println("Y co-ordinate equal"); if (reference.r == actual.r) System.out.println("Radius equal"); } } }
Output
X co-ordinate equal Y co-ordinate equal Radius equal X co-ordinate equal Radius equal X co-ordinate equal Radius equal
Algorithm Explanation
![]() | Make random points with x and y co-ordinates. |
![]() | Make circles and two boundary points known. |
![]() | Returns the smallest circle that encloses all the given points. Runs in expected O(n) time, randomized |
![]() | If x co-ordinate equal, display the message ‘Y co-ordinate equal’. If Y co-ordinate equal, display the message ‘Y co-ordinate equal’ |
![]() | If radius equal, display the message ‘Radius equal’. |
Time Complexity
Best Case | Average Case | Worst Case |
---|---|---|
– | O(n) | – |