Breaking
Randomized

Smallest Enclosing Disk

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++)
} else {
for (int i = 0; i < n; i++)
.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)

}

}
}```

Output

```X co-ordinate equal
Y co-ordinate equal