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) | – |